Two players, Red and Blue, play in alternating turns on a 10x10 board. Blue goes first. In his turn, a player picks a row or column (not chosen by any player yet) and color all its squares with his own color. If any of these squares was already colored, the new color substitutes the old one. The game ends after 20 turns, when all rows and column were chosen. Red wins if the number of red squares in the board exceeds at least by 10 the number of blue squares; otherwise Blue wins. Determine which player has a winning strategy and describe this strategy.
Problem
Source: VII Centroamerican and Caribbean Olympiad 2005, Problem 4
Tags: geometry, geometric transformation, reflection, rectangle, combinatorics proposed, combinatorics
Saul
29.07.2005 13:07
Second player wins by reflecting first player's each move in the main diagonal. After each second player move, the bottom-left half will be antisymmetric (red reflects to blue, vice versa) to the top-right half, these both excluding the main diagonal. So without the main diagonal, the players have equal score. But the second player owns the whole main diagonal, which is 10 points.
ElChapin
20.12.2007 22:53
Basically the same with other words.(May be considered as an overkill, by haven't noticed what is mention above about the diagonal)
Winner: Red player.
Strategy: paint perpendicular to the inmediately before painting.
Let $ k$ be number of rows the Blue painted.
We reorder the board to have all, blue's at the bottom an the red's at the top, each player own a rectangle with sides $ k$ and $ 10-k$, there are two squares of sides $ k$ and $ 10-k$ being shared, but as Red goes second he owns , respectively, $ 1,2,...,k$ at each turn, squares, the same in the square with side$ 10-k$.
And so the punctuation of Blue is $ k(10-k)+ \frac{k^2-k}{2}+\frac{(10-k)^2-(10-k)}{2}$ and the punctation of Red is $ k(10-k)+\frac{k^2+k}{2}+\frac{(10-k)^2+(10-k)}{2}$, thus the difference in points in this way is always $ 10$
panamath
03.07.2012 03:14
My way of solution involves simetry as well, but I didn't use the diagonal but the line between de $4th$ and $5th$ row and the line between the $4th$ and $5th$ column, so if red plays a row , then blue w'd have to play it's respective simetric row, and with the columns blue proceeds the same... since there are 20 moves, the last move will be for blue, and this way he/she will ensure that at least the game will be tied, or blue will win by one tile
chaotic_iak
03.07.2012 09:42
The problem with that argument is that Blue starts first, not Red. Also, you didn't prove the conclusion (Blue can ensure that the game is tied or win for Blue), and also you missed the fact that Blue cannot win by one tile (the difference of tiles must be even).
panamath
13.09.2012 09:44
Ok I did a complete different problem, my bad