The Ball Factory Worker

Question

A woman works at a ball factory. She's instructed to open up a ball creation kit composed of one red rubber ball and two strips of digit stickers from $0$ through $9$.

She's instructed to do the following:

1. Starting with $1$, write the current number on the ball using the digits available on the 2 strips.
2. Put unused digits into a bowl where they can be used later for when she runs out of available digits in step #1.
3. Open up another ball creation kit and continue to step #1 for the next number.

Assume there are no problems with space to put these digits (yes, there will be a lot of them). Also, assume $6$ and $9$ can be differentiated (have a line underneath), so you cannot substitute one for the other.

The question is, what will be the first number that she cannot write out?

Answer 1

I used the code from this answer: https://stackoverflow.com/questions/20945790/count-the-number-of-ks-between-0-and-n, translated to C# and modified to use BigInteger.

I then tried numbers that fit into the following category: 119..91. This is the last number in the long line of numbers that use up 1's faster than they are created.

I now have an answer. I'd really consider it more of an upper bound at this point.

1,174,638,269,999,999,981

The total number of 1's available is 2,349,276,539,999,999,962. The total number of 1's needed is 2,349,276,539,999,999,963.

Update:

I have found that 119..91 is not the best point between 10^n-1 and 10^(n+1)-1. This has allowed me to significantly lower my upper bound. I believe this answer to be too high, but now within one significant digit:

1,999,919,999,999,981

The total number of 1's available is 3,999,839,999,999,962. The total number of 1's needed is one more than that.

Answer 2

Let's lay down some groundwork to help us out:

• Let $req(n, d)$ be the number of digit $d$ required to write out all the numbers from 1 to $n$.
• Since each kit contains two of each digit, we have $2n$ of each digit
• This means we want the smallest $n$ for which $req(n, d) > 2n$ for some $d$

It seems like this would be pretty easy to brute-force until you realize that the first number will have around 20 digits (individual digits see about equal use and we get 20 more digits each time). So instead let's figure out how many of each number is required in order to write up to 9, 99, 999, etc.

Up to 9: One each of 1 through 9

Up to 99: One each of 0 through 9 for each group of ten, then ten each of 1 through 9 for the numbers in the tens places. This totals twenty of each except zero, leaving us with 99*2-20 = 178 of each digit other than zero.

Up to 999: Same as up to 99 (with leading zeros) for each group of 100, then 100 each of 1 through 9 for the hundreds places. This totals twenty*10 + 100 = 300 of each digit required, leaving 999*2-300 = 1698 of each digit left.

So a pattern here is that to write all the numbers of $n$ and fewer digits, we need $req(10^{n-1}-1,1)*10+10^{n-1}$ of each digit other than zero. So where does this get close to $2n$?

Up to 9 (10^1-1):                          1
Up to 99 (10^2-1):              1*10+10 = 20
Up to 999 (10^3-1):          20*10+100 = 300
Up to 9999 (10^4-1):      300*10+1000 = 4000
Up to 99999 (10^5-1):                  50000
Up to 999999 (10^6-1):                600000
Up to 9999999 (10^7-1):              7000000
Up to 99999999 (10^8-1):            80000000
Up to 999999999 (10^9-1):          900000000
Up to 9999999999 (10^10-1):      10000000000
Up to 99999999999 (10^11-1):    110000000000
Up to 999999999999 (10^12-1):  1200000000000
...
Up to 9999999999999999999 (10^19-1):
Need 19000000000000000000
Up to 99999999999999999999 (10^20-1):
Need 200000000000000000000

So it is somewhere between $10^{19}-1$ and $10^{20}-1$ at the latest.

Here's a good summary of what we've determined so far. Keep in mind that digits required and digits left isn't accurate for zero because it follows a different pattern.

# balls   | digits req | digits left
------------------------------------
10^1  - 1 |  1 * 10^0  | 19*10^0 - 2
10^2  - 1 |  2 * 10^1  | 18*10^1 - 2
....................................
10^17 - 1 | 17 * 10^16 | 3*10^16 - 2
10^18 - 1 | 18 * 10^17 | 2*10^17 - 2
10^19 - 1 | 19 * 10^18 | 1*10^18 - 2
10^20 - 1 | 20 * 10^19 | 0*10^19 - 2

---

Looking at it a different way:

Since there have been some nice patterns so far, let's try looking at a different pattern that might give us the solution directly. What if we are only given one strip of digits in each kit? We can easily brute-force that with this Python code:

current = 1
available = [0]*10
while current < 200000000:
    current_str = str(current)
    for i in range(10):
        available[i] += 1 - current_str.count(str(i))
        if available[i] < 0:
            raise Exception('Done! %s has no more available at %s' % (i, current))
    current += 1

