Maths Olympiad Prep

Library / /127 of 264

Number theory Difficulty 5.7 AIME, harder Prove it Romania

Denote A={1000,1001,1002,,2014}A = \{1000, 1001, 1002, \dots, 2014\}. Find the maximum number of elements of a subset of AA which contains only perfect squares pairwise relatively prime.

Solution

If nAn \in A and n=p2n = p^2, then 1000p220141000 \le p^2 \le 2014, that is 32p4432 \le p \le 44. The largest subset of AA whose elements are perfect squares is
B={322,332,342,352,362,372,382,392,402,412,422,432,442}. B = \{32^2, 33^2, 34^2, 35^2, 36^2, 37^2, 38^2, 39^2, 40^2, 41^2, 42^2, 43^2, 44^2\}.
We must choose among them the maximum number of pairwise prime numbers. Consider the partition of BB into the sets C1={322,342,362,382,402,422,442}C_1 = \{32^2, 34^2, 36^2, 38^2, 40^2, 42^2, 44^2\}, C2={332,392}C_2 = \{33^2, 39^2\}, C3={352}C_3 = \{35^2\}, C4={372}C_4 = \{37^2\}, C5={412}C_5 = \{41^2\}, C6={432}C_6 = \{43^2\}. If we choose 7 or more elements of BB, then two of them are in the same CiC_i, so they are not co-prime. So we cannot take more than 6 elements; an example is {322,332,352,372,412,432}\{32^2, 33^2, 35^2, 37^2, 41^2, 43^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.