Michi’s blog » A quick python hack for a mathematical puzzle

## A quick python hack for a mathematical puzzle

• November 12th, 2011
• 4:09 pm

So, today I saw this in my Twitter feed:

«Phil Harvey wants us to partition {1,…,16} into two sets of equal size so each subset has the same sum, sum of squares and sum of cubes.» — posted by @MathsJam and retweeted @haggismaths.

Sounds implausible was my first though. My second thought was that there aren’t actually ALL that many of those: we can actually test this.

So, here’s a short collection of python lines to _do_ that testing.

import itertools allIdx = range(1,17) sets = itertools.combinations(allIdx,8) setpairs = [(list(s), [i for i in allIdx if i not in s]) for s in sets] def f((s1,s2)): return (sum(s1)-sum(s2), sum(map(lambda n: n**2, s1))-sum(map(lambda n: n**2, s2)), sum(map(lambda n: n**3, s1))-sum(map(lambda n: n**3, s2)))

 

goodsets = [ss for ss in setpairs if f(ss) == (0,0,0)] 
And back comes one single response (actually, two, because the comparison is symmetric).

[([1, 4, 6, 7, 10, 11, 13, 16], [2, 3, 5, 8, 9, 12, 14, 15]), ([2, 3, 5, 8, 9, 12, 14, 15], [1, 4, 6, 7, 10, 11, 13, 16])] 

### 7 People had this to say...

• Dan
• November 12th, 2011
• 20:44

 module Main where

 rev [] ys = ys rev (x:xs) ys = rev xs (x:ys) subset_splits :: Int -> [a] -> [([a], [a])] subset_splits n l = ss n l [] [] where ss n l rl rr | n Bool test (l1, l2) = (sum l1 == sum l2 && sum [x*x | x <- l1] == sum [x*x | x <- l2] && sum [x*x*x | x <- l1] == sum [x*x*x | x <- l2]) 

main = do putStrLn $show$ filter test \$ subset_splits 8 [1 .. 16] 

• Jan Van lent
• November 12th, 2011
• 20:50

This problem can be formulated as an integer programming problem, for example using GMPL (GLPK).

 /* partition16.mod */ /* run with: glpsol --math partition16.mod */

 param p := 3; param n := 16; set I := 1..n; set J := 0..p; var x{i in I}, binary; minimize obj: sum{i in I} i^(p+1) * x[i]; s.t. pow{j in J}: sum{i in I} i^j * x[i] = (sum{i in I} i^j)/2; solve; printf{i in I: x[i] == 1} "%d ", i; printf "\n"; printf{i in I: x[i] == 0} "%d ", i; printf "\n"; end; 

• Dan
• November 12th, 2011
• 20:51

Sorry, some of the Haskell code looked like XHTML
tags. You can see the code at
http://pastebin.com/WEv2sS96

• Anders Kaseorg
• November 12th, 2011
• 22:44

This generalizes as follows: for all n â‰¥ 0, thereâ€™s a partition {A[n], B[n]} of {1, â€¦, 2^n} such that for all 0 â‰¤ d < n, âˆ‘[a âˆˆ A[n]] a^d = âˆ‘[b âˆˆ B[n]] b^d.

Proof: By induction on n.

Base case: The statement holds vacuously for either partition of {1}.

Induction step: Given the hypothesis for {A[n], B[n]}, let A[n+1] = A[n] âˆª (B[n] + 2^n), B[n+1] = (A[n] + 2^n) âˆª B[n]. Then by the binomial theorem and the hypothesis,
âˆ‘[a âˆˆ A[n+1]] a^d
= âˆ‘[a âˆˆ A[n]] a^d + âˆ‘[b âˆˆ B[n]] (b + 2^n)^d
= âˆ‘[a âˆˆ A[n]] a^d + âˆ‘[b âˆˆ B[n]] b^d + âˆ‘[0 â‰¤ i < d] (d C i) (2^n)^(d-i) âˆ‘[b âˆˆ B[n]] b^i
= âˆ‘[a âˆˆ A[n]] a^d + âˆ‘[b âˆˆ B[n]] b^d + âˆ‘[0 â‰¤ i < d] (d C i) (2^n)^(d-i) âˆ‘[a âˆˆ A[n]] a^i
= âˆ‘[a âˆˆ A[n]] (a + 2^n)^d + âˆ‘[b âˆˆ B[n]] b^d
= âˆ‘[b âˆˆ B[n+1]] b^d

QED.

(This is a case of the Prouhetâ€“Tarryâ€“Escott problem whose solution is given by the Thueâ€“Morse sequence.)

• L S
• November 13th, 2011
• 8:53

As Richard O’Keefe says, the ultimate optimisation in a search problem is one that hard codes the answer(s)â€”i.e., one has to know when to stop with optimisations; but, here, it may still be worth observing that a lot of hard work can be avoided by summing the powers of one of the subsets, and comparing it to half the sum of the powers of the whole set.

• L S
• November 13th, 2011
• 8:54

(By the way, the sets are very nearly the congruence classes of 1 and 2 modulo 3. I wonder if that’s significant?)

• Charlie Conlon
• November 19th, 2013
• 19:19

Has anyone done it in COBOL?