April 2004
SOLUTION:
The first thing to note is that the "1"s digit is always the one with the lowest stock. Therefore, it must be the digit that will run out first. All other digits are inconsequential. We will use the notation s(x) to denote the number of "1"s that are in stock after labelling the x'th cassette. s(x) can be negative to indicate a deficit in "1"s. We are interested in the lowest x for which s(x) is negative.
Note that the required x must have at least two "1"s, or else
s(x)≥s(x-1).
Second, note that the first unlabellable cassette must have a number of the form 1XYZ... . That is, its most significant digit must be "1". The reason for this is that if the string UVW (of any length) has no "1"s, then
s(UVW1XYZ...) - s(UVW0000...) = s(1XYZ...)
If "UVW1XYZ..." is the first unlabellable cassette, then s(UVW1XYZ...) must be smaller than s(UVW0000...), meaning that s(1XYZ...) is smaller than zero. Because "UVW1XYZ..." is larger than "1XYZ..." it can not be the required solution.
Third, notice that when x is of the form "1XYZ...", s(x) is monotonously decreasing (in a weak sense). For this reason, it is not necessary to inspect each X of that form, but only those x's of the form "1999..." (where "9" represents the "B-1" digit) in order to know in which block of numbers of the form 1XYZ... the x we are looking for is. In particular:
s(2*B^n-1) = (2*B^n-1) - B^n - n*2*B^(n-1) "where "^" denotes exponentiation."
The first term is the number of "1"s we got. The second is the number of "1"s used to label the most digit in the B^n position. The final term states that for each of the preceding n places, exactly 1/B of the digits used were "1"s.
Therefore:
s(2*B^n-1) = (2B-B-2n)*B^(n-1) - 1 = (B-2n)*B^(n-1) - 1
Clearly, the streak of numbers of the form "1XYZ..." in which the number we are looking for resides is the one between B^(B/2) and 2*B^(B/2)-1.
When reaching y=2*B^(B/2)-1 our stock is at s(y)=-1. So, all we need to do is to find the highest number that is smaller than y that has more than a single appearance of the digit "1". This will be the number in which s(x) becomes -1 from a non-negative value for the first time, and is therefore our solution.
This number is 2*B^(B/2)+1-B, which has "1" both in the most significant digit and in the least significant digit. For base ten, this value is 199991, which is significantly smaller than most people initially guess.
John Fletcher gives the following interesting treatment of the case of odd B:
Let c(b, n) be the number of occurrences of digit b, 0 <= b < B, among all the numerals n', 0 < n' <= n, expressed in radix B >= 2 without leading 0's.
Lemma: For all b and n, c(1, n) >= c(b, n).
Proof: There is a 1-to-1 mapping between the occurrences of any particular digit b != 1 and the occurrences of digit 1, with digit b in the bit position valued B^d, d >= 0, of numeral n' being paired with digit 1 in the same bit position of a lesser numeral, n' - (b-1)*B^d if b > 1 or n' - (B-1)*B^d if b = 0. So for every occurrence of digit b contributing to c(b, n) there is an occurrence of digit 1 contributing to c(1, n) -- QED. Let C(n) = c(1, n) and E(n) = C(n)-n, the desired integer N being the least such that E(N) > 0. Let Z = B-1, the largest digit.
Lemma: The leading (leftmost) digit of N must be 1.
Proof: Assume N to have a leading digit b > 1. Let M be the largest numeral less than N with a leading 1 (its digits being 1ZZ...Z), let m be the largest numeral with one fewer digits than N (ZZ...Z), and let m' be N with its leading digit removed; so E(N) = E(M) + (d-2)*E(m) + E(m'). Since M < N, m < N, and m' < N, it must be that E(M) <= 0, E(m) <= 0, E(m') <= 0, and consequently E(N) <= 0, a contradiction -- QED, reductio ad absurdum. So 1 followed by D >= 0 additional digits expresses N.
Let K = 2*B^D - 1 be the largest number expressed as 1 followed by D digits (1ZZ...Z); so C(K) = B^D + 2*D*B^(D-1) and E(K) = (2*D-B)*B^(D-1) + 1. Since E(k) is monotonically non-decreasing when N <= k <= K, it must be that E(K) >= E(N) > 0; so D is the least integer such that 2*D >= B. If B is even, then D = B/2 and E(K) = 1; so N is the largest integer not exceeding K expressed with at least two 1's, namely 2*B^(B/2) - B + 1 (1ZZ...Z1, where the Z's are B/2 - 1 in number) -- QED for even N.
If B is odd, then D = (B+1)/2 and E(K) = B^((B-1)/2) + 1, and there seems to be no simple expression for N. A C-language algorith given later, O(B) in the number of arithmetic and logical operations, implements a division-like procedure that finds N (for B either even or odd) -- QED: Using 012...89AB...YZ as digits, the N's for even B include binary 11, octal 17771, decimal 199991, and hexadecimal 1FFFFFFF1; for small odd B they are given in a table later.
When B is composite these show a tendency for some rightmost digits to have the form ...ZZZ1, just like all digits except the leftmost when B is even.
Counting digits from right to left starting with 0, let NN[d] = B-1-N[d] be the dth digit of NN, the "complement" of N. Assume that, except for d = D (the leftmost digit) and d = 0 (the rightmost digit), N[d] > 1, so that NN[d] < B-2. Then in the algorithm for N[d], L-1 always equals 0, inc always equals d, and only the last ("else") alternative applies for D > d > 0. A bit of algebra then shows that each successive NN[d] from left to right is obtained as the quotient when B*r is divided by d, where r is the remainder obtained from the division to obtain the preceding digit NN[d+1], the initial remainder for d = D being set to 1. (The full algorithm -- no assumptions -- for NN[d] when B is odd is as follows:
int complement (B, NN)
int B; /* radix (odd only) */
int NN[ ]; /* pointer to digits of complement */ {
int D; /* index (power of B) of leftmost digit */
int d; /* index of current digit */
int L; /* count of (B-2)'s among digits indexed >= d */
int r; /* count/(B to the d-1) of (B-2)'s still needed */
int inc; /* rate/(B to the d-1) of increase of (B-2)'s */
D = (B+1)/2;
NN[D] = B-2, r = 1, L = 1; /* find leftmost digit */
for (d = D-1; d > 0; d--) { /* from left to right, */
r *= B, inc = (L-1)*B + d; /* find further digits */
if (r < (B-2)*inc) /* digit < B-2 ? */
NN[d] = r/inc, r %= inc;
else if (r < (B-1)*inc+B) /* digit == B-2 ? */
NN[d] = B-2, r -= (B-2)*inc, L++;
else /* digit == B-1 */
NN[d] = B-1, r -= (B-1)*inc+B; }
inc = L-1; /* find rightmost digit */
if (r < (B-2)*inc) /* digit < B-2 ? */
NN[0] = r/inc;
else if (r < (B-1)*inc+1) /* digit == B-2 ? */
NN[0] = B-2;
else /* digit == B-1 */
NN[0] = B-1;
return D; } /* return digit count */ )
Clearly, if the remainder r equals 0 for d = D', then it also equals zero for all succeeding d in the range D' > d > 0, with NN[d] = 0 (that is, N[d] = B-1); also NN[0] = B-2 (that is, N[0] = 1). Moreover, r surely equals 0 when d is a divisor of B, perhaps (depending on the value of the preceding r) also when d is a multiple of a proper divisor.
All this implies that, except in the following two cases, D' rightmost digits of N are of the form ...ZZZ1, where D' is a multiple of a proper divisor of B and is no less than the largest proper divisor: (1) If B is a prime, then the form does not appear because there are no proper divisors. (2) If NN[d] = B-2 (that is, N[d] = 1) happens to occur for some d equal to or greater than what would be D', then the assumptions are violated, and the form does not appear. These conclusions are illustrated by the following results for small B (where the digits are 012...89AB...YZab...yz):
| B | N | NN |
D' |
| 3: | 111 | 111 | 1 |
| 5: | 1212 | 3232 | |
| 7: | 14314 | 52352 | |
| 9: | 165881 | 723007 | 3 |
| 11: | 18815A0 | 922950A | |
| 13: | 1AA317A1 | B229B52B | 1 |
| 15: | 1CC5EEEE1 | D2290000D | 5 |
| 17: | 1EE86CB1D2 | F228A45F3E | |
| 19: | 1GGAFF1C17E | H22833H6HB4 | |
| 21: | 1IID1A1G8I28 | J227JAJ4C2IC | |
| 23: | 1KKF5G7DH1HAB | L227H6F95L5CB | |
| 25: | 1MMHB1CC1K8O0O | N227DNCCN4G0O0 | |
| 27: | 1OOJG2QQQQQQQQ1 | P227AO00000000P | 9 |
| 29: | 1QQLL1DL40NPDGO3 | R2277RF7OS53FC4P | |
| 31: | 1SSNPP96R1J7N0S4P | T22755LO3TBN7U2Q5 | |
| 33: | 1UUPUDNWWWWWWWWWW1 | V2272J90000000000V | 11 |
| 35: | 1WWRYYYYYYYYYYYYYY1 | X22700000000000000X | 15 |
| 37: | 1YYU1F84J9G2GU3IZ4R8 | Z226ZLSWHRKYK6XI1W9S | |
| 39: | 1aaW2FM8cccccccccccc1 | b226aNGU000000000000b | 13 |
| 41: | 1ccY4XAc1KaAI1EUBCFbNS | d226a7U2dK4UMdQATSP3HC | |
| 43: | 1eea751JBD1WF9LLB8g1QdF | f226ZbfNVTfARXLLVY0fG3R | |
| 45: | 1ggc9Jiiiiiiiiiiiiiiiii1 | h226ZP00000000000000000h | 18 |
| 47: | 1iieBYSX5eXPBY4VBXNIZ1fAZ | j226ZCIDf6DLZCgFZDNSBj5aB | |
| 49: | 1kkgDmmmmmmmmmmmmmmmmmmmm1 | l226Z00000000000000000000l | 21 |
| 51: | 1mmiG9ZYjEoooooooooooooooo1 | n226YfFG5a0000000000000000n | 17 |
| 53: | 1ookILZFlKV6VfWUm5Bdbi1ham8h | p226YVHb5WLkLBKM4lfDF8p9G4i9 | |
| 55: | 1qqmKXOsssssssssssssssssssss1 | r226YLU000000000000000000000r | 22 |
| 57: | 1ssoMj4sLdouuuuuuuuuuuuuuuuuu1 | t226YBq2ZH6000000000000000000t | 19 |
| 59: | 1uuqOuapG2l9GKlt1a2ScRirbBw2oGf | v226Y2M7guBngcB3vMuUKVE5Ll0u8gH | |
| 61: | 1wwsR4fRwJNC9bEJ1aaFrMK1rQCTWCHp | x226XuJX2fbmpNkfxOOj7cex7YmVSmh9 |
Note that the indicated form appears only for composite B, with D' being no less than the largest proper divisor of B and having a common proper factor with B. That D' = 1 for B = 3 and for B = 13 reflects the fact that -- by "chance" -- N[0] happens to equal 1.) Also, the form does not appear for B = 21 or B = 25, because N[d] = 1 for d = 7 or d = 8, respectively, which equals or exceeds the minimum possible D', namely 7 or 5, respectively.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com