Browse · MathNet
PrintThe Problems of Ukrainian Authors
Ukraine counting and probability
Problem
In a table 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 the first player collects , the second ; by the odd the first , second .
Let .
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 points. The second -- in this way to last line collects points, but in the last line he fills numbers to win in every column. In this way he collects 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 and there is even quantity. Odd lines have product "+1"; in this way the product of all "even" lines is "+1". There are pieces.
In this way with even the product of last line will be too. Definitely first player collects at least points, and second -- . 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 the product of last line must be "+1", i.e. the first player will win. The final result in this way will be: first -- , second -- . Whether the second can collect more? In way of another strategy, first player will collect his points for the lines. If the second loses only one column or line, he would collect no more than . But he can't win all of them, in consequence of valuation mentioned here. The first can't collect more than , because the second can collect at least.
Let .
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 columns and lines, without last. The second wins his 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 . That's why with even the first wins the last line too, but with odd -- the second wins. Thereby answer is: in the way of paired the first collects , the second -- ; with odd , the first -- , the second -- .
Let .
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 points. The second -- in this way to last line collects points, but in the last line he fills numbers to win in every column. In this way he collects 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 and there is even quantity. Odd lines have product "+1"; in this way the product of all "even" lines is "+1". There are pieces.
In this way with even the product of last line will be too. Definitely first player collects at least points, and second -- . 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 the product of last line must be "+1", i.e. the first player will win. The final result in this way will be: first -- , second -- . Whether the second can collect more? In way of another strategy, first player will collect his points for the lines. If the second loses only one column or line, he would collect no more than . But he can't win all of them, in consequence of valuation mentioned here. The first can't collect more than , because the second can collect at least.
Let .
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 columns and lines, without last. The second wins his 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 . That's why with even the first wins the last line too, but with odd -- the second wins. Thereby answer is: in the way of paired the first collects , the second -- ; with odd , the first -- , the second -- .
Final answer
Let n be the board size. The optimal scores are: - If n ≡ 0 (mod 4): first player n/2, second player 3n/2. - If n ≡ 1 (mod 4): first player (3n + 1)/2, second player (n − 1)/2. - If n ≡ 2 (mod 4): first player n/2 + 1, second player 3n/2 − 1. - If n ≡ 3 (mod 4): first player (3n − 1)/2, second player (n + 1)/2. Equivalently, writing n = 2k: - If n = 2k with k even: first k, second 3k; if k odd: first k + 1, second 3k − 1. And for n = 2k + 1: - If k even: first 3k + 2, second k; if k odd: first 3k + 1, second k + 1.
Techniques
Games / greedy algorithmsInvariants / monovariants