A policeman is trying to catch a robber on a board of $2001\times2001$ squares. They play alternately, and the player whose trun it is moves to a space in one of the following directions: $\downarrow,\rightarrow,\nwarrow$. If the policeman is on the square in the bottom-right corner, he can go directly to the square in the upper-left corner (the robber can not do this). Initially the policeman is in the central square, and the robber is in the upper-left adjacent square. Show that: $a)$ The robber may move at least $10000$ times before the being captured. $b)$ The policeman has an strategy such that he will eventually catch the robber. Note: The policeman can catch the robber if he reaches the square where the robber is, but not if the robber enters the square occupied by the policeman.
Problem
Source: Spanish Communities
Tags: combinatorics unsolved, combinatorics
31.07.2016 16:05
Could you please give me some guidance ? Thank you.
13.09.2020 00:35
Solution with MinosFx Let's color the $4001$ diagonals that have positive slope with blue, red, and black starting from the bottom-right diagonal (which is the bottom-right corner) and ending with the upper-left diagonal (the upper-left corner). Here is the coloring for a $3\times 3$ board: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(3cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -9.55652892561984, xmax = 1.5509090909090903, ymin = -2.6157024793388435, ymax = 7.36776859504132; /* image dimensions */ draw((-4,2)--(-4,3)--(-3,3)--(-3,2)--cycle, linewidth(2) + blue); draw((-5,2)--(-5,3)--(-4,3)--(-4,2)--cycle, linewidth(2) + red); draw((-5,4)--(-5,5)--(-4,5)--(-4,4)--cycle, linewidth(2) + blue); draw((-4,3)--(-4,4)--(-3,4)--(-3,3)--cycle, linewidth(2) + red); draw((-5,3)--(-6,3)--(-6,4)--(-5,4)--cycle, linewidth(2) + blue); draw((-6,4)--(-6,5)--(-5,5)--(-5,4)--cycle, linewidth(2) + red); /* draw figures */ draw((-4,2)--(-4,3), linewidth(0.4) + blue); draw((-4,3)--(-3,3), linewidth(0.4) + blue); draw((-3,3)--(-3,2), linewidth(2) + blue); draw((-3,2)--(-4,2), linewidth(2) + blue); draw((-5,2)--(-5,3), linewidth(2) + red); draw((-5,3)--(-4,3), linewidth(2) + red); draw((-4,3)--(-4,2), linewidth(2) + red); draw((-4,2)--(-5,2), linewidth(2) + red); draw((-5,4)--(-5,5), linewidth(0.4) + blue); draw((-5,5)--(-4,5), linewidth(2) + blue); draw((-4,5)--(-4,4), linewidth(2) + blue); draw((-4,4)--(-5,4), linewidth(2) + blue); draw((-4,3)--(-4,4), linewidth(2) + red); draw((-4,4)--(-3,4), linewidth(2) + red); draw((-3,4)--(-3,3), linewidth(2) + red); draw((-3,3)--(-4,3), linewidth(2) + red); draw((-5,3)--(-6,3), linewidth(2) + blue); draw((-6,3)--(-6,4), linewidth(2) + blue); draw((-6,4)--(-5,4), linewidth(0.4) + blue); draw((-5,4)--(-5,3), linewidth(2) + blue); draw((-3,4)--(-3,5), linewidth(2)); draw((-5,2)--(-6,2), linewidth(2)); draw((-6,4)--(-6,5), linewidth(2) + red); draw((-6,5)--(-5,5), linewidth(2) + red); draw((-5,5)--(-5,4), linewidth(2) + red); draw((-5,4)--(-6,4), linewidth(2) + red); draw((-6,2)--(-6,3), linewidth(2)); draw((-4,5)--(-3,5), linewidth(2)); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Now, note that, only performing $\nwarrow$, $\downarrow$ or $\rightarrow$, the colors of the cells in which the policeman and the robber are on repeat periodically: blue $\mapsto$ black $\mapsto$ red $\mapsto$ blue Thus, as the policeman starts at black and the robber at red, the policeman will never catch the robber without using his "special move" (moving from the bottom-left corner directly to the upper-left corner). Morerover, he must use it twice. When he uses it for the first time, he goes from a blue cell to a red cell, while the robber would be in a black cell, according to the cycle. Hence, the policeman must perform the trick again: the policeman would go from blue to red again, but, remembering he has skipped black twice, now the robber would be in a red cell, too. Now, we explain how the robber can move $10000$ times. The strategy of the robber would be reaching the bottom-left corner and doing this repeatedly: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -6.745758138056621, xmax = 8.36871694688661, ymin = -1.7830630832992078, ymax = 10.688443680779603; /* image dimensions */ draw((-4,3)--(-5,3)--(-5,4)--(-4,4)--cycle, linewidth(2) + blue); draw((-4,5)--(-4,4)--(-5,4)--(-5,5)--cycle, linewidth(2) + red); draw((-5,4)--(-5,3)--(-6,3)--(-6,4)--cycle, linewidth(2) + red); draw((0,3)--(-1,3)--(-1,4)--(0,4)--cycle, linewidth(2) + blue); draw((-1,3)--(-2,3)--(-2,4)--(-1,4)--cycle, linewidth(2) + red); draw((-1,4)--(-1,5)--(0,5)--(0,4)--cycle, linewidth(2) + red); draw((4,3)--(3,3)--(3,4)--(4,4)--cycle, linewidth(2) + blue); draw((3,3)--(2,3)--(2,4)--(3,4)--cycle, linewidth(2) + red); draw((3,4)--(3,5)--(4,5)--(4,4)--cycle, linewidth(2) + red); draw((8,3)--(7,3)--(7,4)--(8,4)--cycle, linewidth(2) + blue); draw((7,3)--(6,3)--(6,4)--(7,4)--cycle, linewidth(2) + red); draw((7,4)--(7,5)--(8,5)--(8,4)--cycle, linewidth(2) + red); /* draw figures */ draw((-3.608128237093616,3.98299760787552)--(-2.409463905013026,3.98299760787552), linewidth(2),EndArrow(6)); draw((0.3825469172722511,3.98299760787552)--(1.5958291070611412,3.9976154655838196), linewidth(2),EndArrow(6)); draw((4.387839929346418,3.9976154655838205)--(5.557268546010409,3.9976154655838205), linewidth(2),EndArrow(6)); draw((-4,3)--(-5,3), linewidth(2) + blue); draw((-5,3)--(-5,4), linewidth(0.4) + blue); draw((-5,4)--(-4,4), linewidth(0.4) + blue); draw((-4,4)--(-4,3), linewidth(2) + blue); draw((-4,5)--(-4,4), linewidth(2) + red); draw((-4,4)--(-5,4), linewidth(2) + red); draw((-5,4)--(-5,5), linewidth(2) + red); draw((-5,5)--(-4,5), linewidth(2) + red); draw((-5,4)--(-5,3), linewidth(2) + red); draw((-5,3)--(-6,3), linewidth(2) + red); draw((-6,3)--(-6,4), linewidth(2) + red); draw((-6,4)--(-5,4), linewidth(2) + red); draw((0,3)--(-1,3), linewidth(2) + blue); draw((-1,3)--(-1,4), linewidth(0.4) + blue); draw((-1,4)--(0,4), linewidth(0.4) + blue); draw((0,4)--(0,3), linewidth(2) + blue); draw((-1,3)--(-2,3), linewidth(2) + red); draw((-2,3)--(-2,4), linewidth(2) + red); draw((-2,4)--(-1,4), linewidth(2) + red); draw((-1,4)--(-1,3), linewidth(2) + red); draw((-1,4)--(-1,5), linewidth(2) + red); draw((-1,5)--(0,5), linewidth(2) + red); draw((0,5)--(0,4), linewidth(2) + red); draw((0,4)--(-1,4), linewidth(2) + red); draw((4,3)--(3,3), linewidth(2) + blue); draw((3,3)--(3,4), linewidth(0.4) + blue); draw((3,4)--(4,4), linewidth(0.4) + blue); draw((4,4)--(4,3), linewidth(2) + blue); draw((3,3)--(2,3), linewidth(2) + red); draw((2,3)--(2,4), linewidth(2) + red); draw((2,4)--(3,4), linewidth(2) + red); draw((3,4)--(3,3), linewidth(2) + red); draw((3,4)--(3,5), linewidth(2) + red); draw((3,5)--(4,5), linewidth(2) + red); draw((4,5)--(4,4), linewidth(2) + red); draw((4,4)--(3,4), linewidth(2) + red); draw((8,3)--(7,3), linewidth(2) + blue); draw((7,3)--(7,4), linewidth(0.4) + blue); draw((7,4)--(8,4), linewidth(0.4) + blue); draw((8,4)--(8,3), linewidth(2) + blue); draw((7,3)--(6,3), linewidth(2) + red); draw((6,3)--(6,4), linewidth(2) + red); draw((6,4)--(7,4), linewidth(2) + red); draw((7,4)--(7,3), linewidth(2) + red); draw((7,4)--(7,5), linewidth(2) + red); draw((7,5)--(8,5), linewidth(2) + red); draw((8,5)--(8,4), linewidth(2) + red); draw((8,4)--(7,4), linewidth(2) + red); draw((6,4)--(6,5), linewidth(2)); draw((7,5)--(6,5), linewidth(2)); draw((2,4)--(2,5), linewidth(2)); draw((2,5)--(3,5), linewidth(2)); draw((-2,4)--(-2,5), linewidth(2)); draw((-2,5)--(-1,5), linewidth(2)); draw((-6,4)--(-6,5), linewidth(2)); draw((-6,5)--(-5,5), linewidth(2)); label("$R$",(2.2981490849012145,3.8125964085308546),SE*labelscalefactor); label("$R$",(-1.7282479664156294,4.8037095288549985),SE*labelscalefactor); label("$R$",(-4.701587327388068,3.8332445985376076),SE*labelscalefactor); label("$R$",(7.2950110665354515,3.8125964085308546),SE*labelscalefactor); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] As the policeman has to reach the bottom-right corner from being in the center cell, use the trick, go from the upper-left corner to the bottom-left corner, do the trick again, and reach from the upper-left corner to the bottom-left $2\times 2$ square in order to possibly catch the robber, the robber can move at least $$(1000+1000)+1+(2000+2000)+1+(1999+1999)=10000$$times. This proves $a)$. Now, let's see that the policeman, after having done the trick two times and being in the upper-left corner, indeed has an strategy for trapping the robber. The strategy is as follows: $\bullet$ The policeman uses $\rightarrow$ or $\downarrow$ until he is in the same diagonal as the robber. (He performs the move that gets him nearer to the robber's diagonal in the given turn). $\bullet$ After this happens, if the robber does $\rightarrow$ or $\downarrow$, the policeman does exactly the same thing. $\bullet$ If it is the policeman's turn and the robber is on the same diagonal as him, he uses $\downarrow$. Note that, while both of them are in the same diagonal, there is at least one free square between the policeman and the robber in the diagonal (or the policeman would have already caught the robber), as the policeman began above the robber and the robber must be in a black square during the policeman's turn. Thus, the robber never gets to be above or in the same cell as the policeman. The next time the robber performs $\nwarrow$, the policeman does $\rightarrow$, positioning himself in the same diagonal as the robber, again. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -6.928254722806678, xmax = 4.704143906950972, ymin = -7.0005807623688625, ymax = 3.612665117349596; /* image dimensions */ draw((-2,-1)--(-3,-1)--(-3,0)--(-2,0)--cycle, linewidth(2) + blue); draw((-3,-1)--(-4,-1)--(-4,0)--(-3,0)--cycle, linewidth(2) + red); draw((-2,0)--(-3,0)--(-3,1)--(-2,1)--cycle, linewidth(2) + red); draw((-5,-1)--(-6,-1)--(-6,0)--(-5,0)--cycle, linewidth(2) + blue); draw((-4,0)--(-5,0)--(-5,1)--(-4,1)--cycle, linewidth(2) + blue); draw((-3,1)--(-4,1)--(-4,2)--(-3,2)--cycle, linewidth(2) + blue); draw((-2,2)--(-3,2)--(-3,3)--(-2,3)--cycle, linewidth(2) + blue); draw((-5,0)--(-6,0)--(-6,1)--(-5,1)--cycle, linewidth(2) + red); draw((-4,1)--(-5,1)--(-5,2)--(-4,2)--cycle, linewidth(2) + red); draw((-3,2)--(-4,2)--(-4,3)--(-3,3)--cycle, linewidth(2) + red); draw((-5,2)--(-6,2)--(-6,3)--(-5,3)--cycle, linewidth(2) + blue); draw((3,-1)--(2,-1)--(2,0)--(3,0)--cycle, linewidth(2) + blue); draw((2,-1)--(1,-1)--(1,0)--(2,0)--cycle, linewidth(2) + red); draw((3,0)--(2,0)--(2,1)--(3,1)--cycle, linewidth(2) + red); draw((0,-1)--(-1,-1)--(-1,0)--(0,0)--cycle, linewidth(2) + blue); draw((0,0)--(-1,0)--(-1,1)--(0,1)--cycle, linewidth(2) + red); draw((0,2)--(-1,2)--(-1,3)--(0,3)--cycle, linewidth(2) + blue); draw((0,1)--(0,2)--(1,2)--(1,1)--cycle, linewidth(2) + red); draw((1,2)--(1,3)--(2,3)--(2,2)--cycle, linewidth(2) + red); draw((1,1)--(1,0)--(0,0)--(0,1)--cycle, linewidth(2) + blue); draw((1,1)--(1,2)--(2,2)--(2,1)--cycle, linewidth(2) + blue); draw((2,2)--(2,3)--(3,3)--(3,2)--cycle, linewidth(2) + blue); draw((-2,-6)--(-3,-6)--(-3,-5)--(-2,-5)--cycle, linewidth(2) + blue); draw((-3,-6)--(-4,-6)--(-4,-5)--(-3,-5)--cycle, linewidth(2) + red); draw((-3,-5)--(-3,-4)--(-2,-4)--(-2,-5)--cycle, linewidth(2) + red); draw((-2,-2)--(-2,-3)--(-3,-3)--(-3,-2)--cycle, linewidth(2) + blue); draw((3,-6)--(2,-6)--(2,-5)--(3,-5)--cycle, linewidth(2) + blue); draw((3,-5)--(2,-5)--(2,-4)--(3,-4)--cycle, linewidth(2) + red); draw((3,-3)--(2,-3)--(2,-2)--(3,-2)--cycle, linewidth(2) + blue); draw((2,-6)--(1,-6)--(1,-5)--(2,-5)--cycle, linewidth(2) + red); draw((0,-6)--(-1,-6)--(-1,-5)--(0,-5)--cycle, linewidth(2) + blue); draw((0,-3)--(-1,-3)--(-1,-2)--(0,-2)--cycle, linewidth(2) + blue); draw((2,-3)--(1,-3)--(1,-2)--(2,-2)--cycle, linewidth(2) + red); draw((2,-4)--(1,-4)--(1,-3)--(2,-3)--cycle, linewidth(2) + blue); draw((1,-4)--(0,-4)--(0,-3)--(1,-3)--cycle, linewidth(2) + red); draw((1,-5)--(0,-5)--(0,-4)--(1,-4)--cycle, linewidth(2) + blue); draw((0,-5)--(-1,-5)--(-1,-4)--(0,-4)--cycle, linewidth(2) + red); draw((-5,-3)--(-6,-3)--(-6,-2)--(-5,-2)--cycle, linewidth(2) + blue); draw((-3,-3)--(-4,-3)--(-4,-2)--(-3,-2)--cycle, linewidth(2) + red); draw((-3,-4)--(-4,-4)--(-4,-3)--(-3,-3)--cycle, linewidth(2) + blue); draw((-4,-5)--(-5,-5)--(-5,-4)--(-4,-4)--cycle, linewidth(2) + blue); draw((-5,-4)--(-5,-3)--(-4,-3)--(-4,-4)--cycle, linewidth(2) + red); draw((-5,-5)--(-6,-5)--(-6,-4)--(-5,-4)--cycle, linewidth(2) + red); draw((-5,-6)--(-6,-6)--(-6,-5)--(-5,-5)--cycle, linewidth(2) + blue); /* draw figures */ draw((-2,-1)--(-3,-1), linewidth(2) + blue); draw((-3,-1)--(-3,0), linewidth(2) + blue); draw((-3,0)--(-2,0), linewidth(2) + blue); draw((-2,0)--(-2,-1), linewidth(2) + blue); draw((-3,-1)--(-4,-1), linewidth(2) + red); draw((-4,-1)--(-4,0), linewidth(2) + red); draw((-4,0)--(-3,0), linewidth(2) + red); draw((-3,0)--(-3,-1), linewidth(2) + red); draw((-2,0)--(-3,0), linewidth(2) + red); draw((-3,0)--(-3,1), linewidth(2) + red); draw((-3,1)--(-2,1), linewidth(2) + red); draw((-2,1)--(-2,0), linewidth(2) + red); draw((-5,-1)--(-6,-1), linewidth(2) + blue); draw((-6,-1)--(-6,0), linewidth(2) + blue); draw((-6,0)--(-5,0), linewidth(2) + blue); draw((-5,0)--(-5,-1), linewidth(2) + blue); draw((-4,0)--(-5,0), linewidth(2) + blue); draw((-5,0)--(-5,1), linewidth(2) + blue); draw((-5,1)--(-4,1), linewidth(2) + blue); draw((-4,1)--(-4,0), linewidth(2) + blue); draw((-3,1)--(-4,1), linewidth(2) + blue); draw((-4,1)--(-4,2), linewidth(2) + blue); draw((-4,2)--(-3,2), linewidth(2) + blue); draw((-3,2)--(-3,1), linewidth(2) + blue); draw((-2,2)--(-3,2), linewidth(2) + blue); draw((-3,2)--(-3,3), linewidth(2) + blue); draw((-3,3)--(-2,3), linewidth(2) + blue); draw((-2,3)--(-2,2), linewidth(2) + blue); draw((-5,0)--(-6,0), linewidth(2) + red); draw((-6,0)--(-6,1), linewidth(2) + red); draw((-6,1)--(-5,1), linewidth(2) + red); draw((-5,1)--(-5,0), linewidth(2) + red); draw((-4,1)--(-5,1), linewidth(2) + red); draw((-5,1)--(-5,2), linewidth(2) + red); draw((-5,2)--(-4,2), linewidth(2) + red); draw((-4,2)--(-4,1), linewidth(2) + red); draw((-3,2)--(-4,2), linewidth(2) + red); draw((-4,2)--(-4,3), linewidth(2) + red); draw((-4,3)--(-3,3), linewidth(2) + red); draw((-3,3)--(-3,2), linewidth(2) + red); draw((-5,2)--(-6,2), linewidth(2) + blue); draw((-6,2)--(-6,3), linewidth(2) + blue); draw((-6,3)--(-5,3), linewidth(2) + blue); draw((-5,3)--(-5,2), linewidth(2) + blue); draw((-5,-1)--(-4,-1), linewidth(2)); draw((-2,1)--(-2,2), linewidth(2)); draw((-4,3)--(-5,3), linewidth(2)); draw((-6,1)--(-6,2), linewidth(2)); draw((3,-1)--(2,-1), linewidth(2) + blue); draw((2,-1)--(2,0), linewidth(2) + blue); draw((2,0)--(3,0), linewidth(2) + blue); draw((3,0)--(3,-1), linewidth(2) + blue); draw((2,-1)--(1,-1), linewidth(2) + red); draw((1,-1)--(1,0), linewidth(2) + red); draw((1,0)--(2,0), linewidth(2) + red); draw((2,0)--(2,-1), linewidth(2) + red); draw((3,0)--(2,0), linewidth(2) + red); draw((2,0)--(2,1), linewidth(2) + red); draw((2,1)--(3,1), linewidth(2) + red); draw((3,1)--(3,0), linewidth(2) + red); draw((0,-1)--(-1,-1), linewidth(2) + blue); draw((-1,-1)--(-1,0), linewidth(2) + blue); draw((-1,0)--(0,0), linewidth(2) + blue); draw((0,0)--(0,-1), linewidth(2) + blue); draw((0,0)--(-1,0), linewidth(2) + red); draw((-1,0)--(-1,1), linewidth(2) + red); draw((-1,1)--(0,1), linewidth(2) + red); draw((0,1)--(0,0), linewidth(2) + red); draw((0,2)--(-1,2), linewidth(2) + blue); draw((-1,2)--(-1,3), linewidth(2) + blue); draw((-1,3)--(0,3), linewidth(2) + blue); draw((0,3)--(0,2), linewidth(2) + blue); draw((0,2)--(1,2), linewidth(2) + red); draw((1,2)--(1,1), linewidth(2) + red); draw((1,1)--(0,1), linewidth(2) + red); draw((1,2)--(1,3), linewidth(2) + red); draw((1,3)--(2,3), linewidth(2) + red); draw((2,3)--(2,2), linewidth(2) + red); draw((2,2)--(1,2), linewidth(2) + red); draw((1,1)--(1,0), linewidth(2) + blue); draw((1,0)--(0,0), linewidth(2) + blue); draw((0,0)--(0,1), linewidth(2) + blue); draw((0,1)--(1,1), linewidth(2) + blue); draw((1,1)--(1,2), linewidth(2) + blue); draw((1,2)--(2,2), linewidth(2) + blue); draw((2,2)--(2,1), linewidth(2) + blue); draw((2,1)--(1,1), linewidth(2) + blue); draw((2,2)--(2,3), linewidth(2) + blue); draw((2,3)--(3,3), linewidth(2) + blue); draw((3,3)--(3,2), linewidth(2) + blue); draw((3,2)--(2,2), linewidth(2) + blue); draw((-1.7816706774971747,0.9775970110052327)--(-1.226249843103488,0.9775970110052327), linewidth(2),EndArrow(6)); draw((-1.144968745387338,-1.1898989280920769)--(-1.8358580759746068,-1.8266008602019115), linewidth(2),EndArrow(6)); draw((-2,-6)--(-3,-6), linewidth(2) + blue); draw((-3,-6)--(-3,-5), linewidth(2) + blue); draw((-3,-5)--(-2,-5), linewidth(2) + blue); draw((-2,-5)--(-2,-6), linewidth(2) + blue); draw((-3,-6)--(-4,-6), linewidth(2) + red); draw((-4,-6)--(-4,-5), linewidth(2) + red); draw((-4,-5)--(-3,-5), linewidth(2) + red); draw((-3,-5)--(-3,-6), linewidth(2) + red); draw((-3,-5)--(-3,-4), linewidth(2) + red); draw((-3,-4)--(-2,-4), linewidth(2) + red); draw((-2,-4)--(-2,-5), linewidth(2) + red); draw((-2,-5)--(-3,-5), linewidth(2) + red); draw((-2,-2)--(-2,-3), linewidth(2) + blue); draw((-2,-3)--(-3,-3), linewidth(2) + blue); draw((-3,-3)--(-3,-2), linewidth(2) + blue); draw((-3,-2)--(-2,-2), linewidth(2) + blue); draw((3,-6)--(2,-6), linewidth(2) + blue); draw((2,-6)--(2,-5), linewidth(2) + blue); draw((2,-5)--(3,-5), linewidth(2) + blue); draw((3,-5)--(3,-6), linewidth(2) + blue); draw((3,-5)--(2,-5), linewidth(2) + red); draw((2,-5)--(2,-4), linewidth(2) + red); draw((2,-4)--(3,-4), linewidth(2) + red); draw((3,-4)--(3,-5), linewidth(2) + red); draw((3,-3)--(2,-3), linewidth(2) + blue); draw((2,-3)--(2,-2), linewidth(2) + blue); draw((2,-2)--(3,-2), linewidth(2) + blue); draw((3,-2)--(3,-3), linewidth(2) + blue); draw((2,-6)--(1,-6), linewidth(2) + red); draw((1,-6)--(1,-5), linewidth(2) + red); draw((1,-5)--(2,-5), linewidth(2) + red); draw((2,-5)--(2,-6), linewidth(2) + red); draw((0,-6)--(-1,-6), linewidth(2) + blue); draw((-1,-6)--(-1,-5), linewidth(2) + blue); draw((-1,-5)--(0,-5), linewidth(2) + blue); draw((0,-5)--(0,-6), linewidth(2) + blue); draw((0,-3)--(-1,-3), linewidth(2) + blue); draw((-1,-3)--(-1,-2), linewidth(2) + blue); draw((-1,-2)--(0,-2), linewidth(2) + blue); draw((0,-2)--(0,-3), linewidth(2) + blue); draw((2,-3)--(1,-3), linewidth(2) + red); draw((1,-3)--(1,-2), linewidth(2) + red); draw((1,-2)--(2,-2), linewidth(2) + red); draw((2,-2)--(2,-3), linewidth(2) + red); draw((2,-4)--(1,-4), linewidth(2) + blue); draw((1,-4)--(1,-3), linewidth(2) + blue); draw((1,-3)--(2,-3), linewidth(2) + blue); draw((2,-3)--(2,-4), linewidth(2) + blue); draw((1,-4)--(0,-4), linewidth(2) + red); draw((0,-4)--(0,-3), linewidth(2) + red); draw((0,-3)--(1,-3), linewidth(2) + red); draw((1,-3)--(1,-4), linewidth(2) + red); draw((1,-5)--(0,-5), linewidth(2) + blue); draw((0,-5)--(0,-4), linewidth(2) + blue); draw((0,-4)--(1,-4), linewidth(2) + blue); draw((1,-4)--(1,-5), linewidth(2) + blue); draw((0,-5)--(-1,-5), linewidth(2) + red); draw((-1,-5)--(-1,-4), linewidth(2) + red); draw((-1,-4)--(0,-4), linewidth(2) + red); draw((0,-4)--(0,-5), linewidth(2) + red); draw((-5,-3)--(-6,-3), linewidth(2) + blue); draw((-6,-3)--(-6,-2), linewidth(2) + blue); draw((-6,-2)--(-5,-2), linewidth(2) + blue); draw((-5,-2)--(-5,-3), linewidth(2) + blue); draw((-3,-3)--(-4,-3), linewidth(2) + red); draw((-4,-3)--(-4,-2), linewidth(2) + red); draw((-4,-2)--(-3,-2), linewidth(2) + red); draw((-3,-2)--(-3,-3), linewidth(2) + red); draw((-3,-4)--(-4,-4), linewidth(2) + blue); draw((-4,-4)--(-4,-3), linewidth(2) + blue); draw((-4,-3)--(-3,-3), linewidth(2) + blue); draw((-3,-3)--(-3,-4), linewidth(2) + blue); draw((-4,-5)--(-5,-5), linewidth(2) + blue); draw((-5,-5)--(-5,-4), linewidth(2) + blue); draw((-5,-4)--(-4,-4), linewidth(2) + blue); draw((-4,-4)--(-4,-5), linewidth(2) + blue); draw((-5,-4)--(-5,-3), linewidth(2) + red); draw((-5,-3)--(-4,-3), linewidth(2) + red); draw((-4,-3)--(-4,-4), linewidth(2) + red); draw((-4,-4)--(-5,-4), linewidth(2) + red); draw((-5,-5)--(-6,-5), linewidth(2) + red); draw((-6,-5)--(-6,-4), linewidth(2) + red); draw((-6,-4)--(-5,-4), linewidth(2) + red); draw((-5,-4)--(-5,-5), linewidth(2) + red); draw((-5,-6)--(-6,-6), linewidth(2) + blue); draw((-6,-6)--(-6,-5), linewidth(2) + blue); draw((-6,-5)--(-5,-5), linewidth(2) + blue); draw((-5,-5)--(-5,-6), linewidth(2) + blue); draw((-1.7991049342473708,-4.535285403222338)--(-1.0839408493060767,-4.535285403222338), linewidth(2),EndArrow(6)); draw((-6,-4)--(-6,-3), linewidth(2)); draw((-5,-2)--(-4,-2), linewidth(2)); draw((-5,-6)--(-4,-6), linewidth(2)); draw((-2,-4)--(-2,-3), linewidth(2)); draw((-1,1)--(-1,2), linewidth(2)); draw((0,3)--(1,3), linewidth(2)); draw((3,1)--(3,2), linewidth(2)); draw((1,-1)--(0,-1), linewidth(2)); draw((0,-2)--(1,-2), linewidth(2)); draw((3,-4)--(3,-3), linewidth(2)); draw((1,-6)--(0,-6), linewidth(2)); draw((-1,-4)--(-1,-3), linewidth(2)); draw((0,1)--(0,2), linewidth(2)); draw((1,-6)--(1,-5), linewidth(2)); label("$P$",(-5.715814382242815,2.769228358696473),SE*labelscalefactor); label("$P$",(-0.6903370286012918,1.6973608112414633),SE*labelscalefactor); label("$P$",(-5.645527985688388,-3.2754017449842387),SE*labelscalefactor); label("$R$",(0.36395891971511163,-3.257830145845632),SE*labelscalefactor); label("$P$",(0.10038493263601078,-3.257830145845632),SE*labelscalefactor); label("$R$",(1.3655400706156948,0.7484944577567003),SE*labelscalefactor); label("$R$",(-3.6950804813030413,0.7133512594794869),SE*labelscalefactor); label("$R$",(-4.749376429619445,-3.257830145845632),SE*labelscalefactor); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] It is clear that the policeman can always play in that way. As he only uses $\downarrow$ and $\rightarrow$, the amount of moves must end, and the only way this can happen is if the policeman is already on the same cell as the robber, proving $b)$. We are done $\square$.
12.10.2020 03:00
Modesti wrote: Solution with MinosFx Let's color the $4001$ diagonals that have positive slope with blue, red, and black starting from the bottom-right diagonal (which is the bottom-right corner) and ending with the upper-left diagonal (the upper-left corner). Here is the coloring for a $3\times 3$ board: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(3cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -9.55652892561984, xmax = 1.5509090909090903, ymin = -2.6157024793388435, ymax = 7.36776859504132; /* image dimensions */ draw((-4,2)--(-4,3)--(-3,3)--(-3,2)--cycle, linewidth(2) + blue); draw((-5,2)--(-5,3)--(-4,3)--(-4,2)--cycle, linewidth(2) + red); draw((-5,4)--(-5,5)--(-4,5)--(-4,4)--cycle, linewidth(2) + blue); draw((-4,3)--(-4,4)--(-3,4)--(-3,3)--cycle, linewidth(2) + red); draw((-5,3)--(-6,3)--(-6,4)--(-5,4)--cycle, linewidth(2) + blue); draw((-6,4)--(-6,5)--(-5,5)--(-5,4)--cycle, linewidth(2) + red); /* draw figures */ draw((-4,2)--(-4,3), linewidth(0.4) + blue); draw((-4,3)--(-3,3), linewidth(0.4) + blue); draw((-3,3)--(-3,2), linewidth(2) + blue); draw((-3,2)--(-4,2), linewidth(2) + blue); draw((-5,2)--(-5,3), linewidth(2) + red); draw((-5,3)--(-4,3), linewidth(2) + red); draw((-4,3)--(-4,2), linewidth(2) + red); draw((-4,2)--(-5,2), linewidth(2) + red); draw((-5,4)--(-5,5), linewidth(0.4) + blue); draw((-5,5)--(-4,5), linewidth(2) + blue); draw((-4,5)--(-4,4), linewidth(2) + blue); draw((-4,4)--(-5,4), linewidth(2) + blue); draw((-4,3)--(-4,4), linewidth(2) + red); draw((-4,4)--(-3,4), linewidth(2) + red); draw((-3,4)--(-3,3), linewidth(2) + red); draw((-3,3)--(-4,3), linewidth(2) + red); draw((-5,3)--(-6,3), linewidth(2) + blue); draw((-6,3)--(-6,4), linewidth(2) + blue); draw((-6,4)--(-5,4), linewidth(0.4) + blue); draw((-5,4)--(-5,3), linewidth(2) + blue); draw((-3,4)--(-3,5), linewidth(2)); draw((-5,2)--(-6,2), linewidth(2)); draw((-6,4)--(-6,5), linewidth(2) + red); draw((-6,5)--(-5,5), linewidth(2) + red); draw((-5,5)--(-5,4), linewidth(2) + red); draw((-5,4)--(-6,4), linewidth(2) + red); draw((-6,2)--(-6,3), linewidth(2)); draw((-4,5)--(-3,5), linewidth(2)); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Now, note that, only performing $\nwarrow$, $\downarrow$ or $\rightarrow$, the colors of the cells in which the policeman and the robber are on repeat periodically: blue $\mapsto$ black $\mapsto$ red $\mapsto$ blue Thus, as the policeman starts at black and the robber at red, the policeman will never catch the robber without using his "special move" (moving from the bottom-left corner directly to the upper-left corner). Morerover, he must use it twice. When he uses it for the first time, he goes from a blue cell to a red cell, while the robber would be in a black cell, according to the cycle. Hence, the policeman must perform the trick again: the policeman would go from blue to red again, but, remembering he has skipped black twice, now the robber would be in a red cell, too. Now, we explain how the robber can move $10000$ times. The strategy of the robber would be reaching the bottom-left corner and doing this repeatedly: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -6.745758138056621, xmax = 8.36871694688661, ymin = -1.7830630832992078, ymax = 10.688443680779603; /* image dimensions */ draw((-4,3)--(-5,3)--(-5,4)--(-4,4)--cycle, linewidth(2) + blue); draw((-4,5)--(-4,4)--(-5,4)--(-5,5)--cycle, linewidth(2) + red); draw((-5,4)--(-5,3)--(-6,3)--(-6,4)--cycle, linewidth(2) + red); draw((0,3)--(-1,3)--(-1,4)--(0,4)--cycle, linewidth(2) + blue); draw((-1,3)--(-2,3)--(-2,4)--(-1,4)--cycle, linewidth(2) + red); draw((-1,4)--(-1,5)--(0,5)--(0,4)--cycle, linewidth(2) + red); draw((4,3)--(3,3)--(3,4)--(4,4)--cycle, linewidth(2) + blue); draw((3,3)--(2,3)--(2,4)--(3,4)--cycle, linewidth(2) + red); draw((3,4)--(3,5)--(4,5)--(4,4)--cycle, linewidth(2) + red); draw((8,3)--(7,3)--(7,4)--(8,4)--cycle, linewidth(2) + blue); draw((7,3)--(6,3)--(6,4)--(7,4)--cycle, linewidth(2) + red); draw((7,4)--(7,5)--(8,5)--(8,4)--cycle, linewidth(2) + red); /* draw figures */ draw((-3.608128237093616,3.98299760787552)--(-2.409463905013026,3.98299760787552), linewidth(2),EndArrow(6)); draw((0.3825469172722511,3.98299760787552)--(1.5958291070611412,3.9976154655838196), linewidth(2),EndArrow(6)); draw((4.387839929346418,3.9976154655838205)--(5.557268546010409,3.9976154655838205), linewidth(2),EndArrow(6)); draw((-4,3)--(-5,3), linewidth(2) + blue); draw((-5,3)--(-5,4), linewidth(0.4) + blue); draw((-5,4)--(-4,4), linewidth(0.4) + blue); draw((-4,4)--(-4,3), linewidth(2) + blue); draw((-4,5)--(-4,4), linewidth(2) + red); draw((-4,4)--(-5,4), linewidth(2) + red); draw((-5,4)--(-5,5), linewidth(2) + red); draw((-5,5)--(-4,5), linewidth(2) + red); draw((-5,4)--(-5,3), linewidth(2) + red); draw((-5,3)--(-6,3), linewidth(2) + red); draw((-6,3)--(-6,4), linewidth(2) + red); draw((-6,4)--(-5,4), linewidth(2) + red); draw((0,3)--(-1,3), linewidth(2) + blue); draw((-1,3)--(-1,4), linewidth(0.4) + blue); draw((-1,4)--(0,4), linewidth(0.4) + blue); draw((0,4)--(0,3), linewidth(2) + blue); draw((-1,3)--(-2,3), linewidth(2) + red); draw((-2,3)--(-2,4), linewidth(2) + red); draw((-2,4)--(-1,4), linewidth(2) + red); draw((-1,4)--(-1,3), linewidth(2) + red); draw((-1,4)--(-1,5), linewidth(2) + red); draw((-1,5)--(0,5), linewidth(2) + red); draw((0,5)--(0,4), linewidth(2) + red); draw((0,4)--(-1,4), linewidth(2) + red); draw((4,3)--(3,3), linewidth(2) + blue); draw((3,3)--(3,4), linewidth(0.4) + blue); draw((3,4)--(4,4), linewidth(0.4) + blue); draw((4,4)--(4,3), linewidth(2) + blue); draw((3,3)--(2,3), linewidth(2) + red); draw((2,3)--(2,4), linewidth(2) + red); draw((2,4)--(3,4), linewidth(2) + red); draw((3,4)--(3,3), linewidth(2) + red); draw((3,4)--(3,5), linewidth(2) + red); draw((3,5)--(4,5), linewidth(2) + red); draw((4,5)--(4,4), linewidth(2) + red); draw((4,4)--(3,4), linewidth(2) + red); draw((8,3)--(7,3), linewidth(2) + blue); draw((7,3)--(7,4), linewidth(0.4) + blue); draw((7,4)--(8,4), linewidth(0.4) + blue); draw((8,4)--(8,3), linewidth(2) + blue); draw((7,3)--(6,3), linewidth(2) + red); draw((6,3)--(6,4), linewidth(2) + red); draw((6,4)--(7,4), linewidth(2) + red); draw((7,4)--(7,3), linewidth(2) + red); draw((7,4)--(7,5), linewidth(2) + red); draw((7,5)--(8,5), linewidth(2) + red); draw((8,5)--(8,4), linewidth(2) + red); draw((8,4)--(7,4), linewidth(2) + red); draw((6,4)--(6,5), linewidth(2)); draw((7,5)--(6,5), linewidth(2)); draw((2,4)--(2,5), linewidth(2)); draw((2,5)--(3,5), linewidth(2)); draw((-2,4)--(-2,5), linewidth(2)); draw((-2,5)--(-1,5), linewidth(2)); draw((-6,4)--(-6,5), linewidth(2)); draw((-6,5)--(-5,5), linewidth(2)); label("$R$",(2.2981490849012145,3.8125964085308546),SE*labelscalefactor); label("$R$",(-1.7282479664156294,4.8037095288549985),SE*labelscalefactor); label("$R$",(-4.701587327388068,3.8332445985376076),SE*labelscalefactor); label("$R$",(7.2950110665354515,3.8125964085308546),SE*labelscalefactor); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] As the policeman has to reach the bottom-right corner from being in the center cell, use the trick, go from the upper-left corner to the bottom-left corner, do the trick again, and reach from the upper-left corner to the bottom-left $2\times 2$ square in order to possibly catch the robber, the robber can move at least $$(1000+1000)+1+(2000+2000)+1+(1999+1999)=10000$$times. This proves $a)$. Now, let's see that the policeman, after having done the trick two times and being in the upper-left corner, indeed has an strategy for trapping the robber. The strategy is as follows: $\bullet$ The policeman uses $\rightarrow$ until he is in the same diagonal as the robber. $\bullet$ After this happens, if the robber does $\rightarrow$ or $\downarrow$, the policeman does exactly the same thing. $\bullet$ If it is the policeman's turn and the robber is on the same diagonal as him, he uses $\downarrow$. Note that, while both of them are in the same diagonal, there is at least one free square between the policeman and the robber in the diagonal (or the policeman would have already caught the robber), as the policeman began above the robber and the robber must be in a black square during the policeman's turn. Thus, the robber never gets to be above or in the same cell as the policeman. The next time the robber performs $\nwarrow$, the policeman does $\rightarrow$, positioning himself in the same diagonal as the robber, again. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -6.928254722806678, xmax = 4.704143906950972, ymin = -7.0005807623688625, ymax = 3.612665117349596; /* image dimensions */ draw((-2,-1)--(-3,-1)--(-3,0)--(-2,0)--cycle, linewidth(2) + blue); draw((-3,-1)--(-4,-1)--(-4,0)--(-3,0)--cycle, linewidth(2) + red); draw((-2,0)--(-3,0)--(-3,1)--(-2,1)--cycle, linewidth(2) + red); draw((-5,-1)--(-6,-1)--(-6,0)--(-5,0)--cycle, linewidth(2) + blue); draw((-4,0)--(-5,0)--(-5,1)--(-4,1)--cycle, linewidth(2) + blue); draw((-3,1)--(-4,1)--(-4,2)--(-3,2)--cycle, linewidth(2) + blue); draw((-2,2)--(-3,2)--(-3,3)--(-2,3)--cycle, linewidth(2) + blue); draw((-5,0)--(-6,0)--(-6,1)--(-5,1)--cycle, linewidth(2) + red); draw((-4,1)--(-5,1)--(-5,2)--(-4,2)--cycle, linewidth(2) + red); draw((-3,2)--(-4,2)--(-4,3)--(-3,3)--cycle, linewidth(2) + red); draw((-5,2)--(-6,2)--(-6,3)--(-5,3)--cycle, linewidth(2) + blue); draw((3,-1)--(2,-1)--(2,0)--(3,0)--cycle, linewidth(2) + blue); draw((2,-1)--(1,-1)--(1,0)--(2,0)--cycle, linewidth(2) + red); draw((3,0)--(2,0)--(2,1)--(3,1)--cycle, linewidth(2) + red); draw((0,-1)--(-1,-1)--(-1,0)--(0,0)--cycle, linewidth(2) + blue); draw((0,0)--(-1,0)--(-1,1)--(0,1)--cycle, linewidth(2) + red); draw((0,2)--(-1,2)--(-1,3)--(0,3)--cycle, linewidth(2) + blue); draw((0,1)--(0,2)--(1,2)--(1,1)--cycle, linewidth(2) + red); draw((1,2)--(1,3)--(2,3)--(2,2)--cycle, linewidth(2) + red); draw((1,1)--(1,0)--(0,0)--(0,1)--cycle, linewidth(2) + blue); draw((1,1)--(1,2)--(2,2)--(2,1)--cycle, linewidth(2) + blue); draw((2,2)--(2,3)--(3,3)--(3,2)--cycle, linewidth(2) + blue); draw((-2,-6)--(-3,-6)--(-3,-5)--(-2,-5)--cycle, linewidth(2) + blue); draw((-3,-6)--(-4,-6)--(-4,-5)--(-3,-5)--cycle, linewidth(2) + red); draw((-3,-5)--(-3,-4)--(-2,-4)--(-2,-5)--cycle, linewidth(2) + red); draw((-2,-2)--(-2,-3)--(-3,-3)--(-3,-2)--cycle, linewidth(2) + blue); draw((3,-6)--(2,-6)--(2,-5)--(3,-5)--cycle, linewidth(2) + blue); draw((3,-5)--(2,-5)--(2,-4)--(3,-4)--cycle, linewidth(2) + red); draw((3,-3)--(2,-3)--(2,-2)--(3,-2)--cycle, linewidth(2) + blue); draw((2,-6)--(1,-6)--(1,-5)--(2,-5)--cycle, linewidth(2) + red); draw((0,-6)--(-1,-6)--(-1,-5)--(0,-5)--cycle, linewidth(2) + blue); draw((0,-3)--(-1,-3)--(-1,-2)--(0,-2)--cycle, linewidth(2) + blue); draw((2,-3)--(1,-3)--(1,-2)--(2,-2)--cycle, linewidth(2) + red); draw((2,-4)--(1,-4)--(1,-3)--(2,-3)--cycle, linewidth(2) + blue); draw((1,-4)--(0,-4)--(0,-3)--(1,-3)--cycle, linewidth(2) + red); draw((1,-5)--(0,-5)--(0,-4)--(1,-4)--cycle, linewidth(2) + blue); draw((0,-5)--(-1,-5)--(-1,-4)--(0,-4)--cycle, linewidth(2) + red); draw((-5,-3)--(-6,-3)--(-6,-2)--(-5,-2)--cycle, linewidth(2) + blue); draw((-3,-3)--(-4,-3)--(-4,-2)--(-3,-2)--cycle, linewidth(2) + red); draw((-3,-4)--(-4,-4)--(-4,-3)--(-3,-3)--cycle, linewidth(2) + blue); draw((-4,-5)--(-5,-5)--(-5,-4)--(-4,-4)--cycle, linewidth(2) + blue); draw((-5,-4)--(-5,-3)--(-4,-3)--(-4,-4)--cycle, linewidth(2) + red); draw((-5,-5)--(-6,-5)--(-6,-4)--(-5,-4)--cycle, linewidth(2) + red); draw((-5,-6)--(-6,-6)--(-6,-5)--(-5,-5)--cycle, linewidth(2) + blue); /* draw figures */ draw((-2,-1)--(-3,-1), linewidth(2) + blue); draw((-3,-1)--(-3,0), linewidth(2) + blue); draw((-3,0)--(-2,0), linewidth(2) + blue); draw((-2,0)--(-2,-1), linewidth(2) + blue); draw((-3,-1)--(-4,-1), linewidth(2) + red); draw((-4,-1)--(-4,0), linewidth(2) + red); draw((-4,0)--(-3,0), linewidth(2) + red); draw((-3,0)--(-3,-1), linewidth(2) + red); draw((-2,0)--(-3,0), linewidth(2) + red); draw((-3,0)--(-3,1), linewidth(2) + red); draw((-3,1)--(-2,1), linewidth(2) + red); draw((-2,1)--(-2,0), linewidth(2) + red); draw((-5,-1)--(-6,-1), linewidth(2) + blue); draw((-6,-1)--(-6,0), linewidth(2) + blue); draw((-6,0)--(-5,0), linewidth(2) + blue); draw((-5,0)--(-5,-1), linewidth(2) + blue); draw((-4,0)--(-5,0), linewidth(2) + blue); draw((-5,0)--(-5,1), linewidth(2) + blue); draw((-5,1)--(-4,1), linewidth(2) + blue); draw((-4,1)--(-4,0), linewidth(2) + blue); draw((-3,1)--(-4,1), linewidth(2) + blue); draw((-4,1)--(-4,2), linewidth(2) + blue); draw((-4,2)--(-3,2), linewidth(2) + blue); draw((-3,2)--(-3,1), linewidth(2) + blue); draw((-2,2)--(-3,2), linewidth(2) + blue); draw((-3,2)--(-3,3), linewidth(2) + blue); draw((-3,3)--(-2,3), linewidth(2) + blue); draw((-2,3)--(-2,2), linewidth(2) + blue); draw((-5,0)--(-6,0), linewidth(2) + red); draw((-6,0)--(-6,1), linewidth(2) + red); draw((-6,1)--(-5,1), linewidth(2) + red); draw((-5,1)--(-5,0), linewidth(2) + red); draw((-4,1)--(-5,1), linewidth(2) + red); draw((-5,1)--(-5,2), linewidth(2) + red); draw((-5,2)--(-4,2), linewidth(2) + red); draw((-4,2)--(-4,1), linewidth(2) + red); draw((-3,2)--(-4,2), linewidth(2) + red); draw((-4,2)--(-4,3), linewidth(2) + red); draw((-4,3)--(-3,3), linewidth(2) + red); draw((-3,3)--(-3,2), linewidth(2) + red); draw((-5,2)--(-6,2), linewidth(2) + blue); draw((-6,2)--(-6,3), linewidth(2) + blue); draw((-6,3)--(-5,3), linewidth(2) + blue); draw((-5,3)--(-5,2), linewidth(2) + blue); draw((-5,-1)--(-4,-1), linewidth(2)); draw((-2,1)--(-2,2), linewidth(2)); draw((-4,3)--(-5,3), linewidth(2)); draw((-6,1)--(-6,2), linewidth(2)); draw((3,-1)--(2,-1), linewidth(2) + blue); draw((2,-1)--(2,0), linewidth(2) + blue); draw((2,0)--(3,0), linewidth(2) + blue); draw((3,0)--(3,-1), linewidth(2) + blue); draw((2,-1)--(1,-1), linewidth(2) + red); draw((1,-1)--(1,0), linewidth(2) + red); draw((1,0)--(2,0), linewidth(2) + red); draw((2,0)--(2,-1), linewidth(2) + red); draw((3,0)--(2,0), linewidth(2) + red); draw((2,0)--(2,1), linewidth(2) + red); draw((2,1)--(3,1), linewidth(2) + red); draw((3,1)--(3,0), linewidth(2) + red); draw((0,-1)--(-1,-1), linewidth(2) + blue); draw((-1,-1)--(-1,0), linewidth(2) + blue); draw((-1,0)--(0,0), linewidth(2) + blue); draw((0,0)--(0,-1), linewidth(2) + blue); draw((0,0)--(-1,0), linewidth(2) + red); draw((-1,0)--(-1,1), linewidth(2) + red); draw((-1,1)--(0,1), linewidth(2) + red); draw((0,1)--(0,0), linewidth(2) + red); draw((0,2)--(-1,2), linewidth(2) + blue); draw((-1,2)--(-1,3), linewidth(2) + blue); draw((-1,3)--(0,3), linewidth(2) + blue); draw((0,3)--(0,2), linewidth(2) + blue); draw((0,2)--(1,2), linewidth(2) + red); draw((1,2)--(1,1), linewidth(2) + red); draw((1,1)--(0,1), linewidth(2) + red); draw((1,2)--(1,3), linewidth(2) + red); draw((1,3)--(2,3), linewidth(2) + red); draw((2,3)--(2,2), linewidth(2) + red); draw((2,2)--(1,2), linewidth(2) + red); draw((1,1)--(1,0), linewidth(2) + blue); draw((1,0)--(0,0), linewidth(2) + blue); draw((0,0)--(0,1), linewidth(2) + blue); draw((0,1)--(1,1), linewidth(2) + blue); draw((1,1)--(1,2), linewidth(2) + blue); draw((1,2)--(2,2), linewidth(2) + blue); draw((2,2)--(2,1), linewidth(2) + blue); draw((2,1)--(1,1), linewidth(2) + blue); draw((2,2)--(2,3), linewidth(2) + blue); draw((2,3)--(3,3), linewidth(2) + blue); draw((3,3)--(3,2), linewidth(2) + blue); draw((3,2)--(2,2), linewidth(2) + blue); draw((-1.7816706774971747,0.9775970110052327)--(-1.226249843103488,0.9775970110052327), linewidth(2),EndArrow(6)); draw((-1.144968745387338,-1.1898989280920769)--(-1.8358580759746068,-1.8266008602019115), linewidth(2),EndArrow(6)); draw((-2,-6)--(-3,-6), linewidth(2) + blue); draw((-3,-6)--(-3,-5), linewidth(2) + blue); draw((-3,-5)--(-2,-5), linewidth(2) + blue); draw((-2,-5)--(-2,-6), linewidth(2) + blue); draw((-3,-6)--(-4,-6), linewidth(2) + red); draw((-4,-6)--(-4,-5), linewidth(2) + red); draw((-4,-5)--(-3,-5), linewidth(2) + red); draw((-3,-5)--(-3,-6), linewidth(2) + red); draw((-3,-5)--(-3,-4), linewidth(2) + red); draw((-3,-4)--(-2,-4), linewidth(2) + red); draw((-2,-4)--(-2,-5), linewidth(2) + red); draw((-2,-5)--(-3,-5), linewidth(2) + red); draw((-2,-2)--(-2,-3), linewidth(2) + blue); draw((-2,-3)--(-3,-3), linewidth(2) + blue); draw((-3,-3)--(-3,-2), linewidth(2) + blue); draw((-3,-2)--(-2,-2), linewidth(2) + blue); draw((3,-6)--(2,-6), linewidth(2) + blue); draw((2,-6)--(2,-5), linewidth(2) + blue); draw((2,-5)--(3,-5), linewidth(2) + blue); draw((3,-5)--(3,-6), linewidth(2) + blue); draw((3,-5)--(2,-5), linewidth(2) + red); draw((2,-5)--(2,-4), linewidth(2) + red); draw((2,-4)--(3,-4), linewidth(2) + red); draw((3,-4)--(3,-5), linewidth(2) + red); draw((3,-3)--(2,-3), linewidth(2) + blue); draw((2,-3)--(2,-2), linewidth(2) + blue); draw((2,-2)--(3,-2), linewidth(2) + blue); draw((3,-2)--(3,-3), linewidth(2) + blue); draw((2,-6)--(1,-6), linewidth(2) + red); draw((1,-6)--(1,-5), linewidth(2) + red); draw((1,-5)--(2,-5), linewidth(2) + red); draw((2,-5)--(2,-6), linewidth(2) + red); draw((0,-6)--(-1,-6), linewidth(2) + blue); draw((-1,-6)--(-1,-5), linewidth(2) + blue); draw((-1,-5)--(0,-5), linewidth(2) + blue); draw((0,-5)--(0,-6), linewidth(2) + blue); draw((0,-3)--(-1,-3), linewidth(2) + blue); draw((-1,-3)--(-1,-2), linewidth(2) + blue); draw((-1,-2)--(0,-2), linewidth(2) + blue); draw((0,-2)--(0,-3), linewidth(2) + blue); draw((2,-3)--(1,-3), linewidth(2) + red); draw((1,-3)--(1,-2), linewidth(2) + red); draw((1,-2)--(2,-2), linewidth(2) + red); draw((2,-2)--(2,-3), linewidth(2) + red); draw((2,-4)--(1,-4), linewidth(2) + blue); draw((1,-4)--(1,-3), linewidth(2) + blue); draw((1,-3)--(2,-3), linewidth(2) + blue); draw((2,-3)--(2,-4), linewidth(2) + blue); draw((1,-4)--(0,-4), linewidth(2) + red); draw((0,-4)--(0,-3), linewidth(2) + red); draw((0,-3)--(1,-3), linewidth(2) + red); draw((1,-3)--(1,-4), linewidth(2) + red); draw((1,-5)--(0,-5), linewidth(2) + blue); draw((0,-5)--(0,-4), linewidth(2) + blue); draw((0,-4)--(1,-4), linewidth(2) + blue); draw((1,-4)--(1,-5), linewidth(2) + blue); draw((0,-5)--(-1,-5), linewidth(2) + red); draw((-1,-5)--(-1,-4), linewidth(2) + red); draw((-1,-4)--(0,-4), linewidth(2) + red); draw((0,-4)--(0,-5), linewidth(2) + red); draw((-5,-3)--(-6,-3), linewidth(2) + blue); draw((-6,-3)--(-6,-2), linewidth(2) + blue); draw((-6,-2)--(-5,-2), linewidth(2) + blue); draw((-5,-2)--(-5,-3), linewidth(2) + blue); draw((-3,-3)--(-4,-3), linewidth(2) + red); draw((-4,-3)--(-4,-2), linewidth(2) + red); draw((-4,-2)--(-3,-2), linewidth(2) + red); draw((-3,-2)--(-3,-3), linewidth(2) + red); draw((-3,-4)--(-4,-4), linewidth(2) + blue); draw((-4,-4)--(-4,-3), linewidth(2) + blue); draw((-4,-3)--(-3,-3), linewidth(2) + blue); draw((-3,-3)--(-3,-4), linewidth(2) + blue); draw((-4,-5)--(-5,-5), linewidth(2) + blue); draw((-5,-5)--(-5,-4), linewidth(2) + blue); draw((-5,-4)--(-4,-4), linewidth(2) + blue); draw((-4,-4)--(-4,-5), linewidth(2) + blue); draw((-5,-4)--(-5,-3), linewidth(2) + red); draw((-5,-3)--(-4,-3), linewidth(2) + red); draw((-4,-3)--(-4,-4), linewidth(2) + red); draw((-4,-4)--(-5,-4), linewidth(2) + red); draw((-5,-5)--(-6,-5), linewidth(2) + red); draw((-6,-5)--(-6,-4), linewidth(2) + red); draw((-6,-4)--(-5,-4), linewidth(2) + red); draw((-5,-4)--(-5,-5), linewidth(2) + red); draw((-5,-6)--(-6,-6), linewidth(2) + blue); draw((-6,-6)--(-6,-5), linewidth(2) + blue); draw((-6,-5)--(-5,-5), linewidth(2) + blue); draw((-5,-5)--(-5,-6), linewidth(2) + blue); draw((-1.7991049342473708,-4.535285403222338)--(-1.0839408493060767,-4.535285403222338), linewidth(2),EndArrow(6)); draw((-6,-4)--(-6,-3), linewidth(2)); draw((-5,-2)--(-4,-2), linewidth(2)); draw((-5,-6)--(-4,-6), linewidth(2)); draw((-2,-4)--(-2,-3), linewidth(2)); draw((-1,1)--(-1,2), linewidth(2)); draw((0,3)--(1,3), linewidth(2)); draw((3,1)--(3,2), linewidth(2)); draw((1,-1)--(0,-1), linewidth(2)); draw((0,-2)--(1,-2), linewidth(2)); draw((3,-4)--(3,-3), linewidth(2)); draw((1,-6)--(0,-6), linewidth(2)); draw((-1,-4)--(-1,-3), linewidth(2)); draw((0,1)--(0,2), linewidth(2)); draw((1,-6)--(1,-5), linewidth(2)); label("$P$",(-5.715814382242815,2.769228358696473),SE*labelscalefactor); label("$P$",(-0.6903370286012918,1.6973608112414633),SE*labelscalefactor); label("$P$",(-5.645527985688388,-3.2754017449842387),SE*labelscalefactor); label("$R$",(0.36395891971511163,-3.257830145845632),SE*labelscalefactor); label("$P$",(0.10038493263601078,-3.257830145845632),SE*labelscalefactor); label("$R$",(1.3655400706156948,0.7484944577567003),SE*labelscalefactor); label("$R$",(-3.6950804813030413,0.7133512594794869),SE*labelscalefactor); label("$R$",(-4.749376429619445,-3.257830145845632),SE*labelscalefactor); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] It is clear that the policeman can always play in that way. As he only uses $\downarrow$ and $\rightarrow$, the amount of moves must end, and the only way this can happen is if the policeman is already on the same cell as the robber, proving $b)$. We are done $\square$. I have been wondering for a while, but is it not the case that the robber can move just 9999, and the one moving 10 000 is the police man?
12.10.2020 04:41
Ozc wrote: I have been wondering for a while, but is it not the case that the robber can move just 9999, and the one moving 10 000 is the police man? Hi! No, that can't happen because the robber is the one who moves first. He will always have moved as many times or one more time as the policeman.
12.10.2020 05:02
Oh Thanks, I couldn't read from the post who starts, and I didn't realize the robber started on the upper left diagonal. I was following the statement from the iberoamerican site (https://www.oei.es/historico/oim/xviioimprob.htm), in which actually the policeman starts and the initial position of the robber is upper right from the policeman instead. Modesti wrote: Ozc wrote: I have been wondering for a while, but is it not the case that the robber can move just 9999, and the one moving 10 000 is the police man? Hi! No, that can't happen because the robber is the one who moves first. He will always have moved as many times or one more time as the policeman.