Andrey and Sasha play the game, making moves alternate. On his turn, Andrey marks on the plane an arbitrary point that has not yet been marked. After that, Sasha colors this point in one of two colors: white and black. Sasha wins if after his move it is impossible to draw a line such that all white points lie in one half-plane, while all black points lie in another half-plane with respect to this line. a) Prove that Andrey can make moves in such a way that Sasha will never win. b) Suppose that Andrey can mark only integer points on the Cartesian plane. Can Sasha guarantee himself a win regardless of Andrey's moves? (N. Naradzetski)
Problem
Source: 2019 Belarusian National Olympiad 9.8
Tags: combinatorics, Combinatorial games
04.09.2019 06:39
We'll solve both parts simultaneously. We will describe a winning strategy for Andrey under the assumption that he only plays on lattice points. Andrey's strategy proceeds in two parts. In the first part, he will start by marking the point $(0, 1)$, then $(1, 0),$ then $(2, -1)$, and so on. He terminates the first part when Sasha changes colors. In other words, Sasha chooses two different colors for $(x, 1-x)$ and $(x+1, -x)$ for some $x \in \mathbb{Z}_{\ge 0}.$ If this never happens that Sasha never wins, so WLOG it happens. Now, Andrey will proceed to the second phase. WLOG, shift the entire coordinate plane such that $(0, 1)$ and white and $(1, 0)$ is black. Note that there may be white points of the form $(-x, x+1)$ for $x \in \mathbb{N}.$ We will show Andrey how to maintain the existence of a line of positive slope through the origin, so that all white points are above it and all black points are below it. It's easy to verify that this is initially true. In the beginning, Andrey will let vector $\vec{w} = \left< 0, 1 \right>$ and $\vec{b} = \left< 1, 0 \right>.$ At each point thereafter, Andrey will mark the point corresponding to the vector $\vec{w} + \vec{b}.$ If Sasha colors this point black, then he redefines $\vec{b}$ to be the vector corresponding to this new point, while keeping $\vec{w}$ the same. Otherwise, he'll redefine $\vec{w}$ to be the vector corresponding to this point, while keeping $\vec{b}$ the same. It's then easy to verify that there always exists a desired line. $\square$
04.09.2019 09:48
Another way for a) A winning strategy for Andrey is the following: Choose the origin of the coordinate system, now w.l.o.g the colour of this point is white, Andrey keeps adding points on the $Ox$ line to the left of the previously added point till one point is black, and let $A_1$(white) and $A_2$ be the adjacent points with different colours, now Andrey adds the midpoint of $A_1A_2$, say $A_3$, if the colour in this point is black then the next point we add the midpoint of $A_1A_3$ and do the same procedure for $A_1, A_3$, if $A_3$ is black we add the midpoint of $A_3A_2$ and do the same procedure $A_3, A_2$, clearly there is always a line that divides the points by their colours. $\blacksquare$
04.09.2019 11:19
Where on the Internet I can find problems from Belarussian Math Olympiads? Tnx a lot
04.09.2019 12:54
Nowhere. The only thing I can do is to post here a link for some TST-s: https://drive.google.com/file/d/1gFtItyAq1WndwUj53JN0KH4lOnX9oSJK/view?usp=sharing
04.09.2019 13:28
And to post problems from belarusian books here
04.09.2019 13:35
If you can that would be great!!