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

$\endgroup$
2
  • 4
    $\begingroup$ $8,1$ and $7,4$ $\endgroup$
    – Will Jagy
    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$ Jul 24, 2012 at 20:12

1 Answer 1

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

$\endgroup$
4
  • $\begingroup$ A very cool result! $\endgroup$
    – Igor Rivin
    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$ Jul 24, 2012 at 21:48
  • $\begingroup$ @Anthony, thanks for the serious treatment of the question and the very lucid answer! $\endgroup$ 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$ Jul 25, 2012 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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