Number theoryDifficulty 7.4National Olympiad, round 2Prove itIndia
Let S be a finite set of positive integers. Assume that there are precisely 2023 ordered pairs (x,y) in S×S so that the product xy is a perfect square. Prove that one can find at least four distinct elements in S so that none of their pairwise products is a perfect square.
Note: As an example, if S={1,2,4}, there are exactly five such ordered pairs: (1,1), (1,4), (2,2), (4,1), and (4,4).
Solution
Let S be a finite set of positive integers such that there are exactly 2023 ordered pairs (x,y)∈S×S with xy a perfect square.
Let us analyze the structure of S.
For any x,y∈S, xy is a perfect square if and only if the product of their squarefree parts is a square. For each x∈S, write x=dx2sx, where sx is squarefree. Then xy is a perfect square if and only if sxsy is a square, i.e., sx=sy.
Thus, for each t (squarefree), let St={x∈S:sx=t}. For x∈St and y∈St, xy is a perfect square. For x∈St, y∈St′ with t=t′, xy is not a perfect square.
Let ai=∣Sti∣ for the distinct squarefree parts t1,…,tk that appear in S. Then the total number of ordered pairs (x,y) with xy a perfect square is ∑i=1kai2=2023.
We are to show that S contains at least four distinct elements such that none of their pairwise products is a perfect square. That is, we need to find four elements with distinct squarefree parts.
Suppose, for contradiction, that there do not exist four such elements. Then the number of distinct squarefree parts k≤3.
Let us consider all possible values of k.
Case 1: k=1. Then S consists of numbers with the same squarefree part, so a1=n, n2=2023, but 2023 is not a perfect square. Contradiction.
Case 2: k=2. Then a1+a2=n, a12+a22=2023. Try all possible integer solutions: Let a1=m, a2=n−m. Then m2+(n−m)2=2023. But m2+(n−m)2=2m2−2nm+n2=2023. But n=a1+a2≤2023+2023<90. Try small values: Let a1=a2=t, then 2t2=2023⟹t2=1011.5, not integer. Try a1=t, a2=t+1: t2+(t+1)2=2t2+2t+1=2023⟹2t2+2t−2022=0⟹t2+t−1011=0. Discriminant: 1+4044=4045, not a perfect square. Try a1=t, a2=t+2: t2+(t+2)2=t2+t2+4t+4=2t2+4t+4=2023⟹2t2+4t−2019=0. t2+2t−1009.5=0. No integer solution. Try a1=44, a2=1: 442+12=1936+1=1937. Try a1=45, a2=2: 2025+4=2029. Try a1=44, a2=5: 1936+25=1961. Try a1=45, a2=7: 2025+49=2074. Try a1=40, a2=13: 1600+169=1769. Try a1=42, a2=17: 1764+289=2053. Try a1=43, a2=14: 1849+196=2045. Try a1=41, a2=10: 1681+100=1781. Try a1=45, a2=14: 2025+196=2221. So, no integer solution for k=2.
So, there is no solution for k=3 with positive integers a1,a2,a3.
Therefore, the only possibility is k≥4.
Thus, there are at least four distinct squarefree parts among the elements of S. Pick one element from each of four different Sti, say x1,x2,x3,x4 with sxi all distinct. Then for any i=j, xixj is not a perfect square, since sxi=sxj.
Therefore, there exist at least four distinct elements in S such that none of their pairwise products is a perfect square, as desired.
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.