20
$\begingroup$

After reading a bit in Meta and the help section, I'm still not sure whether this qualifies as a "good" puzzle in the spirit of the site, but the votes will show - I liked it when I encountered it, and maybe others will enjoy it as well.

The goal of this puzzle is to find a set of 17 numbers between 0 and 100, so that every number between 0 and 100 can be written as the sum of two of these numbers.

The limits of 0 and 100 are both inclusive, so there are 101 sums to be constructed. The sums may involve the same number twice. So obviously, 0 must be part of the solution, as 0 = 0 + 0 is the only way of obtaining 0 as one sum.

As an example, a solution might look like

{ 0, 1, 3, ..., 49, 51 }

  0 = 0 + 0  
  1 = 1 + 0
  2 = 1 + 1
  3 = 3 + 0
  4 = 3 + 1
  5 = ...
      ...  
 99 = ...
100 = 49 + 51

A warning:

You will easily find solutions with 18 numbers, or 17 numbers that give 95 of the required sums. But finding a valid solution is really, really hard. I have to admit that I did not manage to manually find such a solution. Instead, I wrote a program to solve it.

Therefore the use of computers, programs or tools of any kind is explicitly encouraged.

In hindsight, might also have been possible to derive a solution manually. But it is difficult, regardless of whether someone considers it as a brainteaser or a programming challenge.

Update with Hints 0 and 1:

Hint 0: As already mentioned above, finding solutions that are "nearly complete" is far easier than finding an actual solution. This does not necessarily mean that it is trivial to manually find a solution, e.g. one that gives 95 sums or uses 18 numbers. It just means that there are far more such solutions. As per request in the comments (and as already posted in the chat), one solution with 18 numbers is

[0, 1, 2, 3, 4, 5, 10, 16, 22, 28, 34, 40, 41, 45, 48, 49, 50, 82]

But one should not expect a 17-number-solution to be "similar" to that in any way.

Hint 1: One could imagine different approaches for solving this:

  • Starting with a solution that gives the desired 101 sums, but uses more than 17 numbers, and trying to reduce the number of numbers step by step
  • Starting with a solution that uses 17 numbers, but does not give all 101 sums, and modifying the numbers step by step
  • A hybrid method of building the list of numbers and checking the resulting sums in parallel, adding and removing numbers as necessary (as some sort of "backtracking")

It's hard to say which approach is more promising when trying to solve it manually. The hybrid one seems to be the most "controllable" and easiest to wrap the head around when trying to solve it manually (but as I mentioned: I did not succeed with this when I tried it). For the program that I eventually wrote, I used the second approach: Starting with 17 "reasonable" numbers, and modifying them, step by step, trying to fill the gaps in the list of sums.

There is another Hint 2 that refers to one particular solution, but I think that it will make it much easier to find this solution, so I'll wait with this one until tomorrow.

(Another remark: There are problems that look somewhat similar to this one. For example, the problem of finding a Sparse Ruler. Maybe someone finds this interesting as an entry point, although it will not necessarily help to solve this puzzle)

Improve this question
$\endgroup$
11
  • $\begingroup$ "the use of computers, programs or tools of any kind is explicitly encouraged" - I hope I understood this in the right way... Do you mean "You can just write programs, I don't care."? If yes, this would be more on-topic on the code golf site. I think in any "normal" puzzle you shouldn't be allowed to use programs that solve it completely. But maybe I didn't understand the sentence right :P $\endgroup$
    – user14478
    Aug 15, 2015 at 15:43
  • 1
    $\begingroup$ @LuxxMiner It's possible (just hard) to do it without computers. I think this is on-topic here and a nice puzzle. Note the existence of a [computer-puzzle] tag with 46 questions; not everything that allows programming should be migrated to PPCG! $\endgroup$
    – Rand al'Thor
    Aug 15, 2015 at 15:46
  • $\begingroup$ @randal'thor Ok, I always thought writing programs wouldn't be very esteemed on this site. I guess I was wrong all the time, then :D $\endgroup$
    – user14478
    Aug 15, 2015 at 15:48
  • 1
    $\begingroup$ @Marco13 do you have any examples of 18 numbers giving all of the sums? $\endgroup$
    – Andrew Smith
    Aug 15, 2015 at 22:45
  • 2
    $\begingroup$ @AndrewSmith Yes, but I'm not sure whether I should post them now, for several reasons: 1. The question is rather new - I'd at least wait until today evening before posting it. And 2: I'm not sure whether it would be helpful or "distracting". Nevertheless, I could post it together with the first hint, but this would not be a "hint" in the classical sense (i.e. it would not make the problem itself easier, but only describe the "general" coding approach that I took). Another hint exists that refers to one particular solution, and will make it easier to find this particular solution. $\endgroup$
    – Marco13
    Aug 16, 2015 at 4:08

