A set $A$ contains exactly $n$ integers, each of which is greater than $1$ and every of their prime factors is less than $10$. Determine the smallest $n$ such that $A$ must contain at least two distinct elements $a$ and $b$ such that $ab$ is the square of an integer.
Problem
Source: INAMO 2020 P5
Tags: pigeon hole, combinatorics, construction
14.10.2020 07:59
Wow, strange problem to appear on an olympiad. We consider the set $S=\{2^{a_1}3^{a_2}5^{a_3}7^{a_4}\mid a_1,a_2,\ldots a_4\geq 0\}$. Clearly, $A\subseteq S$. We can define any element of $S$ from a quadruplet of points $(a_1,a_2,a_3,a_4)$. If we have at least $17$ points, there are two points in $A$ with the same representation modulo $2$ (as there are only $16$ possible representations), implying that if they are $(a_1,a_2,a_3,a_4)\equiv (b_1,b_2,b_3,b_4)\pmod 2$, then \[2^{a_1+b_1}3^{a_2+b_2}5^{a_3+b_3}7^{a_4+b_4}\]is a perfect square by construction. To construct $A$ with $16$ elements, we just consider the set of quadruplets with $1\leq a_k\leq 2$ for $1\leq k\leq 4$.
14.10.2020 10:33
Consider the $2^4$ sets each is in the form of $n^2 2^a 3^b 5^c 7^d$ where $0\leq a ,b,c,d\leq 1$. Obviously, $ab$ is a perfect square if and only if $a$ and $b$ each lies in the same set (On the exam I spent a considerable amount of time proving it). The answer is $16+1=17$ by pigeonhole principle.
17.10.2020 19:36
Is the problem wrong? I think thre is no $n$ works. The answer is not $17$ since the problem is "find the smallest $n$ such that $A$ must contain exactly two distinct integers $a,b$ such that $ab$ is square. If $n=17$ we can find $A$ such there are more than exactly two distinct $a,b$ such that $ab$ is square
17.10.2020 20:06
@above Fixed it. Thanks.