12 August 2011

A puzzle about splitting up numbers into groups

A puzzle from David Radcliffe: "Split {1,2,...,16} into two groups of the same size having equal sums, equal sums of squares, and equal sums of cubes."

Solution: one group is A, D, E, G, J, K, M, P; the other is B, C, E, H, I, L, N, O. (I've replaced each number with the corresponding letter of the English alphabet to obscure things a bit.)

Here's how I found this. It's often useful to look at cubes mod 9, because any cube of an integer is either a multiple of 9, one less than a multiple of 9, or one more than a multiple of 9. These cases correspond to the integer itself being a multiple of 3, one less than a multiple of 3, or one more than a multiple of 3. So 13 + 23 + 33 is a multiple of 9; so are 43 + 53 + 63, ..., 133 + 143 + 153. Since 163 is one more than a multiple of 9, so is the sum of the first sixteen cubes, which we'll call N.

We want to find eight integers in 1, ..., 16 that have sum of cubes equal to N/2. Now, if N is congruent to 1 mod 9, then N/2 is congruent to 5 mod 9. This means it's relatively far from a multiple of 9, so a lot of the numbers that are one more than a multiple of 9 are going to have to go into the same group. In particular, each group must contain either five more 1 mod 3 than 2 mod 3 integers, or four more 1 mod 3 than 2 mod 3 integers. Keeping in mind the limited supplies -- we only have six integers in our set congruent to 1 mod 3, and five each congruent to 0 and 2 mod 3, the only possible groups are:







≅ 0 (mod 3)≅ 1 (mod 3)≅ 2 (mod 3)
350
161
404
215

Furthermore we either have a group of the type given in the first row and one of the type given in the fourth row, or one of the second-row type and one of the third-row type, in order to meet the supply restrictions.

But it's not possible to have a group of the first-row type and a group of the fourth-row type. Let's consider a group of the fourth-row type -- that is, it has two multiples of three, one number that's one more than a multiple of three, and five that are one less than a multiple of three. The five that are one less than a multiple of three must be 2, 5, 8, 11, and 14. The square of each of these is one more than a multiple of three, so 22 + 52 + 82 + 112 + 142 is congruent to 2 mod 3. Call the other three members of this group x, y, and z. From the table above, two of these are multiples of 3.

But the square of every integer is either 0 mod 3 (if it's a multiple of 3) or 1 mod 3 (if it's not a multiple of 3) and so the sum of the first sixteen squares is 2 mod 3. So each group must have sum of squares congruent to 1 mod 3. The five integers that we've already put in the group have squares summing to 2 mod 3; thus x2 + y2 + z2 is also 2 mod 3, contradicting the fact that exactly one of x, y, and z is not a multiple of 3.

So we must have groups of the type in the second row and of the type in the third row. Let's look at the group of the second-row type. It contains all six integers in {1, 2, ..., 16} congruent to 1 mod 3 -- that's 1, 4, 7, 10, 13, and 16. By symmetry the other two elements -- call them t and u -- must sum to 17. Furthermore the sum of the first 16 squares is (16)(16+1)(2×16+1)/6 = 1496; so the sums of the squares in each group must be 1496/2 = 748. 12+42+72+102+132+162 = 591 and so we must have t2 + u2 = 748 - 591 = 157. So we need two integers that sum to 17, with squares summing to 157; solve the quadratic t2 + (17-t)2 = 157 to get t = 6 or t = 11, and correspondingly u = 11 or u = 6.

So if there's any way at all to do what we were asked, it's with one group being 1, 4, 6, 7, 10, 11, 13, 16 -- and this checks out.

Of course, it would be trivial to write a program to check this...

5 comments:

Anonymous said...

In case you weren't aware, the pattern of the two sets follows the Thue-Morse sequence. See pages 4--6 of the following PDF: http://www.math.uga.edu/olympiad/10/teacher-team10.pdf

Michael Lugo said...

In fact, Rex, I didn't know that. Thanks!

Jeffrey Shallit said...

This is the "Tarry-Escott" problem, also known as a "multigrade".

Prouhet proved that your solution, based on Thue-Morse, works in general, back in 1851.

"Card Colm" Mulcahy said...

For a card trick application (with statistical overtones!) see:

http://www.maa.org/columns/colm/cardcolm200712.html

Also see A135419 at http://oeis.org/

Array read by rows, showing the ways of splitting the numbers from 1 to 16 into two groups so that the numbers in each group have the same sum (68) and the same sum of squares (748)

http://cardcolm.blogspot.com

David said...

If {a_n} is any sequence of complex numbers such that sum |a_n| < infinity, then

sum (-1)^{w(n)} a_n =
sum (-1)^{w(n)} (a_{2n} - a_{2n+1})

where w(n) is the sum of the binary digits of n.

It follows (by induction on k) that if p is a polynomial function of degree less than k, then

sum [n=0 to 2^k - 1] (-1)^{w(n)} p(n) = 0.

This solves the puzzle, but I wonder if there are other nice applications of this identity.