Digit Counting (Posted on 2005-02-25)

	Submitted by David Shin
Rating: 3.3333 (3 votes)
Solution:	(Hide)
Make a list of positive integers by writing down, for each j in the sequence 1,2,3,...,10^n, all the numbers you get by inserting a zero after any digit in j. For example, for j=207, we would add the numbers 2007 (twice) and 2070 to the list. Clearly, the number of entries added to the list for any value of j is the number of digits in j, so the length of the final list is the total number of digits in the sequence 1,2,3,...,10^n. It is also clear that each number in the list is less than or equal to 10^(n+1). To establish the desired result we show that for any positive integer k<=10^(n+1), the number of times that k appears in the list is equal to the number of zeros in k, and therefore the length of the list is also the total number of zeros in the sequence 1,2,3,...,10^(n+1). The reason for this is simply that for each zero in k, k is listed once with that zero being the added zero.

	Subject	Author	Date
	Solution	Tristan	2005-02-26 03:13:00
	solution	Charlie	2005-02-25 14:25:24