Insanely Hard High School Math Question - Online Math Olympiad Apple Tree Probability
Вставка
- Опубліковано 23 вер 2024
- The Online Math Olympiad is a contest for high school students with challenging problem. This 2016 test had an average score of 9 out of 30. This video is an adaption of problem 16 which is an interesting probability puzzle. At the end of day 0, six magical seeds are planted. On each day following, each seed has a chance to magically transform into an apple tree with a probability of 1/2. Once a seed transforms into an apple tree, it stays an apple tree and survives indefinitely. What is the expected number of days until all six seeds have become apple trees? Can you figure it out?
Thanks to:
Arbitrary Renaissance ( / explosivebrohoof ) for suggesting the problem and writing up a solution to fill in details from the official solution.
My blog post for this video:
wp.me/p6aMk-5oy
Source
Adapted from Fall 2016 OMO Problem 16: internetolympia...
Online Math Olympaid homepage:
internetolympia...
Alex Knudson derivation of solution using Markov chains
allmathsconside...
If you like my videos, you can support me at Patreon:
/ mindyourdecisions
Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.
My Blog: mindyourdecisi...
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.co...
Pinterest: / preshtalwalkar
Tumblr: / preshtalwalkar
Instagram: / preshtalwalkar
Patreon: / mindyourdecisions
Newsletter (sent about 2 times a year): eepurl.com/KvS0r
If you buy from the links below I may receive a commission for sales. This has no effect on the price for you.
My Books
"The Joy of Game Theory" shows how you can use math to out-think your competition. (rated 3.8/5 stars on 31 reviews)
amzn.to/1uQvA20
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 5/5 stars on 2 reviews)
amzn.to/1o3FaAg
"Math Puzzles Volume 1" features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 13 reviews.
amzn.to/1GhUUSH
"Math Puzzles Volume 2" is a sequel book with more great problems. (rated 5/5 stars on 3 reviews)
amzn.to/1NKbyCs
"Math Puzzles Volume 3" is the third in the series. (rated 3.8/5 stars on 4 reviews)
amzn.to/1NKbGlp
"40 Paradoxes in Logic, Probability, and Game Theory" contains thought-provoking and counter-intuitive results. (rated 4.3/5 stars on 12 reviews)
amzn.to/1LOCI4U
"The Best Mental Math Tricks" teaches how you can look like a math genius by solving problems in your head (rated 4.7/5 stars on 4 reviews)
amzn.to/18maAdo
"Multiply Numbers By Drawing Lines" This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 5/5 stars on 3 reviews)
amzn.to/XRm7M4
I'll just pretend to understand
The calamity you seek will have its own shadow
I actually skip this question of Presh, like, c'mon its really insane and what I have done is answering the other questions and left this question with an answer of doubt, lmao
Me too. My head hurts while trying to understand
I bed on 4 days
Replace “seeds” for “coins”. Replace “turned into trees” with “landed heads up”.
Replace “how many days will it take” with “how many days should it take on average, assuming that no other factors will influence the outcome”.
I took a look at the puzzle and said “well, 3 Days if everything falls perfectly, but let’s give it 4 just in case we have a crap day”.
Within .3 isn’t half bad.
*Within .03
You are great
😂
Exactly the same approach. By the time you make coffee on day 4, it's done. :D
I'm having a string of crap days. What's the probability of that?
@@SpaceCadet4Jesus Just wait a week. After that, you just gotta except that the dude that sold you these "magic seeds" scammed you good and move on with your life.
Number of Seeds E(N)
2 2.667
4 3.505
8 4.421
16 5.377
32 6.355
64 7.344
128 8.338
The expected number of days grows with the log2 of the number of seeds (roughly). Doubling any number of seeds will make the expected value increase by about 1 day.
I compared his 0, 1, 2, 3 to 6 day e= 0, 2, 2.6, 3.1, 3.5, 3.7, 4.0 ... I have seen this log-like function too. I aspected to see I solution whitch contains something like log2 and not many many equations like the two ways in the video x.x
That makes sense since this is literally exponential decay with a half life of 1 day.
@@rapex2729 When you get to day 3 you can stop and make yourself some apple pi - approximately - 22/7
Like a lot of "Expected time until..." problems, the easiest way is to work backwards, so let's try that.
The last two values are easy:
6 trees = t6 = 0 days to wait.
5 trees means we are waiting for just one seed with probability per day of 1/2, so expected time to wait = t5 = 2 days.
Let's look at the next few values:
4 trees, we have a 1/4 chance to stay at 4 trees, 1/4 chance for both seeds to germinate giving us t6, and 1/2 chance for just one seed to germinate giving t5. All of this takes one day. So we have:
t4 = 1 + 1/4 t4 + 1/2 t5 + 1/4 t6
which we can solve as:
t4 = 1 + (1 + 2 t5 + t6)/3 = 8/3
The binomial pattern is fairly obvious at this point: 3 trees gives us:
t3 = 1 + 1/8 * t6 + 3/8 * t5 + 3/8 * t4 + 1/8 * t3
t3 = 1 + (t6 + 3 * t5 + 3 * t4 + 1)/7
t3 = 22/7
Using Pascal's triangle, we can read off the next equations similarly:
t2 = 1 + (t6 + 4 * t5 + 6 * t4 + 4 * t3 + 1)/15
t1 = 1 + (t6 + 5 * t5 + 10 * t4 + 10 * t3 + 5 * t2 + 1)/31
t0 = 1 + (t6 + 6 * t5 + 15 * t4 + 20 * t3 + 15 * t2 + 6 * t1 + 1)/63
Solving successively,
t2 = 368 / 105
t1 = 2470 / 651
t0 = 7880 / 1953
which appears to be in gcd form already. Despite t3 almost being pi :)
And daaaaamn, having watched the video now, I fidgeted impatiently thru the official solution's extra steps - and then Presh's better solution is almost exactly what I wrote. Looks like all I added was an extra joke about 22/7 and pi.
When in the hell did you learn this?
Olympiad math tends to be learned on extra class hours, at least in my country
Hey can you explain me how you pass from t4= 1+ 1/4 t4 +1/2 t5 +1/4 t6 to t4= 1 + (1 + 2*t5 + 4*t6)/3
I understood nothing of your comment
Incredible problem! Been out of touch with math for a while and I took a few hours to go through the math but I solved it. Definitely didn't think of the recurrence method. My method was similar to the official solution. When I reached the point where I needed to use binomial theorem and make things very messy, I knew there would be another elegant solution but I was in too deep. After expanding, I actually ended up with an arithmetico-geometric series in mine, which is more complicated than the official solution, and I had to look up formulae for infinite summation of AGPs but after some more gruelling calculations, my answer actually matched perfectly! Such an incredible feeling...
I only think and solved this with method 2 using recurrence because of simplicity. It is hard to imagine one can solve this problem using offical method with only a 4-operation calculator...
I just kept multiplying 6 by 1/2 over and over (you could put this into an equation as y=6*(1/2)^x) until the answer was less than 0.5, so that when rounded, there would be 0 seeds left. I got 4 because you have to multiply 6 by 1/2 4 times for it to be less than 0.5. It took just a couple seconds, and I got a very close answer :)
"Average score is 9 and top scorer got 29"
My math ain't that bad if I can understand what that means.
I think no because you might thought that he's 3 times better when he's 100 times better (sorry I'm not mathematician uwu)
it means a lot of people scored 0
@@peachpink2831 I know I'm kind of late on this but notice that it said median, which can easily be seen if you line em all up scaling from low to high and take the score in the middle. This means that there don't even have to be zero's, just that there as many people scoring >9 as there are people scoring =9 or
1,2,4,29
From above data, calculate average and find the top score.
@@todabsolute exponential growth
I like how you simplified such "complicated theorems", your work very inspiring, teaching people how to approach a problem before solving it instead; of blindly trying every "learned by heart" formulas is something that math teachers and "math-phobic" will owe you forever.
I have a little suggestion about adding a specification on the problem's nature, or to classify them into categories just so people interested in a specific category like geometry probability or something else..... can find their way.
the most sincere thanks for your efforts & keep it on :).
I did something I think is quite logical and did it in my head...
I expect at the end of day one 3 of 6 seeds to become apple trees.
I expect that the end of day two another 1.5/3 remaining seeds to become apple trees. So 4.5/6 in total.
By the end of day 3 I expect a further 0.75/1.5 remaining seeds to become apple trees. (5.25)
By day 4 0.375/0.75 become trees. 5.25+0.375 is greater than 5.5 so close to 6 as the nearest whole number so it should take 4 days for all 6 trees to be grown.
Harshil Patel Your method would be ideal way to a solution if the question was "what is the most probable number of days for all 6 seeds turn into trees.".
Sounds good. The only problem is that for example 1.5 seeds (out of 3) don't become apple trees in practice. It's either 1 or 2, so more probably 1 (because 1.5 < 2).
So, at the end of day 2, the practical probability of the remaining seeds growing is 1 out of 3, because half trees don't grow => 4/6 trees in total.
At the end of day 3, because there are two trees left, the probability is 1 of 2, 5/6 in total.
The last tree grows with a probability of 1/2, => two days => the answer is 5 days.. :D Where did this go wrong?
On the other hand, shouldn't the answer be 12 days, because all seeds have only 1/2 chance of growing any single day.
Those would have been my two guesses to this problem and seems I would have failed epically.
Expected number of A by time B does not in general convert to expected time B before you have A. Consider the related problem where you still have 6 seeds, but they are all guaranteed to bloom on the same day. Every step in your process is just as valid. At the end of day one you will still have an expected number of 3 trees (as it is a 50/50 chance of there being 6 or 0). At the end of day two you would still have an expected number of 4.5 trees (75/25 chance of the being 6 or 0), etc. Although the expected number of days until all seeds have bloomed in this situation is clearly 2 (as the number of seeds is here completely irrelevant), your method would still give 4 as the answer.
In many situations though, doing what you've done gives you a fairly good approximation of the answer. I'd probably do the exact same reasoning that you did in order to estimate that there are about 4 days. If my calculations on the actual problem had given me a wildly different answer I would expect there to be a mistake in my calculations somewhere.
This was pretty much exactly how I was going on this problem... [day one: 6/2=3][day two: 3/2=1.5][day three: 1.5/2=0.75][day four: 0.75/2=0.375] ...and because 0.375 is less than half, then the probability is more toward the last seed would change to a tree.
you can't have fraction transformations. It's the limit of such reasenament
much harder than I thought. I went with an intuitive approach, which appears to produce roughly the same outcome, but is incorrect as it skips many of the possibilities:
On 1 day, I would expect 3 seeds to become trees, leaving 3 seeds. On day 2, 1.5 of the 3 seeds have become trees. On day 3 it is 0.75, and on day 4 it is 0.375, which is smaller than 0.5, therefore my result was 4 days.
Yes, this was my solution as well, more or less -- I visualized the probability curve for each day and went looking for the peak. The problem is it doesn't produce the fractional result that the question expected
I love the appearance of Pascal's triangle in the numerators of the fractional coefficients in the second solution.
Love it as it just comes so naturally with the binomial distribution of the seeds, clean!
Your linear-programming/markov-chain/not-throwing-out-all-the-data-at-each-step solution is significantly more elegant than what they've got.
My thought was: if there are an even number of seeds, then 1/2 will blossom. if there were an odd number then you alternate rounding up and rounding down. Day one 6 seeds turns into 3 trees, day two 3 seeds turns to 1 tree (rounded down), day three 2 seeds turns to 1 tree, day four 1 seed turns to 1 tree (rounded up). 4 days.
A very simple computer program can solve this very easily. I simulated 1 billion final outcomes (until all transformed from seeds into trees), and got the answer of about 4.0348 days. I also had the program show me the minimum and maximum number of days needed for all 6 seeds to become trees. The min was 1 and the max was 34.
That cool
I just said that by the first day there will remain only 3 seeds, in the second day there will remain either 1 or 2
If it remains 1 seed then it will take another one or two days for the last seed to turn into a tree (3-4 days)
If 2 seeds remain it will take two or three days(4-5 days)
So basically the seeds will turn into trees in aprox. 4 days
Same here.
Just look like you know what’s going on and nod...
And when asked to explain just start saying random stream of words: probability, equals, one, minus, plus, N and K.
"You get to the formula by using the number and add and minus the fraction"
This works surprisingly well when this happens irl
The formula can also be derived by summation of the probabilities of each fraction, then dividing by N to the power of K minus 1. _nods emphatically_
I lost him at the binomial theorem.
My solution: They don't explain what "expected value" means, therefore we can assume it means if you add up the probabilities until it reaches 100%. Each seed independently has 50% chance, therefore you add them together and get the answer of 2 days. The end.
Alternate one: "keep going till it goes over 5.5" (which I think is a better expected value).
Day 1: 3/6 trees
Day 2: 4.5/6 trees
Day 3: 5.25/6 trees.
Day 4: Over 5.5/6 trees, therefore 4 days is the other answer.
Im 13 and thiught this was a simple tricks video like 4% of 75 is the same as 75% of 4... Boy was i wrong
😂😂😂
Day 1: 3 seeds left. Day 2: 1 or 2 left. Day 3: 0 or 1 left. Day 4: 0 left anyway. I believe it can’t be a decimal number according to the question btw.
I dont know anything in the video and i got 4
Close enough i guess
"Insanely hard" -- title checks out.
To everyone who’s trying to see an intuition for this problem, here’s the key insight: the number of days it takes all 6 trees to sprout is entirely dependent on the MAXIMUM value in our sample of six. The number of days it takes all seeds to sprout is determined by the last seed to sprout. So to find that expected value, you need the probability distribution of the maximum of a sample of six seeds.
I solved it after beating my head against the problem for like three weeks. My solution was more similar to the official solution, but not exactly the same. I still got it though.
I did it like this:
The odds of any given seed being a tree after 1 day is 1/2. There are 6 seeds, therefore the odds of all 6 being a tree after Day 1 is (1/2)^6 = 1/64 ~ 0.156%.
The odds of any given seed being a tree after 2 days is 3/4 (since there is a 1/4 chance it stays a seed twice in a row), and (3/4)^6 = 729/4096 ~ 17.8%.
3 days... (7/8)^6 = 117649/262144 ~ 44.9%
4 days... (15/16)^6 = 11390625/16777216 ~ 67.9%
Since the odds of all seeds becoming trees by Day 4 is greater than not all seeds becoming trees by Day 4, it should take 4 days in most cases.
We can then see that this trend continues to approach 100% as more days pass (5 days = 82.7%, 6 days = 91.0%, 7 days = 95.4%, 8 days = 97.7%, etc.), which is expected.
This wouldn't get credit in the contest since it's not exact, but should still be correct. Yet it seems way too easy to approach it like this, so I'm trying to find the flaw in this logic. Anyone see it?
Radi0actvChickn I don't see a flaw in your logic. Seems like a solid way to estimate the expected value so that we know roughly in what ballpark it lies.
I don't really understand what "expected number of days" means but depending on the defenition I see a potential flaw: You calculate the probability for each day but possibly you need to find a point at which the sum of all probabilities above and below is the same. I guess you have to find the infinite sum of your series to know that point. I have the feeling you assume it is 1. This might be a potential logic flaw. Edit: Not your series, I meant a series that converges to 0.
It looks perfect to me! Since the problem is discrete, I'd say an expression like 4,03 days makes no sense.
The flaw is that what you're finding is the median, not the mean. The question is asking for expected value, which is another word for the mean.
4:38 Homie hit the vibrato on the last word lmfao
Lmao I never even noticed that when I watched it the first time
Once you have the Pr(N>=k) you can back out the P(N=k). P(N>=1) - P(N>=2) = P(N=1). From these probabilities, it is trivial to calculate the expected value, and you can even plot the distribution.
k P(N=k)
0 0.0
1 0.015625
2 0.162354
3 0.270817
4 0.230139
5 0.147618
6 0.083284
7 0.044194
8 0.022759
9 0.011548
10 0.005817
11 0.002919
12 0.001462
13 0.000732
14 0.000366
The variance can be calculated from the following formula. VAR(N) = E(N^2) - E(N)^2. You calculate the expected value of the squared random variable (number of days).
E(N^2) = 1*P(N=1) + 2^2*P(N=2) + 3^2*P(N=3) + ... = 19.467
VAR(N) = 19.467 - (4.034)^2 = 3.186
Take the sqrt of the variance to get the standard deviation.
STD_DEV(N) = sqrt(3.186) = 1.785. This tells you roughly how spread out the distribution will be around the mean (Expected value). It's always a good idea to look at the variance of a probability distribution before using the expected value as a point estimate.
Check out a plot...
www.wolframalpha.com/input/?i=ListPlot%5B%5B0.0156,+0.1624,+0.2708,+0.2301,+0.1476,+0.0833,+0.0442,+0.0228,+0.0115,+0.0058,+0.0029,+0.0015,+0.0007,+0.0004%5D%5D
As someone who has no clue about higher mathematics, and without following required procedure, 4 was the obvious answer to me:
The "remaining trees" need to be reduced to less than 0.5 to be discardable by probability.
Day 1: 3 trees left
Day 2: 1.5 trees left
Day 3: 0.75 trees left
Day 4: 0.375 trees left
Answer: 4 days
At least, this took me only about 10 seconds.
That’s the correct answer, unless you want to give it the extra day cause you can’t have a part of a day. But the answer is BS, because you can’t have part of a day, so there’s no reason for the answer to be in the form of part of a day.
It's about probability. The "official" answer was also rounded to 4.
I like your solution much better than the official one, has a computer science flavor to it :) what’s really cool is that the sums of all the recurrence relations follow Pascal’s triangle divided by a power of 2. You could easily generalize this problem to n number of seeds.
I did this in my head, kinda like the second way. I did 3+1.5+.75+.375 and at that point it reached a number above 5.5 (so it rounds up to 6) and each term in the expression above corresponds to a day. I would have never gotten 4.03, but I did get 4. Thanks for the problem
Is there a more general formula to find e0, e1... ?
What if I had 100 trees instead of just 6?
www.wolframalpha.com/input/?i=e(n)+%3D+sum+(n+choose+i)+%2F+2%5En+*+(1%2Be(i)),+i%3D0+to+n
I'm not 100% percent sure, but I was just realizing that the coefficients on the values for the decreasing e values when taking out the base number follows pascals triangle, so doing e100 trees may work to do with pascals triangle after finding the base probabilities using the concept of flipping 100 coins like in the video.
It is quite simple to derive the general formula usong method 1. The calculation is so tedious that humans cannot handle. But it is very easy for computers.
I solved it without the E(N) method.
Day 1= 6 seeds with probability 0.5 to become a tree. So 3 total expected trees.
Day 2= 3 remaining seeds with same probability = 1.5 expected trees. Since we can't have half trees, we must round down to 1 new tree, 2 seeds remain. But, since we rounded down (gave up probabilty for half a tree), the next time we must round Up to balance it out.
Day 3= 2 seeds, 1 expected new tree.
Day 4= 1 seed, 0.5 tree expected. But here we round up for our carried over percentage. So 1 expected new final tree.
So 4 Expected days to get all 6 trees.
I'm definitely getting old and losing my edge. I just resorted to using excel to do a Monte Carlo simulation on 10k paths using What-If Analysis. Got the answer in less than a minute but it's so lazy and inelegant. I bow my head in shame and salute all of you that managed to do it properly.
I figured that a probability of 1/2 for each meant you'd expect half of them to change every day. So 6, 3, 1.5, .75, and after day 4 the number drops below .5 so you'd expect it to take 4 days.
This is definitely one of THE math problems I have seen.
I was just 0.03 away from the answer and I’m in sixth grade!
Here’s my method: I thought about the number of days it would take at max for all the apple trees to be made and the min. I used this information and I added up all the days between the 2 numbers and then divided by the total number of days. In short, I found the mean. I did this with the probability of this for if each seed number came up per day. (Ex. The days it would take for it to if 1 seed was grown per day would be: 6,7,8,9,10,11,12. I then found the mean of the numbers). I did this for all the possible number of seeds that could come up per day. I then found the mean of that info and got my answer of 4.
I hope you found this method easier!
@15:24 A wild pi appears out of no where.
Nonsense! 22/7 is basically as far away from pi as 1
pi is not rational.
Eppepalli Rohith I thought the same 😂😂😂
so is 22/7 and you are looking for the term irrational
Apple pi!
I hate probability problems. Your solution makes sense, I did not understand a single thing from the official one lmao
After about 30 seconds I had to duct tape my head to keep it from exploding! In my opinion just plant the damn things and wait for them to grow!
What is the definition of "expected number of days"? I can't even start to tackle this problem. After each day the likelihood increases but will never reach 100%. So I assume the likelihood must be over a certain threshold.
I solved this problem and I actually did it in a pretty simple way. I calculated the possibility of each seed staying as a seed over a certain number of days, which would be 1/2 on the first day, 1/4 on the second day and so on. To calculate the probability of any of them still being seeds, you add the values together. So on the fourth day, each seed has a 1/16 chance of still being a seed. So the probability of any of them being seeds is 6/16 or 3/8 when reduced. Since the probability of any of them being seeds is less than 50%, then you would expect all of them to be trees by day 4.
But they can still be seeds!by the day 4
I wrote a python program to simulate the problem, and averaged the number of days over 10000 simulations, and got the exact same answer (albeit not as an exact fraction in the form m/n).
It is worth noting that binomial coefficients (following the rows of Pascal's triangle) are observed in the numerators of the fractional coefficients for e_k. The denominators of those fractional coefficients are 2^(6-k)
Well, if I took the test, I would have failed, even though I reached the conclusion that it would take 4 days for the 6 seeds to grow, I reached the number like this; if 6 seeds have a 1/2 chance to grow in a day, it means that 50% of the seeds will grow the first day, so in day 1, 3 trees will grow, then we have 3 seeds left, the next day, again the 3 seeds left have 50% of a chance to grow, that would mean 1.5 seeds should rise, but that is not possible, because half a seed can't grow, thenonly 1 will rise, now we have 4 trees up in the second day; now in the third day half the remaining seeds will grow, 1 more tree, and now in the next day, being it the fourth, the last seed will grow, and at last, it took 4 days in total for the six seeds to grow; though to a farmer it wouldn't matter if he has the answer in fraction and/or to the decimal XD, though the answer is close i don't think is the corercet way of thinking it.
I used neither method and got answer 4 days in a few seconds:
First day you expect there to be 3 or less seeds.
Second day you expect there to be 1,5 or less seeds.
Third day you expect there to be 0,75 or less seeds. (edit, rounds up to 1)
Fourth day you expect there to be 0,375 or less seeds, aka more likely for all of them to be trees at this point. (edit, rounds down to 0)
Same thinking.
Here is how I solved it.
First I want to mention that it was all in my head there was no way I was going to be exact and that since it was a probability problem, i just used simple logic.
I first noted that if all six seeds grew into trees on the first day which is about 1.56%, pretty unreasonable to expect.
It is also 1.56% for none of the seeds to grow in 6 days which again is unreasonable to expect.
There is 87.5% chance on all six seeds to grow on in 4 days which is reasonable especially when considering in five days it 93.75% which is stretching it.
So my answer was 4 days. And would u look at that the answer was 4.03 days.
It took me about a second to realize that the expected number of trees after 1 day is 3, and after 2 days is 4.5, and after 3 days is 5.25. At that point I surmised that the final answer was a tiny bit more than 4 days, and that was close enough for me without having to do a whole lot of work. :)
I know, right? Seems like a bit of an overcomplication in Presh's solution.
No, as you increase the number days (N), the expected number of trees E(tree after N days) will be converging to 6.
So how would you know the expected number of days is 4 but not 5 or 6?
There are just no clear relationship between E(tree) and E(N) that can help you to estimate the answer.
Day Expected number of trees
1 3
2 4.5
3 5.25
4 5.625
5 5.8125
6 5.90625
7 5.953125
8 5.9765625
9 5.98828125
10 5.994140625
I guess since at Day 4, the value of 5.625 is the first in that series that rounds up to 6 ¯\_(ツ)_/¯
the expected number of trees at that point is either 5 or 6 and it's closer to 6
@@dual-blade-main , under your logic the answer is infinity... clearly misguided.
This is, in my opinion, a poorly worded question. It's a Poisson distribution, so it should really ask on what day is there the probability of X (where X is any percentage) that all seeds would have become a tree?
What does "expected" mean? What probability is that? 90%? 99%? To me this is a meaningless question because "expected" is undefined. Questions like this annoy me because you have to know the mind of the person asking the question, and you simply can't.
The obvious solution is:
Day 1: 6/2 = 3 germinate = 3 total
Day 2: 3/2 = 1.5 germinate so that is 3+1.5 = 4.5 total
Day 3: 1.5/2 = 0.75 germinate so that is 4.5+0.75 = 5.25 total
Day 4: 0.75/2 = 0.375 germinate so that is 5.25+0.375 = 5.625 total
And since you can't have a portion of a seed germinate, and you're over a 50% probability that the last seed germinated, the answer ought to be 4 given the ambiguity of the question. I hate questions like these because it basically boils down to an undefined word that is meaningless in a technical fashion.
In a real world situation, you'd want to have a guarantee of some probability of all 6 germinating, not some wishy-washy concept of "expected". This I think is just a poorly worded question because definitions aren't clear. This would pose a barrier to somebody who had a different concept of "expected" than another person.
If these weren't seeds germinating but the probability that the 6 electrons needed to cross a transistor barrier before they activated a gate in X ns, you'd want to have a higher probability than "expected". You want 99.99999999999999% or higher. Faults do happen in chips, and you have millions of gates, and you want a fault to happen, basically, less than once a year in the entire chip.
I don't think questions like these are useful in any real world situation and don't teach students to think productively or critically. The very first thing this question does, it make you do a guess on what is the intention of the question. So basically, I think this is a question asked by an incompetent that shouldn't be teaching math at all and that unfortunately, is a lot of math teachers in lower education nowadays.
I used the method from the video on the expected number of cards to still be in a specific spot despite a number of shuffles - the 1/52 chance + 1/52 chance and so on one. Ended up with the expectation that, after day 1, I'd end up with 3 trees growing if there's a 1/2 chance of a tree growing. Used the same method with the remainders after each day. Not rounding would end up with an infinite series approaching 6, so I rounded appropriately (you wouldn't get 1.5 trees so I had an actual expectation of 1 tree growing on day 2).
Day 0 - 0 trees of 6 grown, 6 to go
Day 1 - 3 trees of 6 expected to be grown (half of 6), 3 to go
Day 2 - 1 tree expected to be grown ("half" of 3), 4 trees of 6 total, 2 to go
Day 3 - 1 tree expected to be grown (half of 2), 5 trees of 6 total, 1 to go
Day 4 - Either 1 tree will grow or it will not.
Did it the same way only Day 4 the tree has to grow becaus it didn´t grow yesterday.
I started to do something along the lines of the official solution, but I didn’t think of the trick to realigning the expected value sum, or that way to flip over the probability. Here’s as far as I got before I got overwhelmed by the number of terms I would have to expand and sum, decided I didn’t really have time to waste on that, and basically gave up:
E=P(1)+2P(2)+3P(3)+4P(4)+....
Probability of any seed not becoming a tree after n days = 1/2^n
2^n=n’ for short
To calculate the probability of the last day being n, imagine the day before all 6 trees sprouted. We can check all the possible numbers of unsprouted seeds, find the probability of that day occurring, then the chance of all remaining seeds sprouting.
Number of still seeds=m
Number of ways for m seeds to be selected = 6cm (six choose m)
Each seed had a 1/n’ chance of staying a seed, each tree had a (n’-1)/n’ chance of becoming a tree
Chance of their still being m seeds on day n=6cm x 1/n’^m x ((n’-1)/n’)^(6-m)
Chance of all remaining seeds becoming trees on next day is 1/m’
Summing over being 1, 2...6 seeds left and plugging in the chooses, we get 6/n’x((n’-1)/n’)^5/32 + 15/n’^2x((n’-1)/n’)^4/16 + 20/n’^3x((n’-1)/n’)^3/8 + 15/n’^4x((n’-1)/n’)^2/4 + 6/n’^5x((n’-1)/n’)^1/2 + 1/n’^6x((n’-1)/n’)^0/1 for he chance of it taking n+1 days for all seeds to sprout.
I would like to get an intuitive understanding of a real life example. Let's replace "magical tree" by "unstable atom".
The half life is 1 day.
The number of atoms is 6
So, after 4 days, all 6 atoms decayed to lighter element.
How many days is expected of:
* 1000 atoms
* 10^10 atoms
* 10^1000 atoms
Is there a number of days to be expected for number of atoms (or magical seeds) growing toward infinity?
I wouldn't figure it on my own, because i wouldn't think of thinking backwards. The moment you started explaining how you would do that, I just used your method, and it was almost easy. I also NEVER seen anything like that Probability expansion (or whatever it was), like in an official version, so I wouldn't get it this way ever.
Is this a valid way to calculate it?
We determine the number of expected trees for each day. Once that number is greater than 5.5, then the probably that there are six trees is greater than 50%. On day 1, it is 3.0 (6 trees * 0.5), on day 2 it is 4.5 (3.0 + (3 * 0.5)), on day three it is 5.25, and on day four it is 5.625. Day four is the first day where the probability of six trees is greater than 50%, and that's the answer.
This is a brilliant way to approximate it. Since it is a sequence, you will never be able to get an exact answer, but will know that it is between 4 and 5, but very close to 4.
This was very similar to the ideas of top-down and bottom up in dynamic programming !
I got to 5 days (correct integer answer) this way: On the first day, 3 trees, three seeds; day 2, "1.5 trees" (rounded down to at least 1), so total four trees; day 3, maximum of two remaining seeds, 1 more additional tree, 5 total; day four, 1 (maximum) remaining seed takes maximum of 1 additional day to transform; so by day 5, all are trees.
Usually with expected value problems, you can just set up a simple recursive state equation. I just did E_n=sum from k=1 to 6 of (n choose k)/2^n*(E_k)) and just build your way up from base case E_0
Consider ratio 1 to 2: after one day half of the seeds are now trees. day two chance of Half of three seeds become trees - you can only count on one, therefore four trees after day two; One of the two remaining seats becomes a tree at the end of day three. On day four on there is only one seed. you have only a 50% chance of it becoming a tree by the end of the day therefore you need the fifth day for Hundred percent chance: five days needed.
John Davis why 100% chance here ??
This is one of those problems where I knew how to solve it right away using the recursion method in the video but that I had absolutely no interest actually writing it out or calculating the numbers.
The first part of the video though was interesting, I had to blink at the line which went immediately 1*P(N=1) + 2*P(N=2) + ... = P(N>=1) + P(N>=2) + ... . That is not at all obvious at face value, the proof in the video is pretty slick though.
"Each seed on each day has 50% chance to become a tree" means that we are just interested in the number of days after which the last seed will become a tree.
For how many days the last seed can refuse to become a tree?
(The last seed may not be alone.)
EDIT: Chances that the last seed will fail to become a tree are
for 1 day - 50%
for 2 days - 25%
for 3 days - 12.5%
for 4 days - 6.25%
for 5 days - 3.125%
...
If one would like to estimate the answer in whole days, would it go like this: at the end of day 1 the expected amount of trees is 3 (because it's half of six). End of day 2 : 4½ (half of the remaining 3 have grown). End of day 3: 5,25 (4½ + 0,75). End of day 4: 5,625 (5,25 + 0,375). Now it's over 5,5 so it's probable it's 6. And the answer is 4.
First method is insanely complex to one who have forgot math long ago. Second one at least understandable)
Well, at least I've guessed correct that this will take circa 4 days. I've thought as follows: after first day we may expect 3 trees, after second - 4.5, after third - 5.25, and after 4th - 5.625 which can be rounded to 6.))
I found the second solution, but it takes a lot of work to compute and doesn't scale up very nicely (lets say we needed to solve for 10 trees).
The first solution can easily be expanded to 10 trees without too much more effort.
I got it using half life method, at d=0, 6, now keep halfing it will bring yo down to 0.35 seeds left at @4days
That's exactly what I did.
You can equate it to having 6 coins and asking how many coin tosses would you expect to have to get all heads if you remove the coins landing on head from subsequent coin tosses.
You then end up with:
(6 x 1/2) - (3 x 1/2) - (1.5 x 1/2) - (0.75 x 1/2)
and so on until you reach a value of less than 0.5.
Hey, Just wanted to say there is also a more unorthodox method of solving this. You simply need a random number generator, for example just google "random number generator" to use googles widget one. Then take a piece of paper and mark down numbers 1-6. Then start generating random numbers from 0 to 1, where 1 means the seed grows and 0 means it does not. Every time a seed does not grow, roll again on the next row marking another day. Keep track of the total number of trees grown each day (Day 1, day 2 etc.) do this a few times until you have a even spread of trees grown each day and you should average at about 1,5 trees/day. 6/1,5 = 4.
Well
iff every seed has half the chance to grow into an apple tree, this means that by Day 1, 3 seeds would grow and 3 seeds remain
But 3/2=1.5, and you can't cut a seed in half for 4 trees, so either 1 or 2 seeds shall grow (the numbers shall be named a). Nonetheless, the remaining seeds would be 3-a
iff a=1, then one seed shall grow in the next day and the other does it later
iff a=2, the seed could grow the next day
So the answer would, on average, be 4
I just calculated it like this:
1. 6/2 = 3
2. 3/2 = 1.5
3. 1.5/2 = 0.75
4. 0.75/2 = 0.375
The number has to be divided by 2 until it's 0 when rounded into an integer. The answer is the amount how many times you had to divide it. (Answer: 4)
far too complicated for me,,,, i guessed 4 to begin with my logic went like this,,, 50 % so day one 3 are trees, 3 are not, day 2 4.5 are tree 1.5 are not, day 3 5.25 are trees 0.75 are not. day 4 your just been silly if you want me to believe that the 0.375 hasn't turned into a tree by nowww
It is a good idea to get an asymptotic approximation to the recursion formula. Your method looks at the smallest k such that n/2^k < t, where n is the the number of seeds, k the number of days and t some threshold below which you will consider having no seed left. You claim k~log_2(n/t) as n grows large. I think this is plausible. But it does require proof.
that was my logic too
Yeah it's easy to estimate and get a logical answer but I'm guessing they'd require a mathematical proof.
Well... that was close to the real answer, but the question required you to put the exact fraction calculated in the video, so your answer would not be valid
My solution: on the first day, half of the seeds transform, so there are 3 trees and 3 seeds. On the second day half of the 3 seeds transform, so thats VERSION#1 1 tree and 2 seeds left or VERSION#2 2 trees and one seed left. On the third day VERSION#1 one seed transforms and the other one is left to transform on day 4, or VERSION#2 the last one seed could transform this day, or the following day, which is day 4. Conclusion: It takes 4 days for all the seeds to transform!
You finally covered a problem that was a bit challenging (I'm sorry lately they were kinda dull :/ ). Do more like this please
atrumluminarium did u figure out this problem?
Abhishek Ahirvar Yes, but at least it wasn't one of the other ones that one could figure out just by looking at them. I think it took me a solid ~10mins to work through
what are you studying atrum???
Mathematics and Physics
can you please teach me maths i cant even get an A in highschool
I don't know what "expected number" means, so I can't figure it out.
Execute the procedure a large number of times, record how many days until you reach 6 each time. Average all the recorded results together.
I EXPECT the 6 seeds become magic tree in 1 day. So the answer is 1
IIRC "expected number" = Mean Average.
The reason I remember this is because I made a tit of myself in an A Level maths class years ago when I asked the teacher if she actually wanted the mean value or the expected value.
She said, in a very patronising voice, "They're the same thing Lewis".
I’m super late but my estimate was after 1 day 3 trees are expected to grow. After two days either 1 or 2 more trees were expectedly grown. If one then you have 4 grown. Day 3 one is expected to grow making 5. Since earlier it was one tree over 1.5 trees (which can’t happen) and you lost 0.5 trees and this time you will gain the 0.5 tree lost on day 4 to give you 6 trees. For 2 trees on day 2 you now have 5. Since you got the extra 0.5 tree then you expected to not be lucky again, making it take 2 days to get the 6th tree, making it an expected amount of 4 days.
Please read to the end:
I didn't understand most of what was said, yet I got a close answer easily. This is a geometric series that is defined as: a(n)= 6×(1/2)^n, where n=no. of days. Using Calculus, find the limit of the sum which converges into a value. Find the nth day to reach this value, that's it!
Going back to the basics, let's try to count it:
After 1 day, you'll have 3 trees.
After 2 days, 4.5 trees.
After 3days, 5.75 trees.
After 4 days, close to 6.
So the answer is 5 days.
The method of induction can be checked and expressed as p(n) as n being the number of seeds, then you get a Bernoulli type equation and compute 😊🎉
I follow your videos but never comment on them. This one was though, I was amazed by the simplicity of your solution!
Congrats for the channel and for your purpose.
Cheers from Brazil.
It took about 10 seconds to work out four days, in my head. Another way to approach this problem is to realize that it takes one day for half the remaining seeds to become trees.
On the end of the first day we get 3 trees and 3 seeds remain; second day 4.5 trees and 1.5 seeds remain; third day 5.25 trees and 0.75 seeds remain; fourth day 5.625 trees and 0.375 seeds remain.
By the end of day four, we have less than a half seed remaining, and half seeds become trees in a day (the other half of that seed became a tree! Lol). So answer is 4 days (plus a little bit, because this goes to infinity, but never goes to the end of day 5).
4.03 is also the result I get using the Monte Carlo method:
# Python 3.7
# Find the expected number of days until all
# six seeds have become apple trees.
import random
choices = (True, False)
runs = 100001
day_sum = 0
for i in range(runs):
num_days = 0
seeds = [1, 1, 1, 1, 1, 1]
while 1 in seeds:
num_days += 1
for j in range(0, 6):
transform = random.choice(choices)
if transform and seeds[j] == 1:
seeds[j] = 0
day_sum += num_days
print("The expected number of days is ", round(day_sum / runs, 2))
Here's me just saying that about half of the raw amount will grow per day, so day 1 = about 3 grown trees, day 2 = about 4.5 grown trees, day 3 = about 5.25 grown trees, and day 4 = about 5.625 trees, so I estimated 4 days as that's the day where less than half a unit remains ungrown, so they are all more likely to be grown than not.
I actually did figure it out after a couple of days of trying! But I used a completely different method, and I had to cheat and use Wolfram Alpha to calculate some bits as I simply did not know how to calculate them manually. So I'm glad to have now watched a simpler solution that arrives at the same result in a far more systematic and elegant fashion than I was able to!
My method was basically calculating P(x trees in n days) for different x between 0 and 6 and for n = 1, 2 and 3. This required a LOT of binomial expansions! However, I managed to calculate that P(6 trees in 1 day) = (1/2)^6, P(6 trees in 2 days) = 729(1/2)^12 and P(6 trees in 3 days) = 117649(1/2)^18. I used these results to generalise that P(6 trees in n days) = [((2^n) - 1)^6][(1/2)^6n]. HOWEVER, I then realised that for n>1, these probabilities were actually overstated because they also contained cases where 6 trees were achieved on a day earlier than n (e.g. for n = 2, the case where 6 trees are achieved on day 1 is also included). These cases need to be subtracted for each n in order to obtain the correct probabilities. Based on this, I figured out that the actual expression for P(6 trees in n days) = [((2^n) - 1)^6][(1/2)^6n] - [((2^(n-1)) - 1)^6][(1/2)^6(n-1)]. Therefore, the expected value for the number of days to reach 6 trees is the sum of n{[((2^n) - 1)^6][(1/2)^6n] - [((2^(n-1)) - 1)^6][(1/2)^6(n-1)]} from n = 1 to n = infinity. Through algebraic manipulation, I rewrote this as:
Sum of {n[6(2^(1-n) - 2^-n) + 15(2^-2n - 2^(2 - 2n)) + 20(2^(3 - 3n) - 2^-3n) + 15(2^-4n - 2^(4 - 4n)) + 6(2^(5 - 5n) - 2^-5n) + (2^-6n - 2^(6 - 6n))]} from 1 to inf
And then I factored out the 2^-kn terms to give:
Sum of {n[6(2^-n)(2 - 1) + 15(2^-2n)(1 - 4) + 20(2^-3n)(8 - 1) + 15(2^-4n)(1 - 16) + 6(2^-5n)(32 - 1) + (2^-6n)(1 - 64)]} from 1 to inf
= Sum of n[6(2^-n) - 45(2^-2n) + 140(2^-3n) - 225(2^-4n) + 186(2^-5n) - 63(2^-6n)] from 1 to inf
At this point, I had to resort to Wolfram Alpha to calculate the sum from 1 to inf of each of the 6 terms in this expression (if anyone could let me know a method for manually calculating these sums, I'd greatly appreciate it!). Wolfram Alpha actually timed out on the calculations, so I had to rewrite the n in front of each term as 2^(log base 2(n)) and ask it to calculate the individual sums that way. Subbing in the individual sum values gave me:
Expected number of days = 6(2) - 45(4/9) + 140(8/49) - 225(16/225) + 186(32/961) - 63(64/3969) = 7880/1953 ≈ 4.0348.
Would love to hear some thoughts on this more unorthodox approach!
The "method for manually calculating these sums" is the geometric series sum formula - look it up.
yeah i got 4 and my thought process was "well, 3 days is half of six trees, so at 50% odds lets throw in an extra day for good measure. Four days."
I don't see a problem with the following logic:
with P=0.5, After one day, E = 3 (you would expect half of six seeds to become trees). 3 seeds now remain.
On day 2, you would expect half of the remaining seeds to become trees. This would be 1.5, but you can't have half a seed turn into a tree, and a seed either does so fully or it does not. Hence round down. This makes the expected number of trees after 2 days 4. 2 seeds remain.
Applying the same logic on 3 days would yield 5 trees with one seed remaining.
For the last seed, with a probability of .5, we would expect a tree 50% of the time after 1 day, 75% after two days, 87.5% after three days, etc. So the expected time for a single seed to become a tree is
0.5*[0.5(1)+0.5^2(2)+0.5^3(3)+...] = 0.5*Sum n/2^n
Sum n/2^n = 2 (when n goes to infinity), hence the expected time for a single seed is 0.5(2)=1 day.
Adding this to the other three days gives 4 days total.
I used the recurrence relation myself. I used backwards numbering, in that e_n signifies the expected number of days for n seeds to grow into trees. That captures the idea of growing all of a given number of seeds better, with e_n remaining invariant with respect to the total number of seeds. I also messed up my arithmetic in the final step, making my answer slightly off. :-(
i solved by a different method :
since probability of a seed becoming a tree is 1/2 so
on day 1
no.of seeds becoming trees =1/2*6
=3
remaining trees=3
on day 2
no.of seeds becoming trees =1/2*3
=1.5 (so we will take 1 as .5 is not complete)
trees remaining =2
on day 3
no. of seeds becoming trees = 1/2*2
=1
on day 4
the remaining seed will become tree
therefore it will take 4 days
My lazy solution:
first day - 6x1/2=3
second day - 1 or 2 remain
third day - probably remain 1 in either case for balance
4th or 5th day - 0 seeds remain
After just "the second day pseudocalculation" I knew it was about several days. And if I really was a magic farmer, this should be enough for me.
I made a numeric simulation of the problem with a large number of repetitions, and yes expected number of days is ~ 4.03.
I noticed on day 4, all the seeds have Not become apple trees in ~ 32 % of the cases.
I suggest another version of the problem : What is the minimum number of days until all 6 seeds have become apple trees with a given probability (e.g >= 95%).
Half on the first day - 3 trees, 3 seeds
Half of the remainder on the second day - 4 or 5 trees, 1 or 2 seeds
Half of the remainder on the fourth day - 5 or 6 trees, 0 or 1 seed
Half of the remainder on the fifth day - likely to be all 6 trees
So day 4 or 5.
Your bed is lava!!
Yeah, I didn’t get up either.
Micrqwaveッ At least it's warm...
I’m on the couch so I don’t care if my bed burns
I instantaneously got up
Flip 6 coins once a day until all land heads up, setting aside the ones that land on heads. How many days on average should it take until all have landed heads up?
So;
(1, ♾) /seed a day.
But, since we actually got to solve it give a real answer;
4 days on average. Rounded down to avoid none whole number results at any points.
Day 1 = 3 trees, leaving 3 seeds.
Day 2 = 1 tree, leaving 2.
Day 3 = 1 tree, leaving 1
Day 4 = 1 tree, leaving no seeds.
I first wanted to say that there's a mistake in the wording, that it would have to be the "average number of days", but then I figured that that's what the "expected" is standing for.
Since all those seeds basically have a half life of 1 day, is anything stoping me from saying: The expected time to go from 6 seeds to 3 seeds is 1 day. Which means i can keep calculating for only 3 seeds and just add one day to get from 6 to 3 seeds. The expected number of days to get from 1 seed to 0 seeds is 2 days (obviously). The expected number of days to get from 2 seeds to 0 seeds is 3 days (one day for the expected one seed to grow, then another 2 days for the second one), which means the only "problem" is the 3 seeds, which is the expected value with 1/8th that it stays at 3, 3/8th that it goes down to 2, 3/8th that it goes down to 1, and 1/8th that it goes down to 0 right away....
An approximation: log2(6e)... which is the number of times you need divide 6 by 2 to get 1/e.
Just a lucky guess?
Used the second method, that you showed us so many times already :)
When there were 10 seeds the first method would be way more efficient though.
When i was in school, I used to know this(probabilities or math generally) better, but it is still fun to try.
I first considered same method as you, but realized 6 trees is lot, if it was like 3 trees I would had stick to that method but it was too much effort for 6 trees. I figured there must be easier solution as this competition tests maths skills not willingness to brute force. I used almost same as official solution:
probability that all seeds are trees after n days is ((2^n - 1)/2^n)^6, probability that not all seeds are trees after n days is 1 - ((2^n - 1)/2^n)^6 and then getting expected amount of days are given by sum 1 - ((2^n - 1)/2^n)^6, n = 0 to inf, where rewirting 1 as 2^(6n)/2^(6n) and utilising binome coefficients becomes sum 6*2^(-n) - 15*2^(-2n) + 20*2^(-3n) - 15*2^(-4n) + 6*2^(-5n) - 2^(-6n), n = 0 to inf, series consisting of sums of terms that would alone form convergent series can be rewritten as sum of those series and geometric series with multiplier
My guess: 7 days until it's more likely that all trees have grown than not all trees have grown. But as with any probability function there is no certainty and it could take infinite days, though such an event would approach impossibility without actually being impossible.
Cool how this kind of draws parallels to the half life of radioisotopes.
Day 1: Expect 3/6 to grow into trees. [ 50% of 6 flourish, leaving 3 as seeds ]
Day 2: Expect 4/6 to grow into trees. [ 50% of 3 additionally flourish, leaving 2 (pessimistically) as seeds ]
Day 3: Expect 5/6 to grow into trees. [ 50% of 2 additionally flourish, leaving 1 as a seed ]
Day 4: Expect 6/6 to grow into trees. [ 50% of 1 additionally flourishes, leaving 0 as a seed ]
or...
(6 x 1/2) - (3 x 1/2) - (1.5 x 1/2) - (0.75 x 1/2)
[ Repeat until you get to a value < 0.5 ]
Such an interesting way of defining expectation. Thanks for sharing!
Your videos are entertaining and instructive, and I like them a lot. May I strongly encourage you, when doing simplifications and reductions, to not shift digits between terms. It makes it look like the digits are shifting between terms due to some assumed but unexplained mathematical process, and not just to reuse graphic elements, and is confusing.
Great video! Your method of using Markov Chains was much more elegant than the given solution.
"Give this problem a try?"
Me: No, thank you.
11:48 yeah right, Sub-Zero... where math meets mortal kombat :)
I mean I got an answer that is simliar... but I had no idea what this guy was on about.. in his setup lol
tree
A - 1
B - 1
C - 1
D - 0
E - 0
F - 0
D - 1
E - 0
F - 0.5
E - 1
F - 0.75
F - 1
4 days, round up or 3.77
Sorry to be picky, but there is a minor problem at 2:35, where we see P(seed -> tree on day i) = 1/2. This is wrong for i != 0; if it were correct, the probabilities across i would sum to infinity, not 1. The correct statement is
P(seed -> tree on day i | seed is not yet a tree on day i-1) = 1/2.
I find it interesting that in your solution that e3 comes out to the simple approximation of pi. I'm imagining that's just a coincidence, but still interesting nonetheless.
We need to get 3 Blue 1 Brown on that case immediately.