Browse · MathNet
Print55rd Ukrainian National Mathematical Olympiad - Fourth Round
Ukraine counting and probability
Problem
a) Andrii and Olesia both received the set of cards, on which all integer numbers from till are written. After that Olesia leaves herself some amount of cards (but not all) from her set, and the rest she puts aside. Andrii does the same. There are points on the coordinate plane, and coordinates are integer and bounded from till . Olesia paints in blue color the points whose first coordinate equals the number on one of her cards and the second coordinate is on one of Andrii's cards, and Andrii paints in blue color the points whose first coordinate equals the number on one of his cards and the second coordinate is on one of Olesia's cards (some points can be painted in both yellow and blue colors). Prove that no matter which cards Andrii and Olesia will choose they can't make all the points painted at least in one color.
b) Oxana joins Andrii and Olesia and takes all the cards that Olesia and Andrii put aside. Then they paint the coordinate plane with the following rule: Olesia paints in blue color the points, the first coordinate of which equals the number on one of her cards and the second coordinate is on one of Andrii's cards, Andrii paints in yellow color the points the first coordinate of which equals the number on one of his cards, and the second coordinate is on one of Oxana's cards, and Oxana paints in green color the points, first coordinate of which equals the number on one of her cards and the second coordinate is on one of Olesia's cards (again some points can be painted in more than one color). How do Olesia and Andrii have to choose the cards in order to paint every point from at least in one color?
b) Oxana joins Andrii and Olesia and takes all the cards that Olesia and Andrii put aside. Then they paint the coordinate plane with the following rule: Olesia paints in blue color the points, the first coordinate of which equals the number on one of her cards and the second coordinate is on one of Andrii's cards, Andrii paints in yellow color the points the first coordinate of which equals the number on one of his cards, and the second coordinate is on one of Oxana's cards, and Oxana paints in green color the points, first coordinate of which equals the number on one of her cards and the second coordinate is on one of Olesia's cards (again some points can be painted in more than one color). How do Olesia and Andrii have to choose the cards in order to paint every point from at least in one color?
Solution
a) Without loss of generality, we will consider that Olesia didn't choose the card with the number . Then the point cannot be painted. Olesia doesn't paint it because the first coordinate is , Andrii doesn't paint it because the second coordinate is .
b) If there is one number, for instance , that was not chosen by either Olesia or Andrii, then the point cannot be painted by Olesia, nor by Andrii (since the first coordinate is ), nor by Oxana, because the second coordinate is .
Let all the cards in the sets that were not chosen by Olesia and Andrii be pairwise distinct. Thus, it is obvious that every number from till will be chosen at least once. We will show that under such a condition all points will be painted.
Consider the point and possible cases.
If is not chosen by Andrii, then Olesia chose it and it goes to Oxana. If is the one Andrii also chose, then is painted by Andrii. If not, then goes to Oxana and Olesia, since Andrii didn't choose it, thus is painted by Oxana.
If was not chosen by Olesia, then Andrii and Oxana both have it. If is the one Olesia has, then is painted by Oxana; if Olesia doesn't have it, then Oxana has it and the point is painted by Andrii. This completes the proof.
b) If there is one number, for instance , that was not chosen by either Olesia or Andrii, then the point cannot be painted by Olesia, nor by Andrii (since the first coordinate is ), nor by Oxana, because the second coordinate is .
Let all the cards in the sets that were not chosen by Olesia and Andrii be pairwise distinct. Thus, it is obvious that every number from till will be chosen at least once. We will show that under such a condition all points will be painted.
Consider the point and possible cases.
If is not chosen by Andrii, then Olesia chose it and it goes to Oxana. If is the one Andrii also chose, then is painted by Andrii. If not, then goes to Oxana and Olesia, since Andrii didn't choose it, thus is painted by Oxana.
If was not chosen by Olesia, then Andrii and Oxana both have it. If is the one Olesia has, then is painted by Oxana; if Olesia doesn't have it, then Oxana has it and the point is painted by Andrii. This completes the proof.
Final answer
a) It is impossible to color all points; for any number not chosen by one player the point with both coordinates equal to that number remains uncolored. b) Olesia and Andrii must ensure that no number is omitted by both of them, i.e., their discarded sets are disjoint so that every number is chosen by at least one of them; under this condition all points are colored.
Techniques
Coloring schemes, extremal arguments