Maths Olympiad Prep

Library / /68 of 92

Combinatorics Difficulty 6.9 National olympiad Prove it Iran

Arash and Babak play the following game on a 1400×14011400 \times 1401 table. Starting with Arash, he in his turns colors kk number of LL-shaped trominos on the table (rotation and reflection are allowed). Also, Babak in his turns colors one 2×22 \times 2 square from the table. Every cell of the table can be colored at most once and a player who can not color the cells in his turn will lose. Find all values of kk for which Arash has a winning strategy.

Solution

We claim that Arash has a winning strategy if and only if k1400×14013=1400×467k \le \frac{1400 \times 1401}{3} = 1400 \times 467.

First of all, it is obvious if k>1400×467k > 1400 \times 467, then Arash can not color kk trominos in his first turn and he will lose. Indeed, there are not kk disjoint trominos in the table.

Next, we shall prove that for every k1400×467k \le 1400 \times 467, Arash has a winning strategy. We can partition the table into 700×467700 \times 467 number of 2×32 \times 3 rectangles (intersection of two consecutive columns and three consecutive rows). We count the rectangles in such a way that the rectangles filling the left columns have numbers 1,2,,4671, 2, \ldots, 467 (from top to bottom), then the rectangles filling the third and fourth column have numbers 468,469,,934468, 469, \ldots, 934, etc. We consider two different trominos in each 2×32 \times 3 table, as in the figure below.

Figure 1

Now if k700×467k \ge 700 \times 467, Arash will color the trominos of type 1 in all the rectangles and then k=k700×467k' = k - 700 \times 467 trominos of type 2 in rectangles of numbers 1,2,,k1, 2, \ldots, k'. It is easy to find that after Arash's turn, every 2×22 \times 2 square has a colored cell. So, Babak can not color any 2×22 \times 2 square in his turn and Arash will win.

If k700×467k \le 700 \times 467, Arash in his first turn colors the trominos of type 1 in rectangles 1,2,,k1, 2, \ldots, k. For the next turns, suppose that Babak has filled some square and now this is Arash's turn. If he can find kk disjoint trominos not intersecting rectangles 1,2,,k1, 2, \ldots, k, he will color them. In the case that there is not kk disjoint trominos, let kk' be the maximal number such trominos (k<kk' < k). Now, he will color kk' trominos without intersection with rectangles 1,2,,k1, 2, \ldots, k, and also color kkk - k' trominos in rectangles 1,2,,kk1, 2, \ldots, k - k'. After this step, there would be no uncolored 2×22 \times 2 square left in the table and so Babak will lose the game. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.