You have a bag of 1 million balls, each uniquely numbered from 1 to 1 million.
You reach into the bag blindly (ie. without looking) and take out a ball. You write down the number of the ball.
You repeat this 19 more times, so that, at the end, you have a list of 20 numbers written down.
What's the probability that you have written down a list of ascending numbers?
A first very rough guess would be that it would likely be no more than 2 in a million
That’s assuming a 50% chance of each subsequent number being higher
(so 0.5 ^ 19)
Of course that probability would start at some percentage, which could be greater or less than 50%, based on the first number drawn, and the probability on subsequent draws would decline, after a successful draw of a larger number, as each subsequent number increases
a quick thought at the end of lunch is that the available pool of numbers on average is cut in half each time you draw so the answer is something like 1*1/2*1/4*….. 1/2^(n-1)
I believe I have the answer here. I showed my work this time (although I don't have a proof) so would welcome comments if anyone thinks I'm way off base.
Spoiler!
I can't initially solve this problem so I made a simpler problem and solved that to start thinking about it.
The image shows the odds for a bag of 6 balls with 3 pulls. The number in brackets is the odds of success for a given combination of 2 pulls. The T shows success after 2 pulls and the F a failure after 2 pulls.
By way of example, the yellow cell is pulling a 3 on ball one and a 5 on ball two. In that scenario, there are 4 balls remaining (1,2,4,6) and only one of them (6) is a successful set of three ascending numbers. So the odds of success after that initial combination are 1/4. The odds of any initial combination is 1/30, so we can multiply the figure in each cell by 1/30 and add the answers up to get the odds in total. That gives us 20/120 or 1/6 reduced, but I think keeping it as 20/120 is more useful for thinking about the answer.
The denominator is 6*5*4, which makes sense, and I'd expect that pattern to hold for the actual problem, so it should be 1,000,000! / (1,000,000-20)! as the denominator. Roughly the only thing I remember from taking stats/probability is that there were lots of factorial signs everywhere, so that's a good place to start.
Edited to add: I repeated this exercise with 7 balls choose 3 and 8 balls choose 3. I got 35/210 and 56/336 respectively. I think it's pretty unlikely to be a coincidence that those all reduce to 1/6.
There's a pattern there, and it would need more work to prove it, but my thought is 1/(20!), as with 3 balls no matter how many in the bag I got 1/(3!), and with 2 balls the answer is trivially 1/(2!).
Edited to add again: I repeated the problem as 6 balls choose 4, and got 15/360 = 1/24 = 1/(4!), which is pretty confirmatory to me. I've changed my mind about the denominator being relevant, and think the answer here is solely dependent on the number of balls you pull (assuming the number of balls is greater than number of pulls) and so for the problem as stated it's 1/(20!)
I believe I have the answer here. I showed my work this time (although I don't have a proof) so would welcome comments if anyone thinks I'm way off base.
Spoiler!
I can't initially solve this problem so I made a simpler problem and solved that to start thinking about it.
The image shows the odds for a bag of 6 balls with 3 pulls. The number in brackets is the odds of success for a given combination of 2 pulls. The T shows success after 2 pulls and the F a failure after 2 pulls.
By way of example, the yellow cell is pulling a 3 on ball one and a 5 on ball two. In that scenario, there are 4 balls remaining (1,2,4,6) and only one of them (6) is a successful set of three ascending numbers. So the odds of success after that initial combination are 1/4. The odds of any initial combination is 1/30, so we can multiply the figure in each cell by 1/30 and add the answers up to get the odds in total. That gives us 20/120 or 1/6 reduced, but I think keeping it as 20/120 is more useful for thinking about the answer.
The denominator is 6*5*4, which makes sense, and I'd expect that pattern to hold for the actual problem, so it should be 1,000,000! / (1,000,000-20)! as the denominator. Roughly the only thing I remember from taking stats/probability is that there were lots of factorial signs everywhere, so that's a good place to start.
Edited to add: I repeated this exercise with 7 balls choose 3 and 8 balls choose 3. I got 35/210 and 56/336 respectively. I think it's pretty unlikely to be a coincidence that those all reduce to 1/6.
There's a pattern there, and it would need more work to prove it, but my thought is 1/(20!), as with 3 balls no matter how many in the bag I got 1/(3!), and with 2 balls the answer is trivially 1/(2!).
Edited to add again: I repeated the problem as 6 balls choose 4, and got 15/360 = 1/24 = 1/(4!), which is pretty confirmatory to me. I've changed my mind about the denominator being relevant, and think the answer here is solely dependent on the number of balls you pull (assuming the number of balls is greater than number of pulls) and so for the problem as stated it's 1/(20!)
Some really good work here. When you see the solution, it will be like an epiphany. Everything will click and make sense.
Some really good work here. When you see the solution, it will be like an epiphany. Everything will click and make sense.
Keep working away!
Are you sure that answer isn't correct?
Spoiler!
So are you saying it isn't the 1/(20!) I suggested above?
I really think it is. Aside from the pattern I found earlier (which I did run again and it holds), it sort of makes sense. Any group of 20 numbers without repetition can be arranged in 20! different orders, and only one of those orders can be ascending.
Edited to add:
Am I using the ! symbology wrong? The number I mean to suggest as the answer is
So are you saying it isn't the 1/(20!) I suggested above?
I really think it is. Aside from the pattern I found earlier (which I did run again and it holds), it sort of makes sense. Any group of 20 numbers without repetition can be arranged in 20! different orders, and only one of those orders can be ascending.
Edited to add:
Am I using the ! symbology wrong? The number I mean to suggest as the answer is
I'll have to puzzle it some more, but I honestly don't see where I'm mistaken here...
Sorry, yes - the answer you came up with was correct. But your reasoning was based on some grunt work and seeing patterns. It wasn't a real proof.
The actual proof, however, you've actually just come up with in the above reply:
Spoiler!
In a sense, this is another misdirection problem. It's easy to focus on the events (removing a ball from the bag) and look at how the probabilities change as each ball is removed.
But the elegant way is to realize that at the end of the day, you end up with a sequence of 20 numbers and, as you mentioned above, only one sequence of those 20 numbers is in strictly ascending order.
As there are 20! ways to arrange the 20 numbers, the probability that they are in ascending order is 1/20!
Generalizing, if you remove n balls from a bag of m balls (where n <=m) the probability that you've removed them in ascending order is 1/n!
The Following 3 Users Say Thank You to psyang For This Useful Post:
Sorry, yes - the answer you came up with was correct. But your reasoning was based on some grunt work and seeing patterns. It wasn't a real proof.
The actual proof, however, you've actually just come up with in the above reply:
Spoiler!
In a sense, this is another misdirection problem. It's easy to focus on the events (removing a ball from the bag) and look at how the probabilities change as each ball is removed.
But the elegant way is to realize that at the end of the day, you end up with a sequence of 20 numbers and, as you mentioned above, only one sequence of those 20 numbers is in strictly ascending order.
As there are 20! ways to arrange the 20 numbers, the probability that they are in ascending order is 1/20!
Generalizing, if you remove n balls from a bag of m balls (where n <=m) the probability that you've removed them in ascending order is 1/n!
Gotcha, sorry, misunderstood what you were saying there. I quite like the method of making a problem simpler until I can solve it, and then finding patterns to converge on the answer, but that also might be a flaw in how my brain works! I did generalize the solution in my first reply. Also interesting that you would consider the second reply a proof - I suppose it is, although it lacks the 2 columns and q.e.d. at the end from the proofs I recall studying. Anyway, thanks for posting this one! I enjoyed it, and probability is (imo) the most underrated area of mathematics, because the world is both not very black and white AND more predictable than people realize, and so (once again imo) thinking in terms of probability is useful.
Spoiler!
You are correct about the misdirection- if you had said "take 20 balls with numbers and arrange at random, what are the odds they are ascending" I never would have simplified the problem (both because I would have seen the answer and because someone else would have solved it first)
And pedantically, you didn't ask for a proof, just the probability of that happening
Gotcha, sorry, misunderstood what you were saying there. I quite like the method of making a problem simpler until I can solve it, and then finding patterns to converge on the answer, but that also might be a flaw in how my brain works! I did generalize the solution in my first reply. Also interesting that you would consider the second reply a proof - I suppose it is, although it lacks the 2 columns and q.e.d. at the end from the proofs I recall studying. Anyway, thanks for posting this one! I enjoyed it, and probability is (imo) the most underrated area of mathematics, because the world is both not very black and white AND more predictable than people realize, and so (once again imo) thinking in terms of probability is useful.
A proof doesn't have to be a specific format, but I guess what I'm looking for is an explanation for why the solution is correct. Originally, you based your solution on a pattern from a few simpler examples. But who's to say the pattern doesn't break down when examples become larger/more complex.
I called what you wrote in the previous reply a proof simply because it got to the heart of the solution - the reason why the solution was correct, and it was not dependant on specific examples, but applies to the general case.
Anyways, really happy that you (and others) are enjoying these problems. I'll keep posting as long as I keep coming across good ones!
Quote:
Spoiler!
You are correct about the misdirection- if you had said "take 20 balls with numbers and arrange at random, what are the odds they are ascending" I never would have simplified the problem (both because I would have seen the answer and because someone else would have solved it first)
100% agree.
Quote:
And pedantically, you didn't ask for a proof, just the probability of that happening
Yeah, consider that implied from now on . The beauty of the problems isn't so much the answer, but the cleverness of how they are answered.
The Following User Says Thank You to psyang For This Useful Post:
Rear tire will follow a lesser angle than front tire, so the tighter curve is the front (steering) tire.
The right to left the rear tire starts turning before the steering tire, but the left to right it follows after the steering tire.
I understand the first part regarding the "lesser angle".
Can you be clearer on the second part? How do you tell that the rear tire turns *before* the steering tire when travelling right-to-left? And if it does turn before the steering tire, doesn't that mean that is the wrong direction? Shouldn't the rear tire turn after the steering tire?
If the bike were going left-to-right, the lines would not cross over on the right side. Also, maintaining a constant distance between the lines, it becomes almost impossible to follow the path - the rear tire has to reverse itself or at least stop for a long time. Attempting such a manoeuvre would likely result in a crash (though still a really abrupt turn going right-to-left as well).
If the bike were going left-to-right, the lines would not cross over on the right side. Also, maintaining a constant distance between the lines, it becomes almost impossible to follow the path - the rear tire has to reverse itself or at least stop for a long time. Attempting such a manoeuvre would likely result in a crash (though still a really abrupt turn going right-to-left as well).
I think you've come closest to really articulating why the bike has to be moving right-to-left. There is a particular concept/idea I'm going for here that could be applied to any such tracks to determine the bike's direction.
. The beauty of the problems isn't so much the answer, but the cleverness of how they are answered.
<-----Check the Badge bitches. You want some Awesome, you come to me!
