A book lover is thinking of buying six books from a group of eight. The price of each book is a whole number of dollars, and none is less than $2. The prices are such that each possible selection of six books would cost the buyer a different sum. In the end he can’t make up his mind and buys all eight books. What is the smallest amount he must pay?
Each choice of six books from the group of eight leaves two behind. The price of each possible omitted pair must be unique, or else the corresponding sextets would cost the same, which we know is not the case. So we can solve the problem by working out the lowest possible price for each book that ensures that every possible pair has a distinct price.
The three lowest possible prices are $2, $3, and $4. That’s fine so far, but the next book can’t cost $5, because then we’d have two pairs with the same value (5 + 2 = 3 + 4). So we jump to 6 and see if that works. By looking always for the smallest possible next higher price for each volume, we’ll arrive at 2, 3, 4, 6, 9, 14, 22, 31, which gives a total price of $91.
But, interestingly, that’s not the answer! After Roland Sprague published this puzzle in his 1963 book Recreation in Mathematics, he found the solution 2, 3, 4, 6, 10, 15, 20, 30, which totals 90. And Fritz Düball later found 2, 3, 4, 6, 10, 16, 21, 26, which totals 88. Is that the lowest sum possible? Sprague doesn’t claim that it is, and I’ve not seen this problem elsewhere than in his book.
06/19/2022 UPDATE: Reader Michael Küll wrote a program to search for all solutions in a reasonable range. There are four solutions with a total amount less than or equal to $91:
88 : 2 3 4 6 10 16 21 26
90 : 2 3 4 6 10 15 20 30
91 : 2 3 4 6 9 14 22 31
91 : 2 3 4 6 10 17 22 27
So Düball’s solution is indeed the best possible. (Thanks, Michael.)
_01.jpg){kind=link}