This tells us that for 1 strip we run out of 1's at 199991. This would take to long to calculate for 2 strips, but what about partial strips? That doesn't exactly make sense so let's say she has to get the strips from a vending machine for 10 cents each, and each kit has 11 cents in it. Then after opening 10 kits she buy an extra strip for 11 strips total. Let's change this line:

available[i] += cents_per_kit - cost_per_strip*current_str.count(str(i)) # cost_per_strip is 10

Here's a table of what this gives:

Strips/kit |       Result
-----------|-------------
    1.0    |       199991
    1.1    |      1999918
    1.2    |     19999198
    1.3    |    199991998

Each of these is for when we run out of 1's. This looks like a promising pattern that should continue as follows:

    1.4    |      199991998
    1.5    |     1999919998
    1.6    |    19999199998
    1.7    |   199991999998
    1.8    |  1999919999998
    1.9    | 19999199999998
    2.0    |199991999999998

Unfortunately, there must a break in the pattern here - 199991999999998 only takes two 1's, so we can cover that with what is included in the standard kit. What this does tell us, however, is that @Joel Rondeau and @FlorianF almost certainly have it right - they came up with 1,999,919,999,999,981, which is almost exactly what my pattern suggests.

---

Practical Answer:

She'll die long before she runs out of numbers. Also, she'd need a bigger bowl - one sheet of 8.5" by 11" paper weighs 0.04 lbs (according to Yahoo answers), and if the stickers are 2.5mm by 2.5mm (reasonably small), then each sticker weighs 4.5 milligrams. Right before ball $10^{19}$, she'll have about $10^{19}$ stickers left, which would weigh a total of $4.5*10^{13}$ kilograms. That's 45 billion tonnes. According to Wikipedia, that's one twelfth of the total live biomass excluding bacteria. And that's excluding all the balls and stickers on those balls. They're probably using Soylent Green stickers...

Edit:

As it turns out, the first time she'll run out is shortly before reaching $2*10^{15}$. Right before ball $10^{15}$ she'll have around $5*10^{15}$ leftover. Using the same approximations, this would end up being 22.5 million tonnes. She will have used $1.5*10^{16}$ stickers up to that point, which would weigh 67.5 million tonnes, for a total of 90 million tonnes of stickers. The Great Pyramid of Giza is estimated at 5.9 million tonnes, so she has almost 4 Great Pyramids worth of leftover stickers.

Answer 3

As noted before, the first digit to run out will be the 1's.

If you consider the units you use, you'll see that you use 1,2,3,...,9,0 and restart. At any time you'll have used the 1 before any other number. If you consider the tens, you see that you use 10x1, 10x2, ..., 10x9, 10x0. Again you'll use 1's before the other digits catch up. Since the supply is equal for all digits, you will always have less 1's than any other digit.

From there, I wrote a program.

An upper bound is ${10}^{20}-1$. Even with a computer it is too long to test every number up to that value. But you can skip whole ranges of numbers.

Numbers up to 99 pay for themselves. The strip that comes with it is enough. So 1 to 99 are safe.

Let's see for value 100: For 1..100 you need 21 1's. But you get 200 1's. This gives an excess of 179. Since you now produce 3-digit numbers, you will need no more than 3 1's per ball. 2 are provided by the strips, the 3rd is provided by the pool of 179 1's. So the next 179 are safe, that is up to 279. The next value to check is 280.

For 1..280 you will find an excess of 403 1's and you can safely jump to 683. The pool actually grows faster than you use it up.

When you reach 1000, you'll have to take 2 from the pool. But it still runs fast.

At some point, you will discover that you need more 1's than are provided, this stops the loop. Since you have always skipped safe numbers, you know that the last number is the first to need more 1's than are provided so far.

Here is the program that embodies the method described:

package stackexchange;

public class BallFactory
{
    /** Return the number of 1's needed to write number n */
    public static long onesIn(long n, int base){
        long count = 0;
        for( long k=n ; k>0 ; k/=base ){
            if( k%base==1 ) count++;
        }
        return count;
    }

    /** return the number of 1's needed to write numbers 1 to n */
    public static long sumOnesTo(long n, int base){
        long m = n/base;
        long count = (n+base-1)/base + ( m==0 ? 0 : sumOnesTo(m-1, base)*base + onesIn(m, base)*(n%base+1) );
        return count;
    }

    public static void solve(int base, int strips){
        // up to base^strips, each ball pays for itself
        long good = (long)Math.pow(base, strips);
        while( true ){
            long need = sumOnesTo(good, base);
            long excess = good*strips - need;
            System.out.println(String.format("%20d %20d %20d", good, need, excess));
            if( excess<0 ) break;
            long digits = (long)(Math.log(good)/Math.log(base))+1;
            good += excess/(digits-strips) + 1; // next uncertain number
        }
        // good is first to fail
        System.out.println("base " + base + " strips " + strips + ": " + good);
    }

    public static void main(String[] args)
    {
        solve(10,2);
    }

}

The last line of the output tells you:
For N = 1 999 919 999 999 981 you need 3 999 839 999 999 963 1's but you have a deficit of 1.
and you know that all numbers before are safe (You have more ones than you need).

Answer 4

Continuing on the from where Rob left off, when you label all the balls up to 10^20-1, you will have exactly -2 left of each digit 1-9, and a bunch of zeros. So, to find out the last ball you can successfully label, you need to simply "un-label" the last few balls until you make up the shortfall you have in every digit.

If we un-label the last ball "99999999999999999999", then we will recover 20 9s. Thus, we now have a surplus of 18 9s, but still are 2 short of every other non-zero digit. So, lets un-label 8 more balls, up to 10^20-9. We will end up recovering with 20*9=180 9s, and one of every other non-zero digit. But we still are at -1 of each of those digits, so we need to un-label 10 more. So, if we un-label up to 10^20-19, we will get a ton of 9s back, a handful of 8s (since the balls we just un-labeled ended in "89"-"81") and 2 of every other digit. This will make up our shortfall.

So, the last ball we can successfully label is 10^20-20, which is

99999999999999999980 

EDIT: With the help of the comments, I realized that this answer is wrong because when you "un-label" the last 19 balls, you have to re-package 19 kits, so you will lose 38 of each digit.

Working backwards from this point doesn't seem any easier than working forwards, so I will have to think on it a bit more.

Answer 5

The below table shows what happens in various brackets of balls. Used shows the stickers used for those balls, received shows the number that came with the balls, and left is the number left at the end of the bracket. We come two stickers short at $11,111,111,111,099,999,999$, so that is the first ball she can't label.

$$\begin {array} {r r r r r}Start&End&Used&Received&Left\\1&1E19-1&1.9E19&2E19-2&1E18-2\\1E19&1.01E19-1&2.7E17&2E17&93E16-2\\1.01E19&1.02E19-1&3.7E17&2E17&76E16-2\\1.02E19&1.1E19-1&21.6E17&16E17&20E16-2\\1.1E19&1.101E19-1&3.6E16&2E16&18.4E16-2\\1.101E19&1.102E19-1&4.6E16&2E16&15.8E16-2\\1.102E19&1.11E19-1&28.8E16&16E16&3E16-2\\1.11E19&1.111E19-1&4.6E16&2E16&4E15-2\\1.111E19&1.1111E19-1&5.5E15&2E15&5E14-2\\1.1111E19&1.11111E19-1&6.4E14&2E14&6E13-2\\1.11111E19&1.111,111E19-1&7.3E13&2E13&7E12-2\\1.111,111E19&1.111,111,1E19-1&8.2E12&2E12&8E11-2\\1.111,111,1E19&1.111,111,11E19-1&9.1E11&2E11&9E10-2\\1.111,111,11E19&1.111,111,111E19-1&10E10&2E10&E10-2\\1.111,111,111E19&1.111,111,111,1E19-1&11E9&2E9&E9-2\\1.111,111,111,1E19&1.111,111,111,11E19-1&12E8&2E8&-2\end {array} $$

Answer 6

Actually, it is entirely possible that she ran out of stickers before labelling the 10^19-1 ball.

Note that if you split a range up into groups of 10, you will see that the leading digit is required about more often then other digits within that range. For example:

Range        1    2  ...   9    0
1-9          1    1  ...   1    0
10-19       11    1  ...   1    1
100-199    120   20  ...  20   20
1000-1999 1300  300  ... 300  300

So, consider the point where have just finished labelling the 10^18-1 th ball. We are now in this situation:

Digits 1-9 used:      1,800,000,000,000,000,000 = 1.8 * 10^18
Digits 1-9 remaining:   199,999,999,999,999,998 = 2 * 10 ^ 17 - 2

If we want to label the next 10^18 balls, we will need 1,800,000,000,000,000,000 (1.8 * 10^18) more of each digit. Since all those numbers start with the digit 1, we will also need 10^18 additional ones, so we will need a total of 2.8 * 10^18 more ones to label these balls. However, we don't have that all in reserve - we only have about 1/10th of that.

Summary:

Range: 10^18 - 2 * 10^18 - 1
       1,000,000,000,000,000,000 - 1,999,999,999,999,999,999
Ones required: 2,800,000,000,000,000,000
Ones reserve:    199,999,999,999,999,998
Ones accrued:  2,000,000,000,000,000,000
Short:           600,000,000,000,000,002

So, we have actually run out of ones before 10^19.