Maths Olympiad Prep

Track / Stage 6 / 119 of 400 #1119 of 1964

Problem 1119

National olympiad, first round
Number theory Difficulty 6.2 Prove it

2. 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.

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 and solution reproduced as published; topic, difficulty and ordering added by this site.