Maths Olympiad Prep

Library / /99 of 155

Combinatorics Difficulty 6.4 National olympiad Prove it Saudi Arabia

All of the numbers 1,2,3,,10000001, 2, 3, \ldots, 1000000 are initially colored black. On each move it is possible to choose the number xx (among the colored numbers) and change the color of xx and of all of the numbers that are not co-prime with xx (black into white, white into black). Is it possible to color all of the numbers white?

Solution

The answer is YES. We will prove by induction that the procedure can be applied for any positive integer nn.

The statement is true for n=1n=1. Suppose that it is also true for n=k11n=k-1 \geq 1, which means there exists a way to change every number not exceeding k1k-1 from black to white, which we call process AA.

We shall prove the statement for kk with some cases as follows:

1. If kk is not a square-free number. Put k=p1a1p2a2pvavk=p_{1}^{a_{1}} p_{2}^{a_{2}} \ldots p_{v}^{a_{v}} and k=p1p2pvk' = p_{1} p_{2} \ldots p_{v} with p1,p2,,pvp_{1}, p_{2}, \ldots, p_{v} primes. Note that the number of times the color of kk and kk' are changed are equal (since the set of integers not coprime with them are the same), then kk' can change the color if and only if kk can. So after making process AA with the sequence 1,2,,k11,2, \ldots, k-1, the number kk will change color from black to white.

2. If kk is a square-free number. In case after making process AA, number kk changes color, then we are done. Otherwise, put k=p1p2ptk=p_{1} p_{2} \ldots p_{t} and we consider process BB to select all divisors other than 11 of kk. After that, number kk will be affected 2t12^{t}-1 times and will change the color.

Denote kk' as some divisor greater than 11 of kk, and kk' has s<ts<t prime divisors. Take some number cc which is a multiple of kk' but coprime to k/kk / k'. After process AA, number cc has color white. And after process BB, the number of times the color of cc is changed is (2t1)(2ts1)=2t2ts\left(2^{t}-1\right)-\left(2^{t-s}-1\right)=2^{t}-2^{t-s} which is an even number. This implies that cc will not change color.

So in all cases, we always can find a process to change the color of all numbers from 11 to kk from black to white.

Finally, by replacing n=106n=10^{6}, the problem is solved. \square

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.