Let us call a set of positive integers nice, if its number of elements is equal to the average of all its elements. Call a number $n$ amazing, if one can partition the set $\{1,2,\ldots,n\}$ into nice subsets. a) Prove that any perfect square is amazing. b) Prove that there exist infinitely many positive integers which are not amazing.
Problem
Source: VI Caucasus Mathematical Olympiad
Tags: number theory
14.03.2021 15:56
let's say n=x^2 then 1+3+5+...+x^2-x-1=((x^2-x)/2)^2 and 2+4+6+...+x^2-x+x^2-x+1+...+x^2=((x^2+x)/2)^2 you can find these by saying t1+t2=n and t1^2 +t2^'=n.(n+1)/2 so a is proved. b) let's look at the numbers which are 2 (mod 4) then we can say t1^2+t2^2+...+tk^2=n.(n+1)/2 and t1+t2+...+tk=n. Also, ti=ti^2 (mod 2) so we add these numbers one by one so n.(n+1)/2=n (mod 2) which is contradiction.
14.03.2021 16:04
sad snipe a) Notice that$$\left(\frac{n^2(n^2+1)}{2}\right)=\left(\frac{n(n+1)}{2}\right)^2+\left(\frac{n(n-1)}{2}\right)^2$$and$$n^2=\frac{n(n+1)}{2}+\frac{n(n-1)}{2}.$$This is quite obvious that one could choose $\frac{n(n-1)}{2}$ elements from $n^2$ so that its sum is $\left(\frac{n(n-1)}{2}\right)^2$, since every sum is possible in the interval $\left[\frac{n(n-1)}{2},\frac{3n^4+2n^3+n^2+2n}{8} \right]$ and $\frac{n(n-1)}{2} \leq \left(\frac{n(n-1)}{2}\right)^2\leq \frac{3n^4+2n^3+n^2+2n}{8}$. Therefore, we can choose such $\frac{n(n-1)}{2}$ elements from $n^2$ so that its sum is $\left(\frac{n(n-1)}{2}\right)^2$ and from the two given two equations above, we are left with $\frac{n(n+1)}{2}$ elements with the sum being equal to $\left(\frac{n(n+1)}{2}\right)^2$. b) same as above, one could also use $3\pmod 4$ numbers.