Find the maximum value of $n$, such that there exist $n$ pairwise distinct positive numbers $x_1,x_2,\cdots,x_n$, satisfy $$x_1^2+x_2^2+\cdots+x_n^2=2017$$
Problem
Source: CSMO Grade 11 Problem 8
Tags: Perfect Squares, number theory
24.05.2018 13:36
The answer is $\fbox{16}$, which is archived by the following construction. $$(1^2+2^2+3^2+...+19^2)-(17^2+10^2+8^2) = 2017$$To prove the bound, we first prove that $n\geqslant 18$ does not work. Just notice that $$x_1^2+x_2^2+...+x_n^2\geqslant 1^2+2^2+...+18^2=2109>2017$$which is impossible. Now it suffices to eradicate the case $n=17$. By taking difference between $\{x_1,x_2,...,x_{17}\}$ and $\{1,2,...,17\}$. It suffices to prove that it's impossible to sum up the number in form $$\{a^2-b^2\mid a\in\{18,19,20,...\}, b\in\{1,2,...,17\}\}$$to get the value $2017-(1^2+2^2+...+17^2)=232$. Now we tabulate the number is this form. \begin{tabular}{c|c|c|c|c|c|c|} & 17 & 16 & 15 & 14 & 13 & 12 \\ \hline 18 & 35 & 68 & 99 & 128 & 159 & 180\\ \hline 19 & 72 & 105 & 136 & 165 & 192 & \\ \hline 20 & 111 & 144 & 175 & & & \\ \hline 21 & 152 & 185 & & & &\\ \hline 22 & 195 & & & & &\\ \hline \end{tabular}Note that the smallest entry is $35$ Moreover $232$ is not in the table as the only ways to write $232$ in form $a^2-b^2$ is $31^2-27^2 = 59^2-57^2$, so it suffices to ignore the elements greater than $232-35=197$. First, we prove that two-elements sum is impossible. There exists at least one element in the sum which is less than $116$. So we must have either $35, 68, 72, 99, 111$ in the sum. Their difference to $232$ are $197, 164, 160, 133, 121$ which are all impossible. Now for three-elements sum, observe that $35$ must be forced since otherwise the sum must be greater than $68+72+99=239$, impossible. The other two must sum to $197$. Thus one of them must be $68,72$ which by inspection is impossible. For more than four elements sum, observe that the sum is forced to be greater than $35+68+72+99>232$, which is impossible. We have exhausted all cases so we are done.
11.07.2022 11:56
l1090107005 wrote: Find the maximum value of $n$, such that there exist $n$ pairwise distinct positive numbers $x_1,x_2,\cdots,x_n$, satisfy $$x_1^2+x_2^2+\cdots+x_n^2=2017$$ actually your problem is wrong In the original piece there is no "positive"
12.08.2022 15:38
(1)If n≥18. x₁²+x₂²+...+(x_n)²≥1²+2²+...+18²=2109>2017. (2)If n=17. ∵1²+2²+...+18²-9²=2109-81>2017, ∴1, 2, ..., 9 ∈{x₁, x₂, ..., x₁₇}. Let x_i=i-8 (i=9, 10, ..., 17), then S=x₁²+x₂²+...+x₈²=1732≡0 (mod 4). If the number of odd integers is 0 or 8, it's obvious that LHS>RHS. ∴There are 4 odd integers in x₁, x₂, ..., x₈. ∵S=x₁²+x₂²+...+x₈²=1732≡4 (mod 8), ∴the 4 even integers are {10, 12, 14, 16}or{12, 14, 16, 18}. (i)If 12, 14, 16, 18 ∈{x₁, x₂, ..., x₈}. S=11²+12²+...+18²=1724≠1732, or S>1732. (ii)If 10, 12, 14, 16 ∈{x₁, x₂, ..., x₈}. The 4 odd integers x₁, x₂, x₃, x₄ ∈{11, 13, 15, 17, 19, 21}, or LHS>RHS. ∵S≡1 (mod 3) , ∴x₁²+x₂²+x₃²+x₄²≡1 (mod 3), ∴x₁²≡x₂²≡x₃²≡x₄²≡1 (mod 3). ∴x₁, x₂, x₃, x₄ ∈{11, 13, 17, 19}. ∴S=100+121+144+169+196+256+289+361≠1732. (3)n≤16. Let {x₁, x₂, ..., x₁₆}={1, 2, ..., 19}\{1, 14, 16}, then x₁²+x₂²+...+x₁₆²=2017. You can't find x₁²+x₂²=1²+2²+...+18²-2017=92. So try to find x₁²+x₂²+x₃²=1²+2²+...+19²-2017=453≡1 (mod 4). So there are one odd integer, let it be x₃. While 453≡5 (mod 8), so v₂(x₂)=1, v₁(x₁)≥2. Let x₁=4a, x₂=2b, x₃=c (b, c are odd, a≤4, b≤9, c≤18). Then 16a²+4b²+c²=453, it's not difficult to find (a, b, c).