, while Cody places unit square sticky notes with a letter . They take turns placing sticky notes on squares in the grid, with Daniel going first. Cody wants to have four of his sticky notes form the corners of a perfect square with sides parallel to the grid lines, while Daniel wants to prevent him from doing so.
Daniel and Cody are playing a game on an infinite unit square grid. Daniel places unit square sticky notes with a letterCan Daniel succeed?
Assume that both players make optimal moves.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
One way to prove that it's not possible to Daniel to stop Cody is to prove by construction a method in which Cody can win every time. Below is a photo of each step that Cody needs to take to win. The question says that Daniel must go first, but because they are playing on an infinite grid, Cody can play his next note infinitely far away from him, so technically my diagram begins on Cody's first move, but the 2nd move of the game.
All Cody needs to do hit a stretch of 3 in a row of equal distance from each other (as seen in move 6) which inevitably will lead to Daniel having to make the choice at move 8, but regardless of his choice he will lose. This method can be rotated and dilated based on Daniel's first few moves, but testing a few other initial conditions shows that avoiding the stretch of 3 is impossible, therefore the answer is N o , Daniel cannot succeed.
EDIT: As per requested, here is a more mathematical approach to the problem.
Our goal is for Cody to reach a point where he has three squares in a line with coordinates of the form ( x − n , y ) , ( x , y ) , and ( x + n , y ) where ( x − n , y ± n ) , ( x , y ± n ) and ( x + n , y ± n ) are empty. An example of this can be seen above in move 6 in my original solution. Daniel can't block both sides of Cody's line, so whatever side Daniel plays on (WLOG on the − n side), Cody plays x , y + n ) . No matter where Daniel plays Cody wins the next round. If Daniel plays ( x − n , y + n ) , then Cody plays ( x + n , y + n ) , making a square with ( x , y ) , ( x + n , y ) and ( x , y + n ) . If Daniel plays ( x + n , y + n ) , then Cody plays ( x − n , y + n ) , making a square with ( x , y ) , ( x − n , y ) and ( x , y + n ) . If Daniel plays anywhere else then Cody simply has his pick.
Now we show that it's always possible to get situation like what is described above. Again, we begin on move 2 because Cody can place his 1st square infinitely far away from Daniel's. We'll call Cody's first square the origin, giving it the coordinates ( 0 , 0 ) . We'll denote Daniel's first square (placed on move three) as ( a , b ) . Cody's next square should be placed at ( 2 ∣ a ∣ + 2 ∣ b ∣ + 2 , 0 ) . At this point we break into three cases: Daniel plays a square at ( ∣ a ∣ + ∣ b ∣ + 1 , 0 ) , he plays a square at ( 4 ∣ a ∣ + 4 ∣ b ∣ + 4 , 0 ) , or he plays anywhere else.
Case 1: Square 2 = ( ∣ a ∣ + ∣ b ∣ + 1 , 0 )
Cody plays a square at ( 4 ∣ a ∣ + 4 ∣ b ∣ + 4 , 0 ) . Letting x = y = n = 2 ∣ a ∣ + 2 ∣ b ∣ + 2 this forms a line with ( 0 , 0 ) and ( 2 ∣ a ∣ + 2 ∣ b ∣ + 2 , 0 ) in the desired form, and ( a , b ) and ( ∣ a ∣ + ∣ b ∣ + 1 , 0 ) are not of the form ( x − n , y ± n ) , ( x , y ± n ) or ( x + n , y ± n )
Case 2: Square 2 = ( 4 ∣ a ∣ + 4 ∣ b ∣ + 4 , 0 )
Cody plays a square at ( ∣ a ∣ + ∣ b ∣ + 1 , 0 ) . Letting x = y = n = ∣ a ∣ + ∣ b ∣ + 1 this forms a line with ( 0 , 0 ) and ( 2 ∣ a ∣ + 2 ∣ b ∣ + 2 , 0 ) in the desired form, and ( a , b ) and ( 4 ∣ a ∣ + 4 ∣ b ∣ + 4 , 0 ) are not of the form ( x − n , y ± n ) , ( x , y ± n ) or ( x + n , y ± n )
Case 3: Anywhere else
We have seen that either x = y = n = ∣ a ∣ + ∣ b ∣ + 1 or x = y = n = 2 ∣ a ∣ + 2 ∣ b ∣ + 2 . It must be emphasized that ( x − n , y ± n ) , ( x , y ± n ) are ( x + n , y ± n ) are not the same squares for the two possibilities of x , y and n . If Daniel plays on one of the squares that interfere with one of these 6 squares, then refer to the case that sets x , y and n to the other case, and vice-versa. If Daniel plays on any other square then it doesn't matter what case you choose because neither possibility is blocked.
As you can see, all three cases lead to the scenario as described above, so we're done. Daniel can't stop the line of three, therefore he can't stop Cody from winning.