3 Answers 3

Reset to default
10
$\begingroup$

Answer:

[0, 1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90]

Method:

There are at most ${17 \choose 2} = 136$ combinations of 17 numbers, so if a candidate set generates more than 35 duplicates (more than one pair of numbers adding up to the same sum), that set cannot produce all 101 required numbers and so can be culled.

I generated sets with increasing cardinality, starting from the known {0,1}, culling the partial sets along the way. For each remaining set at that round, all possible sets with one extra number were generated and then culled, etc. This relies on the observation that adding elements to a set does not decrease the number of duplicates it generates.

The number of candidate sets reached a maximum at cardinality 13, with just 149 candidates not culled by the end. Of these 149 sets, only one was able to generate all 101 numbers.

Edit As it turns out, I missed counting the 17 doubled numbers. Increasing the number of allowed duplicates produces the following lists:

[0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 28, 29, 30, 61, 64, 67, 70]
[0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 45, 47, 48, 49, 52]
[0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 47, 48, 49, 51]
[0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 48, 49, 51, 53]
[0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52]
[0, 1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90]
[0, 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50]

Pseudocode: start by calling puzzling101([0,1]).

Invariant: each candidate is an ordered list (strictly increasing) of distinct integers.

puzzling101(c) =
if (#elements in c == 17) {
    display c if it generates all 0..100
} else {
    min = 1 + largest number in c
    max = 84 + #elements in c
    for each x in [min..max], call puzzling101([x|c]) if [x|c] generates
    1. all numbers 0..x (ignore larger x if not), and
    2. less than 52 duplicates between 0 and 100
}
Improve this answer
$\endgroup$
11
  • $\begingroup$ Would you mind sharing your code? I'm interested about the approach you took. $\endgroup$
    – Rohcana
    Aug 17, 2015 at 7:04
  • 1
    $\begingroup$ Congratulations! I did not expect the solution to be found so quickly. And most importantly: You seem to have used a very clear and systematic approach! (My program was rather "trying around" unsystematically, and the resulting code was a mess. Once more a sign that it is often better to diligently analyze a problem before trying to solve it. So I'd also be interested in your code, btw). Well done! $\endgroup$
    – Marco13
    Aug 17, 2015 at 9:58
  • $\begingroup$ @Anachor and Marco13 Thanks! Pseudocode added. The only items of note in the pseudocode other than the order of generating partial candidates are the preservation of the invariant and the cull, both of which helped keep a lid on the combinatorial explosion. $\endgroup$
    – Lawrence
    Aug 17, 2015 at 11:50
  • $\begingroup$ Why oh why would you use brackets in pseudo code?. $\endgroup$
    – Rohcana
    Aug 17, 2015 at 11:53
  • $\begingroup$ @Anachor For clarity. :) $\endgroup$
    – Lawrence
    Aug 17, 2015 at 11:54
5
$\begingroup$

Congratulations to Lawrence for his solution!

Here is a list of all (?) solutions for this problem.

