2
$\begingroup$

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$.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ $8,1$ and $7,4$ $\endgroup$
    – Will Jagy
    Commented Jul 24, 2012 at 20:07
  • $\begingroup$ This is not really an appropriate question for the site (see the FAQ). Try math.stackexchange.com instead. $\endgroup$
    – Qiaochu Yuan
    Commented Jul 24, 2012 at 20:12

1 Answer 1

Reset to default
13
$\begingroup$

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$}. $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ A very cool result! $\endgroup$
    – Igor Rivin
    Commented Jul 24, 2012 at 20:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Anthony Quas
    Commented Jul 24, 2012 at 21:48
  • $\begingroup$ @Anthony, thanks for the serious treatment of the question and the very lucid answer! $\endgroup$
    – rebeccakuang
    Commented Jul 24, 2012 at 22:44
  • $\begingroup$ 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. $\endgroup$
    – Kevin O'Bryant
    Commented Jul 25, 2012 at 1:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .