18
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I strongly suspect that the digit that causes the problem will be 1. It's always the first used in a particular digit place, and otherwise it's used no less than any other digit. $\endgroup$ – TheRubberDuck Sep 23 '14 at 16:40
  • $\begingroup$ I am not perfect in English, so I did not get the point. what option do she have? Doesn't she have to write an specified sequence of numbers? $\endgroup$ – Rafe Sep 23 '14 at 16:59
  • 1
    $\begingroup$ @Rafe I don't think she is making any decisions - she must number the balls 1, 2, 3, ... until she can't anymore. My understanding is that the puzzle is to figure out when she runs out of "stickers" to put on the balls. $\endgroup$ – TheRubberDuck Sep 23 '14 at 18:34
  • $\begingroup$ Yeah, it seems like it is vastly more Math than Puzzle, but there should still be a single ball that she can't create digits of. She has 1 of every digit per ball (1*B, 2*B, ... 9*B where B = ball she is on) $\endgroup$ – Xrylite Sep 23 '14 at 19:46
  • $\begingroup$ @Rafe No options. She just has to number the balls, essentially. Each ball has a number one higher than the last. When will she not be able to continue doing so? $\endgroup$ – Neil Sep 23 '14 at 20:15
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You're right, it is an upper bound, but this isn't the answer. $\endgroup$ – Neil Sep 24 '14 at 17:44
  • $\begingroup$ But I find the same answer. $\endgroup$ – Florian F Sep 24 '14 at 21:24
  • $\begingroup$ Look at the "Looking at it a different way" section that I added to my answer. The pattern I found suggests rather strongly that you've both got the right answer. $\endgroup$ – Rob Watts Sep 24 '14 at 21:51
  • $\begingroup$ Yes. I'd guessed that but still had a couple things I wanted to try. $\endgroup$ – Joel Rondeau Sep 24 '14 at 21:56
  • 2
    $\begingroup$ @Neil, if you hover over the time stamp by the poster's name at the bottom right of the answer (eg where it says "answered yesterday" or "answered 22 hours ago" or whatever), it tells you the actual timestamp in a tooltip. So you can see precisely who was first. $\endgroup$ – Vicky Sep 25 '14 at 15:23
13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It's interesting to note that 10^20 is a "break even" point... that is, if she could borrow stickers from a coworker, she would just have covered her debt upon opening the 10^20th box (although that ball would be left un-stickered). She would have exactly 1 unstickered ball and 0 unstuck stickers. $\endgroup$ – TheRubberDuck Sep 23 '14 at 20:23
  • 1
    $\begingroup$ @EnvisionAndDevelop That is interesting. Of course, she'd still have (literal) tons of zeros left over. $\endgroup$ – Rob Watts Sep 23 '14 at 21:35
  • $\begingroup$ Wow, you're right. I haven't been considering how many zeros she isn't using. Each column "skips" what would be its first round of zeros, because we never write leading zeros. $\endgroup$ – TheRubberDuck Sep 24 '14 at 12:45
  • $\begingroup$ Very clever of you to use use "partial" strips (not sure I fully understand how you did that). The pattern that emerges is the correct one. Very well done. $\endgroup$ – Neil Sep 25 '14 at 7:44
  • $\begingroup$ Yes. It looks like a crazy idea but the result is convincing. $\endgroup$ – Florian F Sep 25 '14 at 9:33
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Well done. I'm not sure who to give credit to though, since also @Joel got it right. Which one of you had the right answer first? I'll trust you at your word. $\endgroup$ – Neil Sep 25 '14 at 7:39
  • $\begingroup$ Joel Rondeau gave the answer first. $\endgroup$ – Florian F Sep 25 '14 at 9:29
  • $\begingroup$ I think I will have to credit him for it, then. However, I am sure you found the solution on your own in any case. $\endgroup$ – Neil Sep 25 '14 at 12:35
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I commend you for your reasoning, but the answer is wrong. This may be because of Rob's false idea that at 10^20-1 you run out of digits. Remember you've been saving them all this time. $\endgroup$ – Neil Sep 24 '14 at 15:41
  • 1
    $\begingroup$ My numbers simply show that if she borrows numbers whenever she doesn't have any, then at 10^20-1 she will have a debt of two of each digit 1-9. So it's just an upper limit. Going backwards from there gives you no guarantee that there wasn't a previous point at which she ran out, had to borrow, and then was able to repay the debt. Also, this answer fails to account for decrementing the number of stickers available for each ball unlabeled. $\endgroup$ – Rob Watts Sep 24 '14 at 15:58
  • $\begingroup$ @RobWatts You are right. I failed to take into account that by unlabelling 19 balls, she has to give back 38 of each digit, so she again has a deficit - in fact a bigger one than before. $\endgroup$ – Trenin Sep 24 '14 at 16:19
1
$\begingroup$

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} $$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I was suspecting that this would be the case - I've only been looking at patterns and establishing some upper bounds $\endgroup$ – Rob Watts Sep 24 '14 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.