Alice and Bob play the following game. It begins with a set of $1000$ $1\times 2$ rectangles. A move consists of choosing two rectangles (a rectangle may consist of one or several $1\times 2$ rectangles combined together) that share a common side length and combining those two rectangles into one rectangle along those sides sharing that common length. The first player who cannot make a move loses. Alice moves first. Describe a winning strategy for Bob.
Problem
Source: XVIII OlimpĂada Matemática Rioplatense (2009)
Tags: geometry, rectangle, combinatorics unsolved, combinatorics
27.07.2011 05:05
Bob should designate one piece as "long" (which will always be of the form $1 \times (2k)$) and one piece as "fat" (which will always be of the form $2 \times (2\ell+1)$). The rest of the pieces will form the "normal" pile, consisting only of $1 \times 2$. Note that the fat piece and long piece will not be able to combine with each other, while any normal pieces will be able to combine with either piece or another normal piece. (Initially, the long/fat pieces will be normal $1 \times 2$ pieces, and Alice may combine them; Bob should just replace whichever piece was previously $1 \times 2$ with one from the normal pile, and pretend that Alice actually used a normal piece.) Bob's strategy for most of the game: If Alice extends either the long piece to $1 \times (2k+2)$ or the fat piece to $2 \times (2\ell+2)$, Bob should extend the same piece Alice extended along the same dimension, with another normal piece. If Alice creates a $2 \times 2$ with two pieces from the normal pile, Bob should add it to the fat piece; If Alice creates a $1 \times 4$ with two pieces from the normal pile, Bob should add it to the long piece. This way, the fat piece's second dimension will always be odd. If, however, after Alice moves there are 3 or fewer normal pieces left and either the fat piece or the long piece is still in its original $1 \times 2$ form, then Bob should extend that piece instead. Cases: fat 2x996, long 1x2, normal 3: extend thin to 1x4, return to original strategy fat 2x1, long 1x1992, normal 3: extend fat to 2x2, return to original strategy fat 2x995, long 1x2, extra 2x2, normal 2: extend long to 1x4, add extra to fat piece fat 2x1, long 1x1990, extra 1x4, normal 2: extend fat to 2x2, add extra to long piece So, at the end Bob should end up with one fat piece and one long piece which Alice cannot combine, and he wins.