Competition problem — Combinatorics

Library / /15 of 18

Combinatorics Difficulty 6.6 National olympiad Prove it Ukraine

a) Andrii and Olesia both received the set of cards, on which all integer numbers from $1$ till $2015$ 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 $2015^2$ points on the coordinate plane, and coordinates are integer and bounded from $1$ till $2015$ . 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 $2015^2$ 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 $2015^2$ at least in one color?

Solution

a) Without loss of generality, we will consider that Olesia didn't choose the card with the number $a$ . Then the point $(a, a)$ cannot be painted. Olesia doesn't paint it because the first coordinate is $a$ , Andrii doesn't paint it because the second coordinate is $a$ .

b) If there is one number, for instance $1$ , that was not chosen by either Olesia or Andrii, then the point $(1, 1)$ cannot be painted by Olesia, nor by Andrii (since the first coordinate is $1$ ), nor by Oxana, because the second coordinate is $1$ .

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 $1$ till $2015$ will be chosen at least once. We will show that under such a condition all points will be painted.

Consider the point $(a, b)$ and possible cases.

If $b$ is not chosen by Andrii, then Olesia chose it and it goes to Oxana. If $a$ is the one Andrii also chose, then $(a, b)$ is painted by Andrii. If not, then $a$ goes to Oxana and Olesia, since Andrii didn't choose it, thus $(a, b)$ is painted by Oxana.

If $a$ was not chosen by Olesia, then Andrii and Oxana both have it. If $b$ is the one Olesia has, then $(a, b)$ is painted by Oxana; if Olesia doesn't have it, then Oxana has it and the point $(a, b)$ is painted by Andrii. This completes the proof.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.