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.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
04/01/2004 @ 8:30 AM ET
Solution:
05/02/2004 @ 8:30 AM ET
List Updated:
04/30/2004 @ 12:00 PM ET
People who answered correctly:
Satish Vedantam (4.1.2004 @10:14:43 AM EDT)
Luke Pebody (4.1.2004 @02:11:16 PM EDT)
Eugene Vasilchenko (4.1.2004 @02:50:43 PM EDT)
Daniel Wood (4.1.2004 @05:22:50 PM EDT)
Graeme McRae (4.1.2004 @08:02:29 PM EDT)
Coserea Gheorghe (4.1.2004 @08:24:32 PM EDT)
John Lister (4.1.2004 @08:31:34 PM EDT)
Dan Dima (4.1.2004 @11:57:11 PM EDT)
M.Venkata Ramayya
Amod Kulkarni (4.2.2004 @04:31:35 AM EDT)
Anand (4.2.2004 @07:18:23 AM EDT)
Trevor Graffa (4.2.2004 @04:30:46 AM EDT)
Stephane Peysson (4.2.2004 @08:49:18 AM EDT)
Roberto Tauraso (4.2.2004 @09:42:37 AM EDT)
John Tromp (4.2.2004 @12:18:00 PM EDT)
Narayanan Rajamani (4.2.2004 @01:48:26 PM EDT)
Sean Owen (4.2.2004 @03:29:34 PM EDT)
Dave Blackston (4.2.2004 @03:48:31 PM EDT)
Gyozo Nagy (4.2.2004 @05:23:00 PM EDT)
Brian Bitto (4.2.2004 @05:51:25 PM EDT)
Hongli Xu (4.2.2004 @09:05:52 PM EDT)
Amit Chattopadhyay (4.3.2004 @03:47:16 AM EDT)
Daidi (4.3.2004 @07:10:21 AM EDT)
Al Zimmermann (4.3.2004 @03:14:57 PM EDT)
L.J. Zigerell Jr. (4.3.2004 @03:43:35 PM EDT)
ILan Algor (4.4.2004 @11:51:41 AM EDT)
Frank Mullin (4.4.2004 @12:18:54 PM EDT)
Rock Verser (4.5.2004 @08:10:27 AM EDT)
Clive Tong (4.5.2004 @10:47:20 AM EDT)
Peter Mattsson (4.5.2004 @11:12:00 AM EDT)
Kalyana Chakravarthy (4.5.2004 @11:34:03 AM EDT)
Kennedy (4.6.2004 @01:14:57 AM EDT)
Luca Dalla Valle (4.6.2004 @06:44:17 AM EDT)
Daragó László (4.7.2004 @04:29:35 AM EDT)
Vardhan (4.7.2004 @08:52:01 AM EDT)
Ross Millikan (4.7.2004 @02:11:11 PM EDT)
Anneke Van Steirteghem (4.7.2004 @04:31:53 PM EDT)
Arun Mandayam Krishnakumar (4.8.2004 @03:42:34 AM EDT)
Joe BGI SF Fendel (4.8.2004 @10:56:38 AM EDT)
Joe Vanore (4.8.2004 @05:46:06 PM EDT)
Vishal Mamania (4.9.2004 @02:53:01 PM EDT)
Tim Deegan (4.9.2004 @03:59:55 PM EDT)
David Friedman (4.9.2004 @04:11:37 PM EDT)
Vinko Marinkovic (4.10.2004 @01:36:17 AM EDT)
Nikhil Sahasrabudhe (4.10.2004 @03:59:42 AM EDT)
Claudio Baiocchi (4.11.2004 @01:04:29 PM EDT)
John Fletcher (4.11.2004 @07:27:57 PM EDT)
Vineet Batra (4.12.2004 @06:47:18 AM EDT)
Andre Rzym (4.12.2004 @01:07:36 PM EDT)
Sriram Sankaranarayanan (4.12.2004 @08:41:58 PM EDT)
Vincent Vermaut (4.13.2004 @08:38:18 AM EDT)
Krishna Chaitanya (4.14.2004 @08:28:41 AM EDT)
IQSTAR (4.14.2004 @01:58:02 PM EDT)
Karl D'Souza & Cristian Ianculescu (4.14.2004 @02:39:23 PM EDT)
Paul Botham (4.14.2004 @03:53:00 PM EDT)
John David Vessey (4.14.2004 @10:56:50 PM EDT)
Mohit Srivastava (4.15.2004 @08:08:19 AM EDT)
Bob Stewart (4.16.2004 @06:45:00 AM EDT)
David P Woodruff(4.16.2004 @08:28:22 PM EDT)
Emile Joubert(4.18.2004 @03:46:16 PM EDT)
Michael Swart(4.19.2004 @11:52:40 AM EDT)
Shmuel Spiegel(4.19.2004 @11:26:54 PM EDT)
Mayank M
Kabra (4.20.2004 @01:04:18 PM EDT)
Ananda Raidu(4.21.2004 @07:26:28 AM EDT)
Derek Kisman (4.21.2004 @02:50:27 PM EDT)
Hagen von Eitzen (4.22.2004 @05:00:56 AM EDT)
Siva Dirisala(4.23.2004 @06:50:32 PM EDT)
Nagachandra Sekhar Grandhi(4.25.2004 @09:19:45 AM EDT)
Srinivaasan Markandan(4.25.2004 @10:49:33 PM EDT)
Daniel Chong Jyh Tar(4.26.2004 @12:32:57 AM EDT)
Wolfgang Kais (4.26.2004 @10:07:44 AM EDT)
Mihai Cioc(4.26.2004 @03:33:03 PM EDT)
Raj Mohan (4.27.2004 @08:41:15 PM EDT)
Kumar (4.29.2004 @05:05:16 AM EDT)
R. Nandakumar (4.29.2004 @07:35:39 AM EDT)
Frans Buijsen(4.29.2004 @07:44:10 AM EDT)
Mark Abramson(4.29.2004 @02:28:35 PM EDT)
Chris Shannon (4.30.2004 @07:19:50 PM EDT)
Ervan Darnell (4.30.2004 @10:53:06 PM EDT)
Peter Huggins (5.01.2004 @01:45:41 PM EDT)
Praveen Jagadishprasad (5.02.2004 @09:24:32 PM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.