Maths Olympiad Prep

Library / /33 of 39

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Croatia

Prove that it is possible to colour each positive integer with one of three colours so that the following conditions are satisfied:
i) For each nN0n \in \mathbb{N}_0, all positive integers xx such that 2nx<2n+12^n \le x < 2^{n+1} have the same colour.
ii) There are no positive integers xx, yy and zz of the same colour (except x=y=z=2x = y = z = 2) such that x+y=z2x+y=z^2. (B. Green, S. Lindqvist, arXiv:1608.08374)

Solution

Let cnc_n denote the colour of positive integers xx such that 2nx<2n+12^n \le x < 2^{n+1}. We will determine colours cnc_n inductively. First, let us choose c0c_0, c1c_1 and c2c_2 to be three different colours. Next, for each n3n \ge 3 let cnc_n be the colour different from cn/2c_{\lfloor n/2 \rfloor} and cn/2+1c_{\lfloor n/2 \rfloor+1}. Note that this is well-defined since n/2+1<n\lfloor n/2 \rfloor + 1 < n for all n3n \ge 3.
By construction condition i) holds. Let us prove that condition ii) also holds. Let xx, yy and zz be positive integers of the same colour such that x+y=z2x + y = z^2. Without loss of generality we may assume that xyx \le y. Let nn be an integer such that 2ny<2n+12^n \le y < 2^{n+1}. Then we obviously have
2n<x+y<2n+2, 2^n < x + y < 2^{n+2},
and hence 2n/2<z<2(n+2)/22^{n/2} < z < 2^{(n+2)/2}. It follows that 2n/2<z<2n/2+22^{\lfloor n/2 \rfloor} < z < 2^{\lfloor n/2 \rfloor+2}. Since yy and zz have the same colour, by construction it follows that n2n \le 2. From here we conclude xy<8x \le y < 8 and z=2z = 2 or 33. Direct verification shows that the only possibility is x=y=z=2x = y = z = 2.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.