Problem A. 890. (November 2024)
A. 890. Bart, Lisa and Maggie play the following game: Bart colors finitely many points red or blue on a circle such that no four colored points can be chosen on the circle such that their colors are blue-red-blue-red (the four points do not have to be consecutive). Lisa chooses finitely many of the colored points. Now Bart gives the circle (possibly rotated) to Maggie with Lisa's chosen points, however, without their colors. Finally, Maggie colors all the points of the circle to red or blue. Lisa and Maggie wins the game, if Maggie correctly guessed the colors of Bart's points. A strategy of Lisa and Maggie is called a winning strategy, if they can win the game for all possible colorings by Bart. Prove that Lisa and Maggie have a winning strategy, where Lisa chooses at most \(\displaystyle c\) points in all possible cases, and find the smallest possible value of \(\displaystyle c\).
Proposed by Dömötör Pálvölgyi, Budapest
(7 pont)
Deadline expired on December 10, 2024.
We claim that the smallest possible value of \(\displaystyle c\) is 3.
We will first prove that \(\displaystyle c=2\) is not working. Bart can color the vertices of an equilateral triangle four different ways obeying the rules, however, Lisa can only pick at most two points three different ways, which is not enough to convey four different kind of information.
Now let's show a strategy for \(\displaystyle c=3\). First observe that the condition in the problem is equivalent to being able to partition the circle into two arcs (one of them can possibly be empty) such that one only contains blue points, and the other only contains red points. Lisa's strategy is defined as follows:
- If Bart is only choosing red points, the Lisa chooses no points.
- If Bart is coloring exactly one point red, then Lisa picks the single red point.
- If Bart is coloring at least two points red, and the red points can be covered with an open semicircle, the Lisa picks the two extreme red points.
- If none of the above is the case, and there are no blue points, then Lisa picks two or three points such that they cannot be covered with an open semicircle. We will show later that this is always possible.
- Finally if there are also blue points, then Lisa picks a blue point and the two red points neighbouring the blue points. Observe that the three points chosen by Lisa form an obtuse or a right triangle.
Let Maggie's strategy be the following:
- If she receives no points, she colors the complete circle blue.
- If she receives a single points, she colors the received point red, and everything else blue.
- If she receives two points that are not opposite on the circle, then she colors these two points and the shorted arc between them red, and everythind else blue.
- If Maggie receives two opposite points on the circle or three points not contained in an open semicircle (i.e. the three points form an acute or a right triangle), then she colors the whole circle red.
- And finally if Maggie receives three points that can be covered with a closed semicircle (i.e. the three points form an obtuse triangle), then she colors the inner points of the arc that is defined by the three points and not longer than a semicircle blue, and everything else red,
The only thing remains to show is that in the fourth case Lisa can always pick three points according two her strategy, namely if the red points cannot be covered with an open semicircle, then it's possible to pick two or three of them that also cannot be covered with a semicircle. If there are only two red points, they must be opposite on the circle, so we can pick them. If there are at least three red points, consider the convex hull of the red points: this polygon most contain the center of the circle inside or on its boundary, otherwise it would be possible to draw a line that separates the center of the circle and the polygon, and this would yield an arc that is shorter than a semicircle containing the red points. Now if we partition the convex hull into triangles, one of the triangles must contain the center of the circle inside or on its boundary, and the three vertices of this triangle cannot be covered with an open semicircle.
This completes our proof.
Statistics:
21 students sent a solution. 7 points: Aravin Peter, Bodor Mátyás, Czanik Pál, Gyenes Károly, Hodossy Réka, Keresztély Zsófia, Pázmándi József Áron, Szakács Ábel, Varga Boldizsár, Vödrös Dániel László. 6 points: Wágner Márton. 4 points: 3 students. 2 points: 3 students. 1 point: 1 student. 0 point: 3 students.
Problems in Mathematics of KöMaL, November 2024