Maths Olympiad Prep

Library / /15 of 15

Combinatorics Difficulty 7.0 National olympiad Prove it Romania

Let n5n \ge 5 be an integer. Consider nn distinct points in the plane, each coloured either white or black. For each positive integer 1k<n21 \le k < \frac{n}{2}, a kk-move consists in selecting kk points and reversing their colours. Find all values of nn for which, for any eligible kk and for any initial colouring, there exists a sequence of kk-moves that turns all points into a same colour.

Solution

The problem holds for and only for nn odd.

To this end, suppose nn even. Colour exactly one point in white and the rest in black. Choose k=2k=2. After performing a 2-move, the number of points of a same colour remains odd, so a monochromatic configuration is not achievable.

Suppose nn odd. Assume kk odd. Consider an initial colouring with pp white points and npn-p black points. Let p=ks+rp = ks+r, 0r<k0 \le r < k. Perform ss kk-moves upon the white points to reach a configuration of rr white and nrn-r black points. Perform a kk-move with the rr white points and other krk-r black to obtain exactly krk-r white points. Therefore, one can obtain exactly rr or exactly krk-r white points, with only one of the numbers rr or krk-r being even, say rr.

Perform a kk-move with the r2\frac{r}{2} white points to get exactly kk white points. After another kk-move with the white points, all points turn black and we are done.

Assume kk even. Again, consider an initial colouring with pp white points and npn-p black points. One of the numbers pp or npn-p is even, say pp. In p=ks+rp = ks+r, 0r<k0 \le r < k, notice that rr is even. From this point on, proceed as in the previous case.

Want a route through all this instead of 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.