Paper Snake
Logic; Difficulty: easy
Can you win the game of Paper Snake?
This is an easy yet interesting logic puzzle that was sent to me:
You are playing the two player game of Paper Snake against an opponent: A rectangular piece of paper is marked as a 13 X 19 grid of squares as shown above. You and your opponent alternate taking turns. Each player on their turn has to make a single straight cut all the way along a chosen line of the grid—no stopping halfway along a line or changing directions. Consequently, a turn results in one more rectangular/square piece of paper. After a cut, it’s the next player’s turn to make a single cut on any of the available rectangular pieces of paper.
If after making a cut, the available pieces can be reassembled into a single long row, the Snake, (of 13 X 19 = 247 squares), the person making the last cut wins.
Note that this doesn’t necessarily mean that we need to have 247 separate squares. For example, if it so happens that the rectangular paper was cut into 13 slices, each containing 19 squares, then the resulting 13 slices can be chained to form a single row resulting in a win for the person making the last 13th cut.
To guarantee your winning this game, will you go first or second and what strategy will you follow?
*spoiler alert* solution and answer follow below
Solution
The solution is easily understood if we first consider a grid with at least one even side (or even number of squares in the grid)—say, 4 X 7. Now in this case we can see that we win if we go first. All we have to do is make a cut on the even side creating two identical 2X7 pieces for the opponent. From now on, what ever the opponent does to any piece can be mirrored by us on an identical piece. This implies that the final first winning cut cannot be made by the opponent—because that cut would be needed on the other identical piece as well!
The solution for the given 13 X 19 grid now easily follows: Let your opponent make the first cut. This cut HAS to result in one grid with even squares and another with odd squares. Now on your turn, just make a cut on the rectangle with even number of squares splitting it into two identical rectangles. There are three rectangles now: two identical and one with an odd number of squares. If your opponent cuts one of the identical grids, you simply mirror the move on the other one. If they cut the grid with odd number of squares, you again take the piece with even squares and split it into two identical pieces.
Once again, by following this process, you are guaranteed that the opponent cannot make a Snake cut.