$a_1,a_2,...,a_{100}$ are permutation of $1,2,...,100$. $S_1=a_1, S_2=a_1+a_2,...,S_{100}=a_1+a_2+...+a_{100}$Find the maximum number of perfect squares from $S_i$
Problem
Source: IZHO 2016 p2
Tags: number theory
15.01.2016 15:01
Answer is 50.Very easy question
15.01.2016 16:44
You are wrong! Answer is 60
15.01.2016 17:11
TolibjonIsmailov1999 wrote: You are wrong! Answer is 60 CAN YOU POST YOUR SOLUTION?
17.01.2016 19:06
Of course what was considering Nomik is obvious, placing odd numbers from 1 to 99 for first 50 a's. After we can still follow this strategy by adding 204, 212, 220, 228, ...... Therefore it certainly makes more than 50.
17.01.2016 21:22
A solution is already posted here.
13.12.2021 08:10
this number is greater than 50
09.02.2022 04:02
Let $S_{1}<S_{2}< ... <S_{100}$-be the sum of numbers, $P_{1}<P_{2}<... $ be the perfect squares, where $P_{k}=m_{k}^2$. Let add $P_{0}=m_{0}^2=0$ to the sequense Since $\sum_{i=1}^{100} i= 5050<72^2$ $\to m_{k} \le71$ If $m_{k+1}=m_{k}+1$ then $P_{k+1}-P_{k}=2m_{k}+1$ so difference between consecutive terms should be odd. Since there is at most $50$ odd numbers, we get contradiction if $m_{k}\ge61$ $m_{61}=(m_{61}-m_{60})+(m_{60}-m_{59})+(m_{59}-m_{58})+...+(m_{2}-m_{1})+(m_{1}-m_{0}) \ge 50*1+2*11=72$ the maximum number of perfect squares is 60 Construction: $P_{1}=1^2 ; P_{2}=P_{1}+3=4 ;... ;P_{49}=P_{48}+97=49^2; P_{50}=P_{49}+99=50^2$ For $P_{51}; P_{52}...P_{60}$; We will use $p^2+2p+1=(p+1)^2$ $$50^2+82+62+42+18=52^2=P_{51}$$$$52^2+84+64+44+20=54^2=P_{52}$$$$54^2+86+66+46+22=56^2=P_{53}$$$$56^2+88+68+48+24=58^2=P_{54}$$$$58^2+90+70+50+26=60^2=P_{55}$$$$60^2+92+72+52+28=62^2=P_{56}$$$$62^2+94+74+54+30=64^2=P_{57}$$$$64^2+96+76+56+32=66^2=P_{58}$$$$66^2+98+78+58+34=68^2=P_{59}$$$$68^2+100+80+60+36=70^2=P_{60}$$