Olympiad Maths Prep

Library / /16 of 16

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Czech Republic

Nela and Jane choose positive integer kk and then play a game with a 9×99 \times 9 table. Nela selects in every of her moves one empty unit square and she writes 00 to it. Jane writes 11 to some empty (unit) square in every her move. Furthermore, kk Jane's moves follow each Nela's move and Nela starts. If sum of numbers in each row and each column is odd anytime during the game, Jane wins. If girls fill out the whole table (without Jane's win), Nela wins. Find the least kk such that Jane has the winning strategy. (Michal Rolínek)

Solution

Let us show at first that Jane wins for k=3k = 3. Let us assume 3×33 \times 3 squares A1A_1, A2A_2 and A3A_3 (see the picture).

We will call the 3×33 \times 3 square *covered* if just one 11 is in each its row and column. If Jane covers squares A1A_1, A2A_2 and A3A_3 without writing to other squares, she wins, because sums in all rows and columns are odd number 11.

Figure 1

Fig. 3

It is obvious that if at most one 00 (and no 11) is written in any 3×33 \times 3 square after Nela's move, Jane can cover this square because of k=3k = 3. Jane has the following strategy: If Nela writes 00 to any uncovered square A1A_1, A2A_2 or A3A_3, Jane covers it immediately. In the opposite case Jane covers any of the uncovered 3×33 \times 3 squares. Jane thus wins after three her triples of moves.

We will show that Nela has winning strategy for k{1,2}k \in \{1, 2\}. Let us realize that if Jane has some winning move, just 88 rows and 88 columns have odd sum before Jane's move, and the winning Jane's move is writing 11 to the intersection of the only one "even" row with the only one "even" column. This implies that if Jane has winning move, this move is unique.

Now it is obvious Nela's winning strategy for k=1k = 1. If Jane has winning move after her move, Nela writes 00 to this square and Jane loses her unique chance for win. In the opposite case Nela writes 00 to some empty square. This move doesn't change parity of sums in rows and columns and Jane still hasn't winning move. This strategy allows Nela to fill out whole table without giving Jane chance to win.

In the case k=2k = 2 Nela will use the same strategy as for k=1k = 1. This strategy doesn't give Jane chance to win in her first move. In the second move Jane can't win because after that move the table contains even number of 11's which excludes possibility to be odd number 11's in every of (odd number) nine rows.

Conclusion. The least value kk, for which Jane has winning strategy, is k=3k = 3.

Looking for a route rather than 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.