Maths Olympiad Prep

Library / Singapore International Mathematical Olympiad Committee National Team Selection Test /6 of 8

Singapore International Mathematical Olympiad Committee National Team Selection Test

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 ∣T∣≥16|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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.