Maths Olympiad Prep

Library / /25 of 397

Combinatorics Difficulty 4.7 AIME Prove it Taiwan

Is it possible to partition all natural numbers into 6 pairwise disjoint subsets A1,A2,,A6A_1, A_2, \dots, A_6, such that for any positive integers x,y,zx, y, z satisfying x+2y=5zx+2y=5z, they never all fall into the same AiA_i?

Solution

Yes, it is possible.
Let AiA_i be the set of all positive integers of the form 7m(7k+i)7^m(7k + i), where m,km,k are non-negative integers, i=1,2,3,4,5,6i = 1,2,3,4,5,6. We now show that A1,A2,A3,A4,A5,A6A_1,A_2,A_3,A_4,A_5,A_6 satisfy the conditions of the problem.

Now suppose x,y,zAix,y,z \in A_i and x+2y=5zx+2y=5z; write x,y,zx,y,z respectively as
x=7m1(7k1+i),y=7m2(7k2+i),z=7m3(7k3+i),mj,kjN{0}, x = 7^{m_1}(7k_1 + i), \quad y = 7^{m_2}(7k_2 + i), \quad z = 7^{m_3}(7k_3 + i), \quad m_j, k_j \in \mathbb{N} \cup \{0\},
and let α=min{m1,m2,m3}\alpha = \min\{m_1,m_2,m_3\}.

Dividing both sides of the equation x+2y=5zx+2y=5z by 7α7^\alpha, and then reducing modulo 7, we obtain the congruence
e1i+2e2i=5e3i,(1) e_1i + 2e_2i = 5e_3i, \quad (1)
where e1,e2,e3e_1,e_2,e_3 equal 0 or 1. But equation (1) only has the solution e1=e2=e3=0e_1 = e_2 = e_3 = 0, which is a contradiction. Therefore, positive integer solutions (x,y,z)(x,y,z) of x+2y=5zx+2y=5z can never all fall into the same AiA_i.

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