The Lottery Ball Factory

Hawkeye

<div class="IPBDescription">Math Savvy Beware!</div>Okay, someone told me a nice math problem the other day and I thought I'd share it. If you know the answer already, don't spoil it for others. If you post an answer, write the answer in spoiler tags, though your proof you can leave outside spoiler tags without any problems. Without further ado:

You work at a factory which creates lottery balls, the ones they draw from a cage on a random basis.

You are given the instructions to unwrap a package with the following contents: a ball and two strips of number stickers from 0 to 9. Your task is to place the stickers on the ball to create the numbers starting from 1 and then up. However, the stickers you do not use in that package, you place aside to use later. So for example, I start by taking the '1' sticker and placing it on the ball, and the 0, 2, 3, 4, 5, 6, 7, 8, 9 and the other 0 - 9 number sticker strip go to a pile. Then I open another package and I take the '2' sticker and place it on the ball, placing the 0, 1, 3, 4, 5.. and the other 0 - 9 number sticker to the same pile.

At what point do I run out of numbers using this system? I'll give you a hint, it's not a small number. <img src="style_emoticons/<#EMO_DIR#>/smile-fix.gif" style="vertical-align:middle" emoid=":)" border="0" alt="smile-fix.gif" />

Have fun!

Hawkeye

I was thinking about it, and the big picture is this:

If f0(n) represents the number of 0s used from numbers 1 to n, f1(n) represents the number of 1s used from numbers 1 to n, etc.,

Then the solution is when the maximum value of f0(n), f1(n), f2(n),... f9(n) = 2*n.

That is to say, when the average use of one of the numbers from 0 through 9 is greater than 2 for a number n (you get 2 of each number for every number you make), you've found your answer.

So all there is left to do is figure out the formulas for f0(n) ... f9(n) and solve for n.

So what is f0(n)?
f0(0) = 1
f0(1) = 1
f0(2) = 1
...
f0(10) = 2
f0(11) = 2
...
f(99) = 10
f(100) = 12

So something like floor(n / 1000) + floor(n / 100) + floor(n / 10) + 1 = f0(n).

Am I gibbering here or is that making any sense to anybody?

lolfighter

If there are 36 numbers in the lottery, for instance, you will only need to label balls from 1 to 36. We can assume that once you're done with that, you'll simply start over. Now, since for each ball you label, you get 20 numbers (0-9 x 2) to work with, and you only use two of those for each balll, you will never run out of numbers. Your stack of numbers will keep growing until <catastrophic event> occurs.

Thansal

it took me a few read throughs to get it, but I think that what he meant is:

Start at 1 and go as high as you can until you run out of numbers. You will eventually run out of stickers once you are in the multiple thousands (or possibly millions or higher, I don't know).

My math isn't up to snuff for this, and I don't feel like figuring it out.

Hawkeye

<!--quoteo(post=1689775:date=Oct 9 2008, 04:17 AM:name=lolfighter)--><div class='quotetop'>QUOTE(lolfighter @ Oct 9 2008, 04:17 AM) <a href="index.php?act=findpost&pid=1689775"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->If there are 36 numbers in the lottery, for instance, you will only need to label balls from 1 to 36. We can assume that once you're done with that, you'll simply start over.<!--QuoteEnd--></div><!--QuoteEEnd-->
Well the question is at what point will I run out of numbers using this system. I never said it stops at 36 (where did you get that number from anyway?)

If anything isn't clear, ask and I'll clarify.

eediot

e: deleted

eediot

e: deleted

Thansal

it is a dumbly worded question, the real one is this:

An even takes place, the event includes:
1) the right to use 2 sets of 0-9
2) using your pool of numbers to create n+1 (where n is the number used in the last event)

n originates at 1.

How many events before you can not create n+1 with your current pool?

no limits, nothing like that, ignore the stupid lotto ball bit (after all, lotto balls have have at least 2 numbers on them, generally 6 or more).

It is a math question, state it as such.

lolfighter

The 36 is pure fabrication.


I think I get what the problem is. It's not an infinite bucket, it's consecutively larger buckets. In terms of buckets, it's kinda like this:

"You have to fill buckets. Each bucket is larger than the previous. Each time you get a bucket, you also get a fixed quantity of water, X. Any water you don't need can be stockpiled. At some point, the amount of water that the buckets can hold exceeds X. When do you run out of water?"


