This problems had appeared here early and I solved it. But I don't remember its previous subject.

This problem was proposed in 2003 IMO Shortilist... It was also proposed for the first Moldavian TST this year.... It is a very hard one! I admit it

Shi bai eshti krutoi. Vrei sa ai mai multi posturi. (palosh) Problema data e intr-adevar nu una din cele mai ushoare. se arata ca nr de forma 4k+1 sunt cele dorite.

vetali wrote: Shi bai eshti krutoi. Vrei sa ai mai multi posturi. (palosh) Problema data e intr-adevar nu una din cele mai ushoare. se arata ca nr de forma 4k+1 sunt cele dorite. please use english language. if you do not know english, please ask your fellow users (both Romanian and Moldovian) to guide you. Thanks. The source of the problem is ISL 2003, proposed by Hojoo Lee, and also MathLinks Contest, 3rd Edition, Round 3, problem 3.

I knew that I had solved this problem early. Consider following representations n=3(n+6k²)-2(n+6k²)-6k² n=4(n+6k²)-3(n+6k²)-3k² n=9(n+6k²)-8(n+6k²)-2k² where k is arbitrary integer. It is easy to prove that one of these representations satisfies all conditions. Valentin! What is official solution for this problem?

Myth, could you please post a complete solution, because I don't get why is easy to solve the problem from ther

Leonardo! I know you is in Venezuela's IMO team. Just try to complete solution yourself. OK? Best regards

But Myth, think about those who are not qualified for IMO.... Pierre.

You want to say that you cannot complete solution?

Let me just speak out my greatest thanks to all posting ISL 2003 problems on this wonderful forum. I hope they will be of much use for me on my two remaining TSTs in the end of May. Darij

darij grinberg wrote: Let me just speak out my greatest thanks to all posting ISL 2003 problems on this wonderful forum. I hope they will be of much use for me on my two remaining TSTs in the end of May. Darij note that only problems previously proposed in other TSTs have been revealed on the forum. no other ISL problems are revealed. for example, this problem has been used in the Moldovian TSTs 2004. the other problems were either used in German TSTs, or Singaporean TSTs.

Well, I think this is mostly true, but - for instance - this geometry problem was used in the Singapore and in the German TSTs (and in the Belgian ones, if I remember correctly). But I guess this is not often the case. Darij

Excuse me. My previous solution is incorrect, because n<>4(n+6k² )-3(n+6k²)-3k². New solution. Consider following representations: (1) n=2(n+2k²)-(n+2k²)-2k² (2) n=4(n+3k²)-3(n+3k²)-3k² Let k be sufficiently large integer. It is clear 2k² and 3k² are good numbers. a) n=4l+1 then we use (1) where k is odd ==> (n+2k²)=3 (mod 4) and 2(n+2k²)=2 (mod 4). So addends are good numbers. b) n=4l+2 then we use (2) where k is even ==> (n+3k²)=2 (mod 4) and 3(n+3k²)=2 (mod 4). c) n=4l+3 then we use (1) where k is even ==> (n+2k²)=3 (mod 4) and 2(n+2k²)=2 (mod 4) d) n=4^rt then we apply 1), 2) or 3) for t and multiply addends by 4^r.

For mod $4$ reasons, we see that the integer must be $3 \mod 4$. For any integer $i \equiv 3 \mod 4$, let $S$ denote the set of primes $p_i$ such that $i$ is not a quadratic residue modulo $p_i$. If I assume $|S|$ is infinite, then the question is trivial, because (for $p_i \in S$, $p_i > |i|$) $$ \displaystyle (a,b,c) = \{-p( \frac{ i + p^2}{2} + p), -p(2+p), ( \frac{ i + p^2}{2} + p)(2+p) \} $$satisfies the condition of the question, so all such $i$ works.

