Lesson 6

We conclude this section by proving a bit more involved result.

Theorem. For any set of thirty seven-digit numbers, there are two disjoint non-empty subsets with the same sum.

A more formal statement looks like this. Let \(S\) be a set of thirty seven-digit numbers: \[S \subseteq \{1000000, 1000001, \dotsc, 9999999\}\] and \(|S|=30\). Then there will be non-empty sets \(A,B \subseteq S\) such that \(A \cap B = \varnothing\) and \(\sum_{a \in A}a=\sum_{b \in B}b\).

For example, for the set \(S=\{7, 31, 3, 12, 5, 14, 20\}\), such subsets would be: \(A=\{7, 3, 12, 14\}\) and \(B=\{31, 5\}\).

When there are not seven, but thirty numbers, and the numbers themselves are larger, it becomes more difficult to find such subsets. Here, for example, are thirty such numbers:

from random import randint, seed

seed(14)

for i in range(30):
    print(randint(10 ** 6, 10 ** 7 - 1), end=' ')
    if i % 6 == 5:
        print()

2792285 9843470 5142886 5548558 5291201 5882438 
2218459 8545410 6083294 8828556 7655079 7607029 
2986415 5421072 4745783 6295863 7006791 5368826 
7051040 9661551 3511608 3701978 5619271 3767372 
1177927 2173344 3064039 6655032 1466196 2395998