From what I understand, we just label the balls consecutively, with no upper limit. We simply continue until we run out of numbers to label balls with. When labeling a ball, we use the numbers on the strips that come with it. Any unused numbers go into the stockpile. If the strips are not sufficient to label a ball, we dig into our stockpile.
Any number with less than twenty digits will net us an increase to our stockpile. Any number with more than twenty digits will net us a decrease. Thus, until we reach twenty digits, our stockpile will continue to increase in size. Once we are past twenty digits it will decrease in size, until we run out. The point is to figure out when we run out.

Is this correct?
Also, are we doing your math assignment for you? <img src="style_emoticons/<#EMO_DIR#>/tounge.gif" style="vertical-align:middle" emoid=":p" border="0" alt="tounge.gif" />

Hawkeye

Why? Seem like a math assignment? Hah. I wish I had math problems like these in high school.

There is no upper bound. If you prefer to drop the lottery ball factory bit, fine by me.

I understand that maybe the wording is a little hard to get and I apologize. I mean to say that at some point, you're making numbers 21 digits long (for example.. don't assume I mean to say the answer is necessarily greater or less than a number with 21 digits) which consume 21 numbers each from your pile and from the two strips of number stickers you opened. You're no longer gaining numbers but losing them one at a time. However, if the problem were as simple as figuring out when 20 * n = log10(n), the solution would already be quick to solve.

lolfighter, I think you've got it right. When you make a single number and you do not have enough of that number from the two strips or from the pile, that number is your answer. So obviously the number could never contain less than three of any single number since you gain two of every digit for every number you need to form. Does that make any sense?

lolfighter

Yeah, the problem is obviously a lot more complex than the bucket one. The bucket example is comparatively simple: Single resource to keep track of. You gain a static amount each iteration, and have to expend a dynamic, ever-increasing amount each iteration.

In the lotto ball example, on the other hand, you have ten different resources to keep track of, and resource requirements change from one iteration to another in a complex manner. Lot more difficult to work with.

I briefly thought about going the cheeky route and writing a program to brute-force the problem rather than bothering with doing any real math, but I quickly realised my computer would run out of memory long before getting anywhere.

That being said, I also have no intention of solving this mathematically. I hereby pass the buck.

Cxwf

We started working on the problem over <a href="http://www.unknownworlds.com/ns2/forums/index.php?s=&showtopic=104727&view=findpost&p=1689687" target="_blank">here</a>, before deciding it was way off-topic for the thread it was in. I don't have an answer yet, but I think you most likely run out of ONE digits somewhere between <span style='color:#000000;background:#000000'>1.9x10^16th and 2.0x10^16th</span>.

If you want to brute-force the problem, you could take a shortcut and start at the number I calculated up to. =p

lolfighter

That wouldn't really work, since I don't know what the contents of your stockpile are. That's also why brute-forcing won't work at all: The stockpile of numbers will be enormous at its apex.

Actually, it might work, but I'd have to swap stuff in and out of memory. It'd also take forever to calculate. All in all, I REALLY can't be arsed.

buck.pass();


Edit: I might be overcomplicating things, and it might actually be brute-forcable with (under the circumstances) rather moderate memory overhead. I STILL can't be arsed though. But if anybody does want to take this rule, start by figuring out how the contents of the stockpile change over time, and whether it can be stored more efficiently than simply as a collection containing the entire contents of the stockpile.

Cxwf

I've already done that. First of all, I'm nearly certain that you only have to track your supply of a single digit, the ONE digit, because that will be the first one to run out. Secondly, while I haven't figured out how to write a generic formula for how many 1s are consumed over a range, I can tell you how many 1s have been consumed vs supplied at any particular number. But its an iterative process that works best when most of the digits in your number are trailing zeros, which is why I've only calculated it to 1.96E16 so far. My suspicion is that the correct answer will be something like <span style='color:#000000;background:#000000'>1999991111111111</span>, or something of that form.

Cxwf

Actually, I think it might be easier to work backwards from here. We know that at exactly 2.0x10^16th, 4.0x10^16th ONEs have been used up, which is the same number that have been supplied. One number before that, we had one less demand and two less supply, so our reserve had to be -1, meaning we must have actually run out of numbers some time ago. So how many numbers backwards must we count from 2.0x10^16th to use up the same amount that we have supplied?

