A new subdivision is being constructed, along a long road with hundreds of houses. The houses are all numbered in order starting with 1 – so they proceed 1, 2, 3, 4, … down the long road. All of the people go to the hardware store to buy numbers for their mailbox, and they line up in order at the counter. The store, unfortunately, has only 100 of each digit available.

Which homeowner will be the first who cannot buy the complete number for his mailbox?

The shopkeeper should have paid more attention to Benford's Law, which figures in the puzzle Bascule's Book. The digit 1 is going to be used more than any other.

The numbers 1-9 use 1 1.
The numbers 10-99 use 10 1's in the tens position and 9 in the units position for a total of 19, bringing the running total to 20.

Numbers 100-199 use 100 1's in the hundreds position plus another 20 duplicating 1-99, so this overshoots the mark, so lets go back to the count of 20 for 1-99.

100-119 use 20 in the hundreds pos, 10 in the 10's pos and 2 in the units pos, for a total of 32, bringing the running total to 52.

120-129 use 10 in the hundreds pos and 1 in the units for a total of 11, bringing the running total to 63.

The ranges 130-139, 140-149, and 150-159 likewise use 11 each, bringing the running total to 96.

160-162 use the remaining 4. Customer 163 finds no 1's left.

A simple program verifies our answer:
DO
 i = i + 1
 i$ = LTRIM$(STR$(i))
 FOR j = 1 TO LEN(i$)
   s = VAL(MID$(i$, j, 1))
   ct(s) = ct(s) + 1
 NEXT
 PRINT i,
 FOR j = 0 TO 9
   PRINT ct(j);
 NEXT
 PRINT
 IF i / 40 = INT(i / 40) THEN DO: LOOP UNTIL INKEY$ > ""
LOOP

158 25 95 36 36 36 35 26 26 26 25
159 25 96 36 36 36 36 26 26 26 26
160 26 97 36 36 36 36 27 26 26 26
161 26 99 36 36 36 36 28 26 26 26
162 26 100 37 36 36 36 29 26 26 26
163 26 101 37 37 36 36 30 26 26 26
164 26 102 37 37 37 36 31 26 26 26

The next most popular digit is 2, with only 37 sold by the time the 1's run out.

Posted by Charlie on 2003-06-18 15:31:27