(0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 28, 29, 30, 61, 64, 67, 70)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 45, 47, 48, 49, 52)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 47, 48, 49, 51)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 48, 49, 51, 53)
(0, 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52)
(0, 1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90)
(0, 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

(I did not all find all of them myself: My program found 5 solutions, and after a few minutes, I stopped it - I'm not sure whether it would also have found the other ones, because it was not as systematic and deterministic as the approach that Lawrence described)

The most interesting solution, for me, was the last one:

(0, 1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

This is the solution that the Hint 2 would have referred to:

Surprisingly, it does not need any value larger than 50. But more importantly: The solution is symmetric! When this is plotted as a graph, it looks like the first part of a sine curve. I think if someone had come to the ideas of 1. Only using the numbers between 0 and 50, 2. Making the solution symmetric, and 3. Using "more" numbers at the beginning and end of the 0...50 interval, and fewer in the middle, then one might also have found the solution manually.

EDIT In response to the comments:

A rough description of the "algorithm". As already mentioned, it is not very systematic, but did its job:

Initialization: First of all, a simple initial solution is constructed by greedily collecting 17 numbers: Starting with a list of [0,1], in each step I'm examining all possible remaining numbers, and choose the one where the number of "missing sums" is the smallest. This produces the initial solution of

0, 1, 3, 5, 7, 12, 17, 20, 26, 30, 35, 39, 41, 44, 46, 54, 68

where 11 sums are still missing.

Search: I'm maintaining a list of "candidate" solutions, each given by the list of 17 numbers, and the number of missing sums. Then, I'm "wiggling" these numbers: For the candiate solution with the least number of missing sums, I'm creating variations, by shifting each number of the list between its left and right neighbor. For example, from a candiate solution like this

0, 1, 3, 5, 7, 12, 17, 20, 26, 30, 35, 39, 41, 44, 46, 54, 68 (missing: 11)
                       ==

I'm creating further candidates:

0, 1, 3, 5, 7, 12, 17, 18, 26, 30, 35, 39, 41, 44, 46, 54, 68 (missing:...)
                       ==
0, 1, 3, 5, 7, 12, 17, 19, 26, 30, 35, 39, 41, 44, 46, 54, 68 (missing:...)
                       ==
...
0, 1, 3, 5, 7, 12, 17, 25, 26, 30, 35, 39, 41, 44, 46, 54, 68 (missing:...)
                       ==

And I'm always doing this with the candiate with the least number of missing sums.

(Actually, this "list" is a priority queue, ordered ascending by the number of missing sums, and I'm occasionally "pruning" this queue by removing candidates that are far worse than the current best one, but these are details).

This is not very deterministic, and (due to the pruning) not even guaranteed to find a solution at all, but it found ... at least 5 of them within a few minutes.

I probably won't post the (Java) code here, because it's a bit lengthy and rather messy, but I hope that the basic idea became clear

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ The fifth is symmetric too, in fact it checks up to 104! $\endgroup$
    – Rohcana
    Aug 17, 2015 at 10:51
  • 1
    $\begingroup$ @Anachor So everything's ready for "Puzzling 104" ;-) I particularly liked the fact that the last one only uses exactly half of the interval, and was symmetric around 25. This looks so much like striking a pattern that it's somehow distressing to not have found it with pen+paper... $\endgroup$
    – Marco13
    Aug 17, 2015 at 10:58
  • $\begingroup$ Nice, I only managed to generate one solution - what algorithm did you use? It seems my culls may have been too aggressive. $\endgroup$
    – Lawrence
    Aug 17, 2015 at 11:56
  • $\begingroup$ @Lawrence OK, I wasn't sure whether your statement that "only one was able to generate all 101 numbers" really meant that only one solution was found in the overall process (the code was not available back then). I'll add an EDIT with my "algorithm" (if it can be called so) soon. $\endgroup$
    – Marco13
    Aug 17, 2015 at 13:05
  • $\begingroup$ I think I found the problem: in counting the max number of duplicates, I only considered pairs of different numbers and missed counting the possibility of selecting the same number twice. So the total number of 'pairs' possible should be increased by 17, which in turn increases the max duplicates to 52. Restricting max duplicates to 35 happens to generate a unique solution quickly. $\endgroup$
    – Lawrence
    Aug 17, 2015 at 14:06
4
$\begingroup$

This problem is almost identical to "Coins of the Realm" which appeared an old Scientific American column, from June 1964. It's included in Chapter 12 of his Sixth Book of Mathematical Games from Scientific American (W. H. Freeman, 1971), and in the following form in Chapter 1 of his The Colossal Book of Short Puzzles and Problems (Norton, 2006, edited by Dana Richards):

In this country at least eight coins are required to make the sum of 99 cents: a half-dollar, a quarter, two dimes and four pennies. Imagine you are the leader of a small country and you have the task of setting up a system of coinage based on the cent as the smallest unit. Your objective is to issue the smallest number of different coins that will enable any value from 1 to 100 cents (inclusive) to be made with no more than two coins. For example, the objective is easily met with 18 coins of the following values:

1, 2, 3, 4, ... 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90.

Can you do better? Every value must be obtainable either by one coin or as a sum of two coins. The two coins need not, of course, have different values.

Martin gives two 16-coin solutions, as follows (which would be 17-number solutions to the problem here):

1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50

is listed as being given in Roland Sprague's Recreation in Mathematics, and is good for precisely the range 1—100.

1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52

is listed as having been provided by Peter Wegner, and is good for the larger range 1—104.

Those solutions were proposed in the 60s so very likely were done manually.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Very interesting! May I ask where you found this? (Plain websearches about "Scientific American" "Coins of the Realm" do not seem to bring results). Indeed, both solutions are equivalent to the solutions already posted - the fact that the question here required 17 values including the 0 is nicely covered by the optional usage of two coins in this original problem description. $\endgroup$
    – Marco13
    Oct 26, 2015 at 13:15
  • 1
    $\begingroup$ I own the book "The Colossal Book of Short Puzzles and Problems " amazon.com/Colossal-Book-Short-Puzzles-Problems/dp/0393061140/… If "Look Inside" works on the link above you will find it on page 8, Problem 1.11. I was not able to do it so I checked the provided solution only to discover is just the two sequences above and no further explanation about HOW they were found, so I googled the solution texts and found them here. $\endgroup$
    – antorsae
    Oct 26, 2015 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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