First, note the even integers obviously don't work since they can't be the sum of three odd integers. In addition, numbers that are $1 \mod 4$ don't work either because if three numbers $a,b,c$ multiply to a perfect square, we must have $(a,b,c) \equiv (1,1,1),(1,3,3) \mod 4$, up to permutation, both sets which have sums that are $3 \mod 4$. Now we will prove that all numbers $3 \mod 4$ work. Write $s=(p_1)^{e_1}(p_2)^{e_2}...(p_k)^{e_k}$. Fixing $s$, we choose a prime $p \equiv 3 \mod 4$, $p \equiv 1 \mod s$, $p \equiv -2-r \mod r^2$, where $r$ is a large prime not dividing $s$ by CRT and Dirichlet. We claim that the construction $(a,b,c) = (-p( \frac{s + p^2}{2} + p), -p(2+p), ( \frac{s + p^2}{2} + p)(2+p))$ satisfies the condition of the question for sufficiently large $p$. To show this, note that if the first one were a perfect square absolute value, $p|s$, impossible for large p. Therefore, the third one must be a perfect square. Let $q_1,q_2,...q_k$ denote the primes with odd exponent in the factorization of $p+2$. Then $q_i|s$ for all $1 \leq i \leq k$. But $p+2 \equiv 3 \mod s$, so the only possibility is the $q_i=3$. However, $q_i=r$ for some $i$ and since $r$ was arbitrarily large, we get a contradiction.

Clearly, no even integer can be expressed as the sum of three odd integers. If $n\equiv 1\bmod{4}$ and $n=a+b+c,$ since $a\cdot b\cdot c$ is an odd perfect square, then $(a,b,c)$ reduces to $(1,1,1)$ or $(1,3,3)$ mod $4$ which both add up to some $m\equiv 3\bmod{4},$ so we get a contradiction. If $n\equiv 3\bmod{4},$ we can, indeed, write it in infinitely many ways! Consider the triple $(x,y,z)=(p+2f(n),p+2g(n),-p)$ for some prime $p>2.$ Then, let $(a,b,c)=(xy,yz,zx).$ Clearly, $abc$ is indeed the square of an odd integer. It boils down to finding some $f$ and $g$ such that $a,b$ and $c$ are good and the following identity holds\[(p+2f(n))(p+2g(n))-p(p+2f(n))-p(p+2g(n))=n.\]Notice that the latter gives us $4f(n)g(n)=n+p^2.$ By taking $p$ to be greater than $n, \ p\nmid n+p^2$ so $p\nmid f(n)$ or $g(n)$ so $-p(p+2g(n))$ and $-p(p+2f(n))$ are good, since the exponents of $p$ in their prime decompositions is $1.$ It remains to find $f$ and $g$ such that: \[f(n)\cdot g(n)=\frac{n+p^2}{4}\text{ and }(p+2f(n))(p+2g(n))\neq \pm k^2.\]Without complicating ourselves too much, we can choose $g(x)= 1$ and $f(x)=(x+p^2)/4.$ Simply choose some prime $p$ such that $p+2\equiv q\bmod{q^2}$ for some other prime $q>x.$ It then follows that $\nu_q((p+2f(n))(p+2g(n)))=1$ so that number is good as well, finishing the proof.

If $m=a+b+c$ where $a$, $b$, $c$ multiply to a number $\equiv 1\pmod 4$ then $(a,b,c)\pmod 4$ is $(1,1,1)$ or $(1,3,3)$ and therefore $m\equiv 3\pmod 4$. Let $m=4k-1$ then consider the following construction: Let $4k-1=xy+yz+zx$, where $x$, $y$, $z$ are odd numbers. It just remains to satisfy the equality and make sure that $xy$, $yz$, $zx$ are not perfect squares or the negations of them. Let $x=2p+1$, $y=-2p+1$, and $z=2p^2+2k-1$. Then \[xy+yz+zx=2z+xy=4k-1\]Note that $xy=1-4p^2$ is always good except at $0$. We need to show that infinitely many times, $(2p^2+2k-1)(2p+1)$ and $(2p^2+2k-1)(2p-1)$ are good. Choose some large prime $q$ and there are infinitely many $p$ such that $\nu_q(2p-1)=1$. In this case, $q\mid 4p^2+4k-2$ so $q\mid 4k-1$, contradicting largeness. We can impose a similar restriction to $2p+1$ by CLT and we are done.