Puzzle time - the ant lottery
-
You have been asked to choose the winner in this year’s ant lottery. To enable you to do this, an arbitrarily long line of ants will parade past you. Each ant will wear an identification tag with a unique integer. You do not know how many ants there will be, but there may well be too many ants for you to record all their identification numbers. When the parade is over, you will announce the identification number of the ant you have chosen. You must make your choice with uniform probability — that is, no ant may be more likely to be chosen than any other ant. You have at your disposal a special calculator that, given a positive integer k, will choose an integer from 1 to k uniformly at random. How do you proceed?
-
Well you get to see them all.
And you have this one tool.
The ant lottery sub-plot is just there to improve the ratings.
@jon-nyc said in Puzzle time - the ant lottery:
Well you get to see them all.
In other words you can’t choose a number you didn’t see. Then the problem would be trivial.
-
@jon-nyc said in Puzzle time - the ant lottery:
Well you get to see them all.
In other words you can’t choose a number you didn’t see. Then the problem would be trivial.
@jon-nyc said in Puzzle time - the ant lottery:
@jon-nyc said in Puzzle time - the ant lottery:
Well you get to see them all.
In other words you can’t choose a number you didn’t see. Then the problem would be trivial.
What does “maybe too many for you to record” from the original statement mean?
Education is extremely important.
-
-
I think it’s ruling out the idea that you capture the highest number and run it through your random number generator until it selects a participating ant.
@jon-nyc said in Puzzle time - the ant lottery:
I think it’s ruling out the idea that you capture the highest number and run it through your random number generator until it selects a participating ant.
But how would you know when to stop, that is, when you’ve hit a number that occurred on a tag? You mean when you have the full list, right?
-
@jon-nyc said in Puzzle time - the ant lottery:
@jon-nyc said in Puzzle time - the ant lottery:
Well you get to see them all.
In other words you can’t choose a number you didn’t see. Then the problem would be trivial.
What does “maybe too many for you to record” from the original statement mean?
@horace said in Puzzle time - the ant lottery:
@jon-nyc said in Puzzle time - the ant lottery:
@jon-nyc said in Puzzle time - the ant lottery:
Well you get to see them all.
In other words you can’t choose a number you didn’t see. Then the problem would be trivial.
What does “maybe too many for you to record” from the original statement mean?
If there’s a fixed space limit - say, 1000 digits- then one may not even be able to write down a single Identifier. They could all be bigger than the limit.
The nature of that limit seems pretty vague. Is it a fixed number of identifiers? A fixed number of digits? Is its size predetermined or can I choose the size? Or is the only purpose of that statement to rule out the "record every identifier" strategy and otherwise there are no limits? I assume it is the latter.
-
@klaus said in Puzzle time - the ant lottery:
I wonder what the significance of the “integer” tag (as opposed to natural number) is.
In my solution it doesn’t matter what you use to label individual ants. Could be letters and numbers, whatever.
-
:::
The simple case for one ant is that the first ant has a 100% chance of winning. The case for two ants is that you roll a 50/50 shot for whether that new ant wins, and if not the current winner wins. This leaves a 50/50 shot for each ant. Third ant, you roll a 1/3 shot for it to win, if not then the current winner stands. Those two first ants each had a .5 chance to be the current winner, and now that the third ant might be the winner, they have a .5 * 2/3 chance, or 1/3, just like the third ant. Fourth ant comes along, it is given a 1/4 chance of winning, and if it doesn't, the current winner stands, who had a 1/3 * 3/4 chance of being winner, or 1/4. And so on...
:::
-
Yep.
:::
I worked backwards from the last ant. She needs a 1/n chance. Second to last would have had her 1/(n-1) chance followed by a (n-1)/n chance. From there I generalized to ant k and saw that the pattern holds.
:::
-
Yep.
:::
I worked backwards from the last ant. She needs a 1/n chance. Second to last would have had her 1/(n-1) chance followed by a (n-1)/n chance. From there I generalized to ant k and saw that the pattern holds.
:::
@jon-nyc said in Puzzle time - the ant lottery:
Yep.
:::
I worked backwards from the last ant. She needs a 1/n chance. Second to last would have had her 1/(n-1) chance followed by a (n-1)/n chance. From there I generalized to ant k and saw that the pattern holds.
:::
When the puzzle author found themselves with a trivially solvable problem scenario and had to add that kludge about not being able to record all the ant IDs, that's when they should have re-thought the whole scenario and found a better one that didn't have a trivial solution.
-
Horace's solution makes sense, but I also think the description is confusing and overly complicated.
@klaus said in Puzzle time - the ant lottery:
Horace's solution makes sense, but I also think the description is confusing and overly complicated.
How about the objective is to take a picture of the winning ant, but your digital camera has storage for only one picture, which can be overwritten any number of times with a new photo.
-
@klaus said in Puzzle time - the ant lottery:
Nice idea!
Thanks Klaus. Another problem with not being able to record the ID of every ant is that the solution assumes a non zero chance of having to record every ant, as the interim lottery winner.
