Police want to arrest on the famous criminals of the country whose name is Kaiser. Kaiser is in one of the streets of a square shaped city with $ n$ vertical streets and $ n$ horizontal streets. In the following cases how many police officers are needed to arrest Kaiser? a) Each police officer has the same speed as Kaiser and every police officer knows the location of Kaiser anytime. b) Kaiser has an infinite speed (finite but with no bound) and police officers can only know where he is only when one of them see Kaiser. Everybody in this problem (including police officers and Kaiser) move continuously and can stop or change his path.
Problem
Source: Iranian National Olympiad (3rd Round) 2008
Tags: search, combinatorics proposed, combinatorics
JBL
20.09.2008 18:19
It was already posted (but not answered) with an additional proposed problem that wasn't on the exam: http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1468877292&t=224004
jerjer
26.09.2008 17:59
You must specify that Kaiser may not cross any policeman. This problem can be extended on any board and more generaly on graphs. To get pointers google something like "tree width" "grid width" and cops Seymour . Try the following simpler ( yet more general) problem : If you play the game on a tree ( any finite tree ) what is the minimum number of cops you need. Then of course you may try rather but narrow grid ( 1xN) obvious , 2xn , 3xn .. Hope it helps.
mathenthusiastic
04.12.2018 19:12
Sorry to revive a 10 year old topic, But this is very interesting... any solution ?
mathenthusiastic
08.12.2018 15:54
up up...
asdf334
08.12.2018 17:04
wow the last post in 2008 i was born around that time -.-
asdf334
08.12.2018 17:12
also im pretty sure you just post them along the boundaries or something