Menu subset puzzle creation help

Question

I'm having trouble finding out the best way to create the lists of numbers for the puzzle I'm creating.

There are 2 sets of 13 integers (from 1 to 50 inclusive). Call these $A$ and $B$.
There exists exactly one 6-integer subset of $A$ and one of $B$ ($a$ and $b$) where $\sum(a) = \sum(b)$.

What I need to do is generate $A$ and $B$ where there is a unique solution (and hopefully a non-trivial one, as finding $a$ and $b$ is the goal of the solver).

Any tips on how to generate these sets (or tips on how to start generation) would be appreciated.

Answer 1

Generating all sets might be computationally infeasible, but there's something very simple you can do:

Generate sets at random, then list all of the unique sums with 6 elements. Keep in a separate list all unique sums that have been found, and the set that generated them, and stop as soon as a unique sum has been found twice.

Listing the sums for a single set should be very fast, since 13 choose 6 is quite small (1716), and a random set generates on average about 17 unique sums, so two sets will collide with the same unique sum very quickly.

Unfortunately, this seems to generate one set with only small numbers and one set with only large ones. Maybe there's some possible tinkering with the parameters that makes finding two sets with a unique hard to find solution easier. My Python 2 code is here:

from random import sample
from itertools import combinations

set_sum = {}
un_sa = {}

def uni(s):
    cnt = {}
    for x in combinations(s, 6):
        k = sum(x)
        cnt[k] = cnt.get(k,0)+1
    return [x for x in cnt if cnt[x]==1], cnt.keys()

while True:
    s = sample(range(1, 51), 13)
    u, alls = uni(s)

    fs = frozenset(s)
    fu = frozenset(alls)
    mm = min(fu)
    ma = max(fu)
    set_sum[fs] = fu
    for k in u:
        if k in un_sa:
            other = un_sa[k]
            if len(set_sum[other] & fu) == 1:
                print fs, other
                print set_sum[other], fu
                print set_sum[other] & fu
                raise SystemExit

        un_sa[k] = fs

Answer 2

You can do the following

The Prouhet-Thue-Morse sequence.

The sequence $$t = (t_n)_{n>=0}$$ has the following property. Define Assuming k=1, we can have the following set of 6 digits which will satisfy the condition above:

$$22 + 24 + 27 +28 + 31 + 33 = 165 = 23+25+26+29+30+32$$

You need to use this theorem for generating the sets from the center of the given sequence. After that complete a series with incremental order numbers for rest 7 so all should be less then the smallest no and next set should contain all 7 larger then the highest no. (Thanks to @Apep) For ex.

$$({1, 2, 3, 4, 5, 6, 7, 22, 24, 27, 28, 31, 33})\\ \text{and}\\({23, 25, 26, 29, 30, 32, 43, 44, 45, 46, 47, 48, 49, 50})$$

Hope this helps you! or might help others to solve this puzzle.

Answer 3

I'm not good at all with python but I think I can give you an idea.
Generate all the possible combinations of 13 out of 50 using itertools.combinations (https://docs.python.org/3/library/itertools.html).

Then go through all the sets of 13 and generate all the sets of 6 out of them and sum up each subset.

Remember all these sums and then check which subsets sum up to the same number and check if they come from different sets with different numbers.

That's all I have for now.