Score Cards

Alright, time for a new puzzle. Though I meant to post last time that that lemma I used didn't actually need the numbers ai to be positive reals, it is sufficient to be real. The proof is the exact same even, the only thing that needed to be positive in the proof were the zi, and positivity is guaranteed by L being the minimum Li. Anyway, whatever. New puzzle, I first learned from Bart:
There is a school that is using flip cards to keep track of scores in their sporting events. They use a series of cards to represent the ones place of the score, and another series for the tens place and so on for as many places as they feel they need. They want to minimize the number of cards used however, and (being a very mathematically inclined school) they are willing to change from base 10 to another base to accomplish this. For example, if you wanted to represent scores 0-99 in base 10 you would need 20 cards (10 for the ones place and 10 for the hundreds place) however you could do even better by using base 5 and having 3 sets of 5 cards (15 cards total) and be able to represent all the way from 0-124, naturally having the ability to represent extra numbers is not harmful at all, if it uses fewer cards it is better.

Actually, this school is even more mathematically inclined than that, they are even willing to use different bases for each place, for example the first digit could be base 5, the second digit base 5 and the third digit base 4, this uses only 14 cards and can represent 100 different possible numbers.

The puzzle is this: given a target number N, find the minimum number of cards it would take to represent at least the numbers 0 through N-1 on this style of scoreboard.

The solution to this puzzle is somewhat surprising, if you do think you have found a solution, make sure you have checked it out in some medium-sized cases (like numbers 10 through 25) to make sure it works, or better yet have a full proof done that it is actually optimal.


ed said...
This comment has been removed by the author.
ed said...

You should only use cards of base 2 or base 3. It is easy to show that no higher bases are needed; for example, a set of five base-5 cards could be replaced by one set of base-2 and one set of base-3, which could represent six states instead of five.

Also, never need to use more than two sets of base-2 cards, because you can replace three sets of base-2 with two sets of base-3, which can represent nine states instead of just eight.

So use either zero, one, or two base two cards, with the rest being base 3.

For N=100, use three base-3 and two base-2, for a total of 13 cards.

(Of course it would also be optimal to replace the two sets of base-2 with one set of base-4.)

If you solve this allowing non-integers, you get ln(N) sets of base-e cards, but this doesn't really make sense. Base-2 and base-3 are closest to base-e.