2
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ But there is a trivial solution. 1-13 and 1-6 plus 44-50. $\endgroup$ – paparazzo Aug 8 '17 at 19:49
  • $\begingroup$ That makes a terrible puzzle though :) It's why I'm trying to find a way to generate a non-trivial subset. $\endgroup$ – Aranlyde Aug 8 '17 at 19:58
  • $\begingroup$ The fact there is a trivial solution means it may not be a very good puzzle. $\endgroup$ – paparazzo Aug 8 '17 at 20:01
  • $\begingroup$ The eventual puzzle was never intended to be finding any solution, rather finding a specific one -- the solver would be given $A$ and $B$ and tasked with finding $a$ and $b$. The question was my asking for construction help. $\endgroup$ – Aranlyde Aug 8 '17 at 20:22
1
$\begingroup$

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
|improve this answer
$\endgroup$
  • $\begingroup$ I've just tried this. The problem is that the unique sums tend to happen only at the extremes, i.e. very low or very high totals. There is a large middle ground of values that can be made as a sum in 15-30 different ways. If you take two random sets of 13, there will almost always be a large overlap of these non-unique sums. Unless there is some clever construction that works, the only way seems to be to have one set of small numbers and one set of large ones, e.g. $\{1,2,3,4,5,6,7,8,9,10,17,18,19\}$ and $\{11,12,13,14,15,16,20,21,22,23,24,25,26\}$, but that is rather obvious. $\endgroup$ – Jaap Scherphuis Aug 8 '17 at 9:15
  • $\begingroup$ @JaapScherphuis I've tried my method and it terminates fairly quickly, though it does generate one of those easy cases you mention. :( $\endgroup$ – ffao Aug 8 '17 at 10:02
  • $\begingroup$ I tried skipping those where the unique sum is the smallest or largest possible sum of either of the sets. It gives results such as $\{2,3,4,7,9,10,21,22,23,28,31,34,35\}$ and $\{20,24,29,30,31,35,36,37,40,43,47,48,49\}$. This is still easy as the largest six numbers of the first set sum to $173$ and the smallest six of the second sum to $169$. It is easy to then switch one number in each to find the common sum $21+22+28+31+34+35=171=20+24+29+30+31+37$. $\endgroup$ – Jaap Scherphuis Aug 8 '17 at 11:06
  • $\begingroup$ It looks like all the solutions that exist are trivial, sadly. I'll have to add an additional constraint into the puzzle to get a solution that actually turns into a fun puzzle to solve. $\endgroup$ – Aranlyde Aug 8 '17 at 16:44
2
$\begingroup$

You can do the following

The Prouhet-Thue-Morse sequence.

The sequence $$t = (t_n)_{n>=0}$$ has the following property. Define enter image description here 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.

|improve this answer
$\endgroup$
  • $\begingroup$ Can someone help to hide the complete answer into the spoiler as i am not able to do so? $\endgroup$ – Anurag Aug 8 '17 at 9:58
  • $\begingroup$ I've spoilered it for you. Unfortunately, your method does not work because when you pad the sets to 13 numbers you allow many more other sums to be created, often in non-unique ways. For example, you can get 49 from both sets (replace 13 by 17 and 12 by 16), and say 90 can be made in many ways. $\endgroup$ – Jaap Scherphuis Aug 8 '17 at 10:42
  • $\begingroup$ I guess i missed one thing that the remaining 7 numbers should be between 32 to 50 $\endgroup$ – Anurag Aug 8 '17 at 10:55
  • $\begingroup$ With the current subset, 3 and 11 can be replaced with 34 and 42. $\endgroup$ – Apep Aug 8 '17 at 11:04
  • 1
    $\begingroup$ Now you can replace {3,5,12} with {16,18,20} and {13} with {47}. You could try finding the set of 6 closer to the center of [1, 50], then include smaller numbers in set A and larger numbers in set B. $\endgroup$ – Apep Aug 8 '17 at 12:53
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ It doesn't have to be Python or even computer-based at all. It's a one-off puzzle, so any method better than brute forcing would help. I edited the main question to reflect this. (Also, 50 choose 13 * 13 choose 6 is ~600 trillion, so I don't have enough space for that) $\endgroup$ – Aranlyde Aug 8 '17 at 5:59
  • $\begingroup$ I thought memory might be a problem. $\endgroup$ – Marius Aug 8 '17 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.