Maths Olympiad Prep

Library / /39 of 39

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Ukraine

In a table n×nn \times n two players fill the lines one by one with numbers "+1" and "1". At first the first player fills the first line. Then second player -- second line, then first player fills third line. Then second -- forth line etc. In the end of filling lines, first player gets 1 point for every line or column, in which product of numbers is positive, in another way, this point gets another player. Each of them try to collect points as much as possible. In a melting way of game, how much points each of them can collect?

Solution

Answer: By even kk the first player collects (3k+2)(3k + 2), the second kk; by the odd kk the first (3k+1)(3k + 1), second (k+1)(k + 1).

Let n=2kn = 2k.

In the beginning we can look into such a strategy for every player. The first player fills numbers in arbitrary way. In this way he collects kk points. The second -- in this way to last line collects (k1)(k-1) points, but in the last line he fills numbers to win in every column. In this way he collects 2k+(k1)=3k12k + (k-1) = 3k-1 points. Only we have to find out who with this strategy will win in last line. As product of all numbers in table is "+1" because product in all columns is 11 and there is even quantity. Odd lines have product "+1"; in this way the product of all "even" lines is "+1". There are kk pieces.

In this way with even kk the product of last line will be 11 too. Definitely first player collects at least kk points, and second -- 3k3k. In attempt of changing strategy, each of them can only reduce his result, because the opponent can use this for improvement of his result. In the way of odd kk the product of last line must be "+1", i.e. the first player will win. The final result in this way will be: first -- (k+1)(k+1), second -- (3k1)(3k-1). Whether the second can collect more? In way of another strategy, first player will collect his kk points for the lines. If the second loses only one column or line, he would collect no more than (3k1)(3k-1). But he can't win all of them, in consequence of valuation mentioned here. The first can't collect more than (k+1)(k+1), because the second can collect (3k1)(3k-1) at least.

Let n=2k+1n = 2k + 1.

The strategy remains here, but only in result of odd size of the table, the last move does the first player. In this way he collects his points for all (2k+1)(2k+1) columns and kk lines, without last. The second wins his kk columns. We only have to check who will win in the last line with these strategies. The product of columns of all numbers is "+1" -- all of them positive. The product of all lines, except last is (1)k(-1)^k. That's why with even kk the first wins the last line too, but with odd -- the second wins. Thereby answer is: in the way of paired kk the first collects (3k+2)(3k+2), the second -- kk; with odd kk, the first -- (3k+1)(3k+1), the second -- (k+1)(k+1).

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.