Maths Olympiad Prep

Library / /16 of 31

Combinatorics Difficulty 6.6 National Olympiad Prove it Italy

Problem:

Every natural number, zero included, is colored either white or red, such 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 a red number and that the sum of two red numbers is always a red number.

Solution

Solution:

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

One is a white number: indeed, if one were red, since there exists a white number yy, we would have that y1=yy \cdot 1 = y is red by the third property, a 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 kk, nn can be written in the form n=qk+rn = qk + r with 0<r<k0 < r < k. We use induction on qq.

If q=0q = 0, nn is white by hypothesis. Assuming the hypothesis holds 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, that is, 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 obtain, by the second property, that in this case too nn must be red. Therefore the red numbers are all and only the multiples of kk. In this case both the hypotheses of the problem and the thesis are trivially verified.

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 translated into English from it; metadata (topic, difficulty) added by this project.