IBM Ponder This #072 · April 2004

This month's puzzle comes from Michael Brand.

My friend compulsively records television programs on his VCR. To this end, he has a very large stock of VCR cassettes. He has long given up on trying to label these cassettes with any meaningful names. Now he just numbers them. The numbers go from 1 up and are consecutive.

In order to label the cassettes, he uses the digit stickers that come with a bought cassette. Each cassette comes with one sticker for each digit.

So, for example, to label the first cassette, he uses just the sticker "1" and keeps the rest. To label the second, he uses just the sticker "2" and keeps the rest. To label the tenth, he uses two stickers, one "1" and one "0", and keeps the rest. To label the eleventh, he uses one "1" sticker from the stickers he just got, and one "1" sticker which he had in stock from the previous ten. And so on.

The question is, what is the number of the first cassette which he will no longer be able to label in this way (i.e., that will deplete his stock of stickers to the point that he will not be able to form the desired number)? Please give your answer for general B, as well as for B=10. Please supply a proof if posssible.

In order to make the question interesting (and avoid simple programmatic solutions), the solver should give a closed formula for the number as a function of B, where B is the base in which my friend counts (assume that the cassettes come with one sticker for each digit of the base used). So, for example, if my friend chooses to count in hexadecimal, this is because each cassette comes with 16 stickers, that are "0", "1", "2", ... , "F"). The closed formula need only work for B's that are even numbers, such as decimal, octal, hexadecimal and binary. I am not aware of the existence of a closed formula for the odd numbered bases.

As usual, preference is given to closed-form solutions (no recursion, no sums). Each proof is expected to be your own; it's no fair using a proof that you've seen elsewhere.

Solution

Best opened after a real attempt

To be added.