No longer updated!

Saturday, July 26, 2008

Beer and Bitterballs

On a nice summer day, two tourists visit the Dutch city of Gouda. During their tour through the center they spot a cosy terrace. They decide to have a drink and, as an appetizer, a portion of hot "bitterballs" (bitterballs are a Dutch delicacy, similar to croquettes). The waiter tells them that the bitterballs can be served in portions of 6, 9, or 20.

The Question: What is the largest number of bitterballs that cannot be ordered in these portions?


Answer: Every natural number is member of one of the following six series:

* 0, 6, 12, 18, ...
* 1, 7, 13, 19, ...
* 2, 8, 14, 20, ...
* 3, 9, 15, 21, ...
* 4, 10, 16, 22, ...
* 5, 11, 17, 23, ...

If for a number in one of these series holds that it can be made using the numbers 6, 9, and 20, then this also holds for all subsequent numbers in the series (by adding a multiple of 6).

To find out what the largest number is that cannot be made using the numbers 6, 9, and 20, we therefore only need to know, for every series, what the smallest number is that can be made in that way.

In the series 0, 6, 12, 18, ... the smallest number that can be made is 0, so there is no number that cannot be made.
In the series 1, 7, 13, 19, ... the smallest number that can be made is 49 (20+20+9), so 43 is the largest number that cannot be made.
In the series 2, 8, 14, 20, ... the smallest number that can be made is 20, so 14 is the largest number that cannot be made.
In the series 3, 9, 15, 21, ... the smallest number that can be made is 9, so 3 is the largest number that cannot be made.
In the series 4, 10, 16, 22, ... the smallest number that can be made is 40 (20+20), so 34 is the largest number that cannot be made.
In the series 5, 11, 17, 23, ... the smallest number that can be made is 29 (20+9), so 23 is the largest number that cannot be made.

Therefore, 43 is the largest number that cannot be made using the numbers 6, 9, and 20.


No comments: