Sticky Note Square off!

Logic Level 2

Daniel and Cody are playing a game on an infinite unit square grid. Daniel places unit square sticky notes with a letter D D , while Cody places unit square sticky notes with a letter C C . 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.

Can Daniel succeed?

Assume that both players make optimal moves.

Yes It depends No

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.

2 solutions

Garrett Clarke
Jun 15, 2015

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 \boxed{No} , 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-n,y) , ( x , y ) (x,y) , and ( x + n , y ) (x+n,y) where ( x n , y ± n ) (x-n,y\pm n) , ( x , y ± n ) (x,y\pm n) and ( x + n , y ± n ) (x+n,y\pm 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 -n side), Cody plays x , y + n ) x,y+n) . No matter where Daniel plays Cody wins the next round. If Daniel plays ( x n , y + n ) (x-n,y+n) , then Cody plays ( x + n , y + n ) (x+n,y+n) , making a square with ( x , y ) (x,y) , ( x + n , y ) (x+n,y) and ( x , y + n ) (x, y+n) . If Daniel plays ( x + n , y + n ) (x+n,y+n) , then Cody plays ( x n , y + n ) (x-n,y+n) , making a square with ( x , y ) (x,y) , ( x n , y ) (x-n,y) and ( x , y + n ) (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 ) (0,0) . We'll denote Daniel's first square (placed on move three) as ( a , b ) (a,b) . Cody's next square should be placed at ( 2 a + 2 b + 2 , 0 ) (2|a|+2|b|+2, 0) . At this point we break into three cases: Daniel plays a square at ( a + b + 1 , 0 ) (|a|+|b|+1,0) , he plays a square at ( 4 a + 4 b + 4 , 0 ) (4|a|+4|b|+4,0) , or he plays anywhere else.

Case 1: Square 2 = ( a + b + 1 , 0 ) (|a|+|b|+1,0)

Cody plays a square at ( 4 a + 4 b + 4 , 0 ) (4|a|+4|b|+4,0) . Letting x = y = n = 2 a + 2 b + 2 x=y=n=2|a|+2|b|+2 this forms a line with ( 0 , 0 ) (0,0) and ( 2 a + 2 b + 2 , 0 ) (2|a|+2|b|+2,0) in the desired form, and ( a , b ) (a,b) and ( a + b + 1 , 0 ) (|a|+|b|+1,0) are not of the form ( x n , y ± n ) (x-n,y\pm n) , ( x , y ± n ) (x,y\pm n) or ( x + n , y ± n ) (x+n,y\pm n)

Case 2: Square 2 = ( 4 a + 4 b + 4 , 0 ) (4|a|+4|b|+4,0)

Cody plays a square at ( a + b + 1 , 0 ) (|a|+|b|+1,0) . Letting x = y = n = a + b + 1 x=y=n=|a|+|b|+1 this forms a line with ( 0 , 0 ) (0,0) and ( 2 a + 2 b + 2 , 0 ) (2|a|+2|b|+2,0) in the desired form, and ( a , b ) (a,b) and ( 4 a + 4 b + 4 , 0 ) (4|a|+4|b|+4,0) are not of the form ( x n , y ± n ) (x-n,y\pm n) , ( x , y ± n ) (x,y\pm n) or ( x + n , y ± n ) (x+n,y\pm n)

Case 3: Anywhere else

We have seen that either x = y = n = a + b + 1 x=y=n=|a|+|b|+1 or x = y = n = 2 a + 2 b + 2 x=y=n=2|a|+2|b|+2 . It must be emphasized that ( x n , y ± n ) (x-n,y\pm n) , ( x , y ± n ) (x,y\pm n) are ( x + n , y ± n ) (x+n,y\pm n) are not the same squares for the two possibilities of x x , y y and n 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 x , y y and n 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.

What if Daniel places his sticky note two places above one of Cody's sticky notes on Move 5?

Daniel Liu - 5 years, 12 months ago

Log in to reply

Good point! This is one of the "initial conditions" I mentioned above. Let's say that Daniel placed it two above the left C note. Let Cody complete move 6 as planned. If Daniel places anything above Cody's string or to the side of it he loses because this leaves Daniel to make move 8 as planned. Now say Daniel in move 7 places one two spaces below one of Cody's. All Cody has to do is place one 4 to the right of his last one and he's made his string of 3, all 4 apart instead of 2! Daniel can't block the top and bottom middles in one move so we're done.

Garrett Clarke - 5 years, 12 months ago

Log in to reply

Perfect, that is the intended solution.

Daniel Liu - 5 years, 12 months ago

Yes, that works. However, as Calvin said, there is a strategy for Cody to win in 10 moves rather than 12.

Peter Byers - 4 years, 4 months ago

Log in to reply

@Peter Byers Can you add your 10 step win?

Calvin Lin Staff - 4 years, 4 months ago

You essentially have all the ideas, but your solution lacks mathematical rigor.

In move 2, why must Daniel play right next to Cody?

For the "All cody needs to do", you should also explain that Daniel cannot occupy both of the "perpendicular" squares. IE If the grid was

D
C C C
D

then Cody would be unable to win via your method.

Calvin Lin Staff - 5 years, 12 months ago

Log in to reply

Your right, my argument was a bit vague. I have edited my solution to be a bit more mathematical; this should now cover every possibility.

Garrett Clarke - 5 years, 12 months ago

Log in to reply

This looks better. The initial part of "we can play C infinitely far from D" still needs to be quantified better.

Review through your solution and try and find what the crux observation is. There is no need to split it out into so many cases. One can guarantee that Cody will win on the 10th (half) move.

Calvin Lin Staff - 5 years, 12 months ago
Brandon Saunders
Oct 5, 2015

It isn't possible because they take it in turns therefore one can always stop the other

Well, Daniel can never stop Cody, so you're argument is wrong, sorry.

Daniel Liu - 5 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...