Maths Olympiad Prep

Track / Stage 6 / 144 of 400 #1144 of 1964

Problem 1144

National Olympiad, first round
Number theory Difficulty 6.2 Prove it

Every natural number, including zero, is colored either white or red, in such a way that:

- there is at least one white number and at least one red number;
- the sum of a white number and a red number is white;
- the product of a white number and a red number is red.

Prove that the product of two red numbers is always red and that the sum of two red numbers is always red.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Solution: Zero is a red number: indeed, if 0 were white, given that there exists a red number xx, we would have that 0+x=x0+x=x is white by the second property, contradiction.

One is a white number: indeed, if one were red, given that there exists a white number yy, we would have that y1=yy \cdots 1=y is red by the third property, contradiction.

If there are no red numbers other than zero, the thesis is trivial. Otherwise, let kk be the smallest red number greater than zero. Then every number that is not a multiple of kk is white: indeed, if nn is not a multiple of k,nk, n can be written in the form n=qk+rn=q k+r with 0<r<k0<r<k. We use induction on qq. If q=0,nq=0, n is white by assumption. Assuming the hypothesis is true for q1q-1, we have n=[(q1)k+r]+kn=[(q-1) k+r]+k, which is white by the second property.

By the third property, every multiple of kk of the form jkj \cdot k, with jj not divisible by kk, is red. Suppose now that nn is a multiple of kk of the form jkj \cdot k with j=lkj=l k divisible by kk, i.e., that nn is of the form lk2l \cdot k^{2}. From the equality k+lk2=(1+lk)kk+l \cdot k^{2}=(1+l k) \cdot k we have, by the second property, that in this case nn must also be red. Therefore, the red numbers are all and only the multiples of kk. In this case, both the assumptions of the problem and the thesis are trivially satisfied.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.