Skip to Content »

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

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

Here’s a similar haskell version:


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]

Gravatar
  • 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;

Gravatar
  • 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

Gravatar
  • 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.)

Gravatar
  • 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.

Gravatar
  • 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?)

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

Has anyone done it in COBOL?

Want your say?

* Required fields. Your e-mail address will not be published on this site

You can use the following XHTML tags:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>