This time we can ignore the leading 1 on all those numbers for simplicity, and just assume our supply is a single 1 instead of two of them. There's a lot of digits cycling, but most of them are 9s which can be ignored. If we count back 10 numbers, the 1 farthest right column has cycled through 1 ONE. If we count back 100 numbers, the 2 farthest right columns have each cycled through 10 ONEs. 1000 numbers, the 3 right columns have each cycled through 100 ONEs.

Lets jump to 1x10^9th numbers backwards. Hold on...did I just make a math error? Damnit, I think I dropped an entire column in my earlier calculations that got me to 2.0x10^16th. Give me a minute to go over those numbers again.

This, by the way, is the danger of working with numbers too large to write down efficiently.

Cxwf

Ok, I think I'm safe. I correctly identified the 16-digit number as the number of interest, but then attempted to write that as 1.0x10^16th when a 16-digit number should really be 1.0x10^15th. I think all further errors are self-correcting as soon as you replace 10^16th with 10^15th.

So yes, 1.0x10^9th backwards from 2.0x10^15th. At this point, 9 columns have cycled through 1.0x10^8th ONEs, giving 0.9x10^9th consumed and 1.0x10^9th supplied. Close.

How about 1.0x10^10th backwards? At this point, 10 columns have cycled through 1.0x10^9th ONEs, giving 1.0x10^10th consumed and 1.0x10^10th supplied. We have found an equilibrium point! For each 1.0x10^10th we step back, we used the same number that we supplied. But we aren't quite done yet, because that gives us several different points where supply = demand, and we want the FIRST point. Anyone up for the next step?

Hawkeye

It hurts my head to rationalize that way.

I'd just assume search for a diamond of the size of a grain of sand amongst the beaches of the world.

Don't you think it'd be easier to match formulas?

Cxwf

You have a formula? By all means, share please!

Having determined that 1.0x10^15 - 1.0x10^10 is an equilibrium point, I would think the next step is fairly clear. It remains in equilibrium only as long as the 11th digit is not a ONE, so 1.0x10^15 - 8.0x10^10 (aka 1,999,920,000,000,000) should be the first one of this type. Stepping back one more transition gives 1,999,910,000,000,000, and that transition consumes an extra leading ONE on each number, meaning we must have first crossed equilibrium somewhere in that range.

How far back are we at 199991E10? During that period we cycle through 1x10^10 numbers, yielding 1x10^9 ONEs in 10 columns to the right, plus our two leading ONEs which exactly offset the supply. So at 199991E10, we have exactly 1x10^10th spare ONE digits. But how fast do we consume those?

At this point we don't have to worry about our supply increasing, since that's exactly offset by our two leading ones. *thinks* Actually that makes it easy. Since our supply always decreases in this area, never increases, and we know it hits exactly 0 at the end, then it can't possibly <i>cross</i> 0 until it hits the end -- with one exception. The very last number in the range is 1999992E10, and that number gives us a net +1 ONE digit, with leaves us with exactly 0 spares. So the most recent previous number at which we consumed a ONE digit is our answer. And that is...

*drumroll*

<span style='color:#000000;background:#000000'>1,999,919,999,999,991</span>

Xyth

Cxwf while I understand your logic that number doesn't seem correct to me. That would imply that you've used nearly 4,000,000,000,000,000 1s stickers. I'm thinking the actual number is much lower, though I could just be thinking about it the wrong way. Regardless, I'm going to split the problem into two graphs (one graph for the number of 1's available to you, y = 2x and the second graph will compare the number of 1s required to reach any number. That last one is proving a bit difficult but (hopefully) not impossible) then just compute where graph 2 crosses graph 1. Ill check back later with what I can come up with.

CrystalSnake

If my calculations are correct, you'll run out of stickers when you reach 21-digit numbers (or earlier, it's only an upper bound).
Am I close to being correct?

Cxwf

@Xyth: Yes, I do think you've used nearly 4,(large number of zeros) ONE stickers. Tell me what you come up with, but that second function is remarkably hard to describe mathematically.

@Crystal: You are coming to the same upper-bound that I came to, but the upper-bound in this case is not particularly useful because you have 10 different resources which run out at different rates, and one of them is likely to run out significantly before the other nine.