$\definecolor{A}{RGB}{70,80,0}\color{A}\fbox{C4.}$ Show that for any positive integer $n \ge 3$ and some subset of $\lbrace{1, 2, . . . , n}\rbrace$ with size more than $\frac{n}2 + 1$, there exist three distinct elements $a, b, c$ in the subset such that $$\definecolor{A}{RGB}{255,70,255}\color{A} (ab)^2 + (bc)^2 + (ca)^2$$is a perfect square. Proposed by ltf0501. #1736
Problem
Source: C4 IMOC 2020
Tags: combinatorics, IMOC
Rickyminer
05.09.2020 15:54
Note that if $c=a+b$, $$ (ab)^2 + (bc)^2 + (ca)^2=(a^2+ab+b^2)^2 $$is a perfect square. The rest is routine.
Mathotsav
05.09.2020 16:09
Note that $a^2b^2+a^2(a+b)^2+b^2(a+b)^2=(a^2+ab+b^2)^2$. So if there exist three elements in the set with $a+b=c$, then $(ab)^2+(bc)^2+(ca)^2=(a^2+ab+b^2)^2$ is a square. So all we have to show is that a subset of $\{1,2,3,...n \}$ having at least $\frac{n}{2}+1$ is not sum-free. If $n$ is even, consider the $\frac{n}{2}$ pairs of the form $\{i,n+1-i \}$ and apply PHP. If instead $n$ is odd, consider the $\frac{n-1}{2}$ sets of the form $\{i,n-i \}$ for $i<n$. Note that there will be at least $\frac{n}{2}$ elements in the set which are less than $n$, so we again apply PHP and show that the set is not sum-free. Proved