Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is it possible for two different $n$-element sets, each of which consists of $n$ unique positive integers (they can appear in both sets, though) to have the same sum when the squares of their elements are added?

Edit: For obvious reasons, I'm not considering the case $n=1$.

share|improve this question
4  
$8,1$ and $7,4$ –  Will Jagy Jul 24 '12 at 20:07
    
This is not really an appropriate question for the site (see the FAQ). Try math.stackexchange.com instead. –  Qiaochu Yuan Jul 24 '12 at 20:12
add comment

1 Answer 1

up vote 13 down vote accepted

Yes. One way to see this is that there are more $n$-element subsets with terms up to $N$ than there are possible sums of squares, giving an answer by the pigeonhole principle.

A more beautiful answer was given by Prouhet in the 1850's, who exhibited for each $n$ an explicitly-defined pair of sets $A$ and $B$ of size $2^n$ such that $$\sum_{a\in A}a^k=\sum_{b\in B}b^k\text{ for each $1\le k\le n$}. $$

share|improve this answer
    
A very cool result! –  Igor Rivin Jul 24 '12 at 20:33
1  
Apparently it's well known to the French as the subsets come from the Morse sequence, so that Prouhet discovered the Morse sequence 50 years before Thue did, which in turn was 15 years before Morse did! I think the proof of this is actually a nice non-trivial, but non-impossible exercise in induction. –  Anthony Quas Jul 24 '12 at 21:48
    
@Anthony, thanks for the serious treatment of the question and the very lucid answer! –  rebeccakuang Jul 24 '12 at 22:44
    
If you include 0, there are other interesting families of solutions: $3^2+4^2=0^2+5^2$, $10^2+11^2+12^2=0^2+13^2+14^2$, $21^2+22^2+23^2+24^2 = 0^2 + 25^2+26^2+27^2$, and so on. The pattern is left to the reader. –  Kevin O'Bryant Jul 25 '12 at 1:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.