Maths Olympiad Prep

Library / /7 of 9

Number theory Difficulty 8.1 Shortlist Prove it Singapore

A subset TT of {7,8,...,26}\{7, 8, ..., 26\} does not contain three elements whose product is a perfect square. Determine the maximum number of elements in TT.

Solution

By checking the parity of the prime factorization of all the integers in TT, we partition them into disjoint triples, whose products are all squares:
{8,13,26},{11,18,22},{14,21,24},{12,15,20},{9,16,25}. \{8, 13, 26\}, \{11, 18, 22\}, \{14, 21, 24\}, \{12, 15, 20\}, \{9, 16, 25\}.
If T16|T| \ge 16, at least one of these triples will be in TT, a contradiction.

We can easily check that the subset (obtained by strategically removing one element 88, 1818, 2424, 1212, 99 from each of the triples above):
{7,10,11,13,14,15,16,17,19,20,21,22,23,25,26} \{7, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 25, 26\}
satisfies the condition given. Thus the maximum number of elements in TT is 1515.

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.