{"entities":{"Q1662492":{"pageid":1673233,"ns":120,"title":"Item:Q1662492","lastrevid":56803908,"modified":"2026-03-23T15:52:28Z","type":"item","id":"Q1662492","labels":{"en":{"language":"en","value":"How many lions are needed to clear a grid?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6920467"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$3271FD08-CE9E-4C94-BE70-F522373EC598","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"180414f540d1ab039623437cf985a674b3282b1d","datavalue":{"value":{"text":"How many lions are needed to clear a grid?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1662492$7B1B393F-63CF-4A43-A0FC-E6B2462BB9D8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ccc5207b41c8f9d7fa0486c772ff2a8ff04aaaf","datavalue":{"value":"1461.91049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662492$12728155-9554-4A1F-A6DF-51736902B59F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8773ae34f42001c81b7cbfa7c10b8cee10510044","datavalue":{"value":{"entity-type":"item","numeric-id":1662491,"id":"Q1662491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$1115EBD7-C549-41E9-A7E2-751095A9510C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9477aef9a397f1d25d6e9273ceff107807b963a1","datavalue":{"value":{"entity-type":"item","numeric-id":390366,"id":"Q390366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$B61DC9C5-8BE1-4B49-962E-68A78BCD8BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d85dc3cc798ff25ea0081f6b029d540af2faadc6","datavalue":{"value":{"entity-type":"item","numeric-id":870423,"id":"Q870423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$FE0A3BE2-D208-43F7-8FA7-5E840A9F7E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a1693234cb2b94788908b8e8a90f524543aea5b","datavalue":{"value":{"entity-type":"item","numeric-id":166235,"id":"Q166235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$E33882F6-4F02-4795-8191-41B245CDEBBB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$8136793A-B780-41A1-AA1E-F0E4BF6BCF11","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"431a43c637c8a2264e4d8145aa5a3c26bfb96786","datavalue":{"value":{"time":"+2018-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1662492$7646FE13-30DE-4207-96CF-43DEB8601B21","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c5f706a7c47846f15f5b98127efe6f88cecaf5cb","datavalue":{"value":"Summary: We consider a pursuit-evasion problem where some lions have the task to clear a grid graph whose nodes are initially contaminated. The contamination spreads one step per time unit in each direction not blocked by a lion. A vertex is cleared from its contamination whenever a lion moves to it. \\textit{P. Brass} et al. [Comput. Geom. 42, No. 2, 119--126 (2009; Zbl 1156.68574)] showed that \\(\\frac{n}{2}\\) lions are not enough to clear the \\(n\\times n\\)-grid. In this paper, we consider the same problem in dimension \\(d>2\\) and prove that \\(\\Theta(n^{d-1}/\\sqrt d)\\) lions are necessary and sufficient to clear the \\(n^d\\)-grid. Furthermore, we analyze a problem variant where the lions are also allowed to jump from grid vertices to non-adjacent grid vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$9E1E6EB7-B62D-4A99-8BE5-B0025B3886F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662492$848F9E40-7C6E-4AD7-ACB3-AE0BE1B9897A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662492$8CE37180-71F2-45FF-B872-6E3FA4281486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662492$E07E52E2-EE7E-405D-881D-262101CEF3F3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fe6df0c2a480957aa1f161bceb42c6aa770e97c9","datavalue":{"value":"6920467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662492$7FDFBEF6-8989-41D0-9726-E33B922CD97F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdeb32266fa6705178860817f7e4d14a35cc866a","datavalue":{"value":"lion and man","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$6BF33B73-2ACD-4EAA-99F1-D12D8652D94D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeafaad162422aa2e6c57e2fa618069f53190546","datavalue":{"value":"safe path planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$22FB3C0E-6707-45EE-98F5-F99319059B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bade7b9bd7630b7bdc71fa726a67c6f0af4de26","datavalue":{"value":"avoidance number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$15B4CA2A-A60A-4A77-8D4C-B38BB225A94E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0261481a59fec84d8328f301f0e114d77fe51701","datavalue":{"value":"pursuit games","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$188B22EE-9030-4194-9D71-8F84A60BE1B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77c6f1b09549445d5ec498e4c4bf0d8fc2fe6bbd","datavalue":{"value":"graph separator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$3BF7B9CE-22C8-49EE-B566-3D7C3C20A6C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dab73bef609473a7fc183a4b9efe778737f82114","datavalue":{"value":"graph search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$544D384C-911B-43D1-A6F3-41EA0D695069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"812c062dfe6a4b116e1217d30c74249a0c6ddd71","datavalue":{"value":"isoperimetric inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662492$28A0325C-BF37-4909-8D72-EFA33EE4B00E","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"650e761a5f418c574655712b35b1fe882f756011","datavalue":{"value":{"entity-type":"item","numeric-id":19297,"id":"Q19297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$B992A415-2B2A-401A-A93C-4DD82A3F07F5","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$1ACAEAB5-E464-4ACC-A106-FBF7A5C84A60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e14078071b33002588a40899e92f69574dc83b92","datavalue":{"value":"https://doi.org/10.3390/a2031069","type":"string"},"datatype":"url"},"type":"statement","id":"Q1662492$BA8CD411-324B-45B8-890E-C626DEA73DDC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"017adbc9da79015e044d08beb66d1aa02d3ef37d","datavalue":{"value":"W2082754619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662492$1D4CAD61-2837-4F01-963B-1AF78CA55A24","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f53a63d36ef875cc17e54ae305df1115dfa88e26","datavalue":{"value":{"entity-type":"item","numeric-id":4024317,"id":"Q4024317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$212DA400-1BE8-47D4-A5C9-8577906A5149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9d3f589cc14fdb4d9cef9a89f1a1d0804432c89","datavalue":{"value":{"entity-type":"item","numeric-id":4035355,"id":"Q4035355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$896091D6-48C1-48C2-BBA7-4C59EC08C9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d30315f34cd8ca007635cf42b8eec14c3225877","datavalue":{"value":{"entity-type":"item","numeric-id":807642,"id":"Q807642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$1220A559-D8AD-44CA-B510-B2580961BDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9330a39a485cadfeef2534bebcb5f6c595c08d0b","datavalue":{"value":{"entity-type":"item","numeric-id":955225,"id":"Q955225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$224B92E5-193B-4FE3-A59D-C5EC5F9E5D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcb06ac589d1773170c107116d3f9792a04fb2cc","datavalue":{"value":{"entity-type":"item","numeric-id":930894,"id":"Q930894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$BAAA53F3-FE7C-44F8-9741-B70B628B0385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73de5d06b50821afae240d17120a93d4c93bd6f1","datavalue":{"value":{"entity-type":"item","numeric-id":5286162,"id":"Q5286162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$53E9709E-FEE9-46B7-9CB2-37172BC03E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$B1328589-D1CA-4223-BEC6-076D233785D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2418b8fb5308a40363fb7ee1a8cbe2ea0a42c8","datavalue":{"value":{"entity-type":"item","numeric-id":5819415,"id":"Q5819415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$72C9FF51-CD15-4C02-B571-1F336ED246C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcd7542caac5915c8f63a224b76605abf20c2235","datavalue":{"value":{"entity-type":"item","numeric-id":1837707,"id":"Q1837707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$36AA6A1F-09A6-45E0-88DB-B03232868AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aec7a5195d839105a9eaed2e0df2aa8b7b1aebe","datavalue":{"value":{"entity-type":"item","numeric-id":4159394,"id":"Q4159394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$2BD8052D-5805-4B3D-8985-0C609056EB86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86948ae383981e54b1af98cd1b8691bd9899e11b","datavalue":{"value":{"entity-type":"item","numeric-id":2859380,"id":"Q2859380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$ABA5DA6A-34AB-4FB6-B348-A173925550E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2492d9307b5e07665e497643832cb51dc836f430","datavalue":{"value":"10.3390/A2031069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662492$550177A2-0279-4639-AF20-33974D5DF512","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1927d2a3d1ed1486950da80bf56e4a7beb9531c8","datavalue":{"value":{"entity-type":"item","numeric-id":2678261,"id":"Q2678261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12fa797a4b10314c27ba0916f4ccca2e7b14c1b2","datavalue":{"value":{"amount":"+0.8696090579032898","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662492$6E0D195B-8BB7-4765-A4FD-650CB28D66BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e9e86c8b0e854c2d351545286fc03c6f740afb3","datavalue":{"value":{"entity-type":"item","numeric-id":2080095,"id":"Q2080095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bd81ca29d8f3c5d9e121149e536cf486d7415f7","datavalue":{"value":{"amount":"+0.8627589344978333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662492$37A710D8-4E87-4C24-BE48-3E54AB7ACF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b60d52edebc4033843d1d9d6f851f065f7c3b0a","datavalue":{"value":{"entity-type":"item","numeric-id":4580077,"id":"Q4580077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2d905629bb7eac2832020be5826be79db4c5a0d","datavalue":{"value":{"amount":"+0.7100579738616943","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662492$738887C8-CD7C-4361-9399-376F27FA88E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2c811086ea49d6c7a9c137fa97387f6ae1acf15","datavalue":{"value":{"entity-type":"item","numeric-id":5140824,"id":"Q5140824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15e1d79c0915ac416d5d2c2c89809089d78747ce","datavalue":{"value":{"amount":"+0.7077254056930542","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662492$91A12D6E-5E98-4029-90FC-05558535D1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6779d84de3cfc99124cda93e3b25fc0c59d51883","datavalue":{"value":{"entity-type":"item","numeric-id":393889,"id":"Q393889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"791afef93c765caee2bb21b6ff47664436f4981e","datavalue":{"value":{"amount":"+0.6994392275810242","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1662492$62967575-03C8-4B3E-A6B8-39FCECE81F2F","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662492$76DEA92D-F3E0-4C4C-BF71-6A80EB86A31F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1662492","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1662492"}}}}}