Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
For those who don't know, FiveThirtyEight is a website dedicated to looking at current events in politics, economics, science, pop culture and sports through a statistics-heavy, projection-based lens. It's run by a very smart fellow named Nate Silver, who started it in 2008 to analyze presidential election polls; it's expanded greatly since then and has been purchased by ESPN (which, aside from creating a sports-heavy portion of the site, has allowed it a lot of room to operate as it pleases). It's still probably the very best site for numbers-based election coverage.
At any rate, FiveThirtyEight writer Oliver Roeder has started a weekly blog series called The Riddler. Here's how he describes it:
Quote:Welcome to FiveThirtyEight’s first weekly installment of The Riddler. On Fridays, I’ll offer up a problem related to the things we hold dear around here — math, logic and probability, of course. These problems, puzzles and riddles will come from lots of top-notch puzzle folks around the world, including you, the readers.
This is the sort of thing I love, so I figured I would start a thread on here where I and anyone else interested could discuss the puzzle, talk about the solutions, and discuss any other sorts of mathematical puzzles that caught our fancy. So, each week I plan on linking to The Riddler's most recent puzzle, giving some brief thoughts, and opening the floor to discussion! The types of problems are a lot like "The 100 Prisoners' Problem" recently posted on here by Aractus, so hopefully stuff like that can find its way to this thread too!
There have been 11 Riddler puzzles posted already, so I'll work through posting them over the next week or two, including a couple right now to start things off right!
How will we know, when the morning comes, we are still human? - 2D
Don't worry, my friend. If this be the end, then so shall it be.
Here's the very first Riddler puzzle, posted by Oliver Roeder on December 11, 2015:
[quote]Now, here’s this week’s inaugural Riddler, which comes to us from Laura Feiveson, an economist at the Federal Reserve’s Board of Governors:
You work for a tech firm developing the newest smartphone that supposedly can survive falls from great heights. Your firm wants to advertise the maximum height from which the phone can be dropped without breaking.
You are given two of the smartphones and access to a 100-story tower from which you can drop either phone from whatever story you want. If it doesn’t break when it falls, you can retrieve it and use it for future drops. But if it breaks, you don’t get a replacement phone.
Using the two phones, what is the minimum number of drops you need to ensure that you can determine exactly the highest story from which a dropped phone does not break? (Assume you know that it breaks when dropped from the very top.) What if, instead, the tower were 1,000 stories high?[quote]
I haven't looked at the answer, and I don't immediately see how to solve it, so here are my thoughts written out on how to get towards a solution:
Obviously, the naive manner of correctly determining this would be to drop it from Story 1 ("S1"), then, if it doesn't break, from S2, and so on, until you get to S100, where you know it will break. Clearly, by this method you will need 99 drops to *ensure* you know the highest story you can drop it from.
A slight improvement would be to drop it from every even-numbered floor in ascending order. If you drop it from S2, and it breaks, then drop the back-up phone from S1. If it doesn't break from S2, drop it from S4. And so on. You'll eventually hit a point where it's ok at S(n) but not S(n+2); then you just need to drop the back-up from S(n+1) to see if the highest is either S(n) or S(n+1). By that method, you'll need at most 50 drops (S2, S4 through possibly S98, and then the corresponding even one).
If you had an unlimited number of phones, the best strategy would be to do it by powers of 2: drop Phone 1 from S50; if it breaks, do the next one at S25, and if it doesn't, go up to S75. You'll eventually get a sequence like: S50 - Break, S25 - Ok, S37 - OK, S43 - Break, S 40 - Break, S39 - Break, S38 - Break. Then you know it's S37. So, if you have an unlimited number of phones, the number of drops you'd need would just be log_2 (100), rounded up, which is 7 (that is, the number of drops you'd need, x, would be whatever x is such that 2^x > number of stories).
The problem, of course, is that you don't have limited phones - just two. So, whatever you do with the first phone, you need to save the second phone for precision (that is, to fine-tune by counting up one story at a time).
So, based on all that, here's my first guess towards a solution. I'm not convinced this is the best method, only that it's a reasonable guess that I'll need to spend some time thinking about improving:
The first really solid strategy that appears is to do this:
Drop phone 1 from S10, and if it breaks, drop phone 2 from S1, then S2... until it breaks. If S10 doesn't break phone 1, drop it from S20, S30 and so on until it breaks and S(10*n), and then use phone 2 to count upwards from S(10*n - 9) to S(10*n - 1). The greatest number of drops you would need is [bold]eighteen[/bold], a maximum of nine drops for phone 1 (S10, S20... S90) and a maximum of nine drops for phone 2 (S(10*n - 9), S(10*n - 8)... S(10*n - 1)).
So, my question becomes, is that the best strategy, though? I'm going to think about it for a little bit. If you think you have the answer, and want to check it against mine, go ahead and post if yours is better! Or post anything else that comes to mind, variations on the problem, etc. I haven't addressed the 1000 story variation (although I think my solution above could be easily extended to that case), so if you have thoughts on that post them as well!
How will we know, when the morning comes, we are still human? - 2D
Don't worry, my friend. If this be the end, then so shall it be.
(February 25, 2016 at 5:06 am)ignoramus Wrote: If you only get 2 phones, 9 and 9 I think is a guaranteed solution. (18 moves max)
Tthere are other riskier moves with less potential total moves, but with no guarantee of an absolute answer.
I tend to agree. This should then mean that, for 1000 stories, the max should be 2 * (square root of 1000, rounded down) = 62.
The strategy's the same, except instead of going S10, S20... S90 with the first phone and using the second phone to fine tune the nine stories between each decade, you go S32, S64... S960, S992 (thirty-one) and then use the second phone to fine tune the 31 stories between each thirty-second. You end up not quite even (at floor 992, with only 7 possible floors above) because 1000 is not a perfect square.
Let's see what the solution on the site says:
NO WE ARE WRONG!!! We can do better!!!
Discussion of the correct solution, and why we are wrong:
Having seen the solution, I understand what our problem is. From a broad standpoint, we were looking at it geometrically when we should've been looking at it triangularly! Our solutions were a good effort, but were inefficient inasmuch as there were too many times there would only be a couple of drops needed, and we could have better leveraged this into a solution that lowered the ceiling of how many drops we'd need (which is what we want to minimize) at the expense of raising the floor (which we don't care about).
The lowest number is 14. This is because 1 + 2 + ... + 14 > 100, and you can make it so that, if phone 1 breaks after x drops, you only need 14 - x drops with the second phone to fine-tune it.
The strategy is this:
Drop from S14, S27, S39, S50, S60, S69, S77, S84, S90, S95, S99. If phone 1 breaks after the first drop - S14 - then you need 13 drops with phone 2 to fine-tune. If it's the second drop that breaks phone 1, well, there are now only twelve stories from S15 to S26. And so on: every extra drop with phone 1, you set it up so that there's one fewer floor to test.
That means that the strategy for 1000 gets us 45 drops, as 1 + 2 + ... + 45 = 1035 > 1000.
So, open challenge to anyone who saw my and Ignoramus's reasonable but ultimately incorrect efforts: POST YOUR BETTER SOLUTION BELOW (without cheating, sucka) AND YOU WILL GET MAJOR PROPS FROM ME AND MAYBE A REP
I'll post The Riddler No. 2 later today!
How will we know, when the morning comes, we are still human? - 2D
Don't worry, my friend. If this be the end, then so shall it be.
This is the 2nd puzzle in FiveThirtyEight's The Riddler series, in which Oliver Roeder posts an interesting math/creative thinking-ish brain-teaser every Friday. I'll post either my solution (if I can come up with one) or my initial thoughts (if I don't see how to solve it) in hide tags, and everyone is welcome to give it a go! I have promised a rep to people who solve a problem that I got wrong
Quote:Now, here’s this week’s Riddler, which comes to us from Brian Galebach, an amateur mathematician from Columbia, Maryland:
You arrive at the beautiful Three Geysers National Park. You read a placard explaining that the three eponymous geysers — creatively named A, B and C — erupt at intervals of precisely two hours, four hours and six hours, respectively. However, you just got there, so you have no idea how the three eruptions are staggered. Assuming they each started erupting at some independently random point in history, what are the probabilities that A, B and C, respectively, will be the first to erupt after your arrival?
This was the first Riddler question I read, and I saw how to solve it straight away (it just took a little bit to work out the numbers). Here's my groundwork - my initial way of thinking about the problem - which you can check out if you want a hint:
This question looks tough because it may not appear that there's enough information, but it's really a pretty straightforward "plug-and-chug" probability problem when you see how to do it.
They call the geysers A, B and C - I'm going to call them A2, B4, and C6, just so we can easily remember how often every one erupts. In the problem, you walk up and look at the geysers; you don't know when any of them last erupted, but you can reason out that a) A2 is guaranteed to erupt in the next 2 hours, b) B2 is guaranteed to erupt in the next 4 hours, and c) C6 is guaranteed to erupt in the next 6 hours. Put another way, A2 will definitely erupt in the next two hours, B2 has a 1/2 chance of erupting in the next two hours, and C6 has a 1/3 chance of erupting in the next 2 hours. Luckily for us, each of these probabilities is independent.
And then here's the solution:
So, let's consider the probability that A2 erupts first. There's a 100% chance A2 erupts in the next two hours; if B4 and C6 don't erupt in the next two hours, A2 erupts first by default. If both A2 and B4 erupt in the next two hours (but C6 doesn't), then there's a 50% chance A2 is first and a 50% chance B4 is first (simply because there's two of them, and - if we assume they're both going to erupt in the next two hours - they're equally likely to go first). If both A2 and C6 erupt in the next two hours, there's again a 50% chance A2 goes first and 50% chance C6 goes first. Finally, if they all erupt in the next 2 hours, there's a 1/3 chance A2 is the first to erupt.
Blah. So, that gives us this:
(Probability A2 erupts first) = (Probability only A2 erupts in the next two hours)*(100%) + (Probability A2 and B4 erupt in the next two hours and C6 doesn't)*(50%) + (Probability A2 and C6 erupt in the next two hours and B4 doesn't)*(50%) + (Probability all three erupt in the next two hours)*(33.3...%)
We know all of these probabilities:
Probability A2 erupts in the next 2 hours = 100% = 1
Probability B4 erupts in the next 2 hours = 50% = 1/2, which means the probability it doesn't erupt in the next 2 hours is also 1/2
Probability C6 erupts in the next 2 hours = 33.3...% = 1/3, which means the probability it doesn't erupt in the next 2 hours 1 - 1/3 = 2/3
That one was a bit easier if you're not afraid of fractions I haven't looked at any of the remaining problems, so I'll be working through them on here over the coming days! POST YOUR SOLUTIONS AND SHOW ME HOW AWESOME YOU ARE.
Joe's Record through 2 Riddler Puzzles: 1-1
How will we know, when the morning comes, we are still human? - 2D
Don't worry, my friend. If this be the end, then so shall it be.
This is the 3rd puzzle in FiveThirtyEight's The Riddler series, in which Oliver Roeder posts an interesting math/creative thinking-ish brain-teaser every Friday. I'll post either my solution (if I can come up with one) or my initial thoughts (if I don't see how to solve it) in hide tags, and everyone is welcome to give it a go! I have promised a rep to people who solve a problem that I got wrong
I'm one for two; as noted above, I crashed and burned on the first one but was able to brute force the second. I haven't looked at this one yet, so, let's see if this will join the "stumps Joe" category:
Quote:Now, here’s this week’s Riddler, which comes to us from Olivia Walch, a mathematics Ph.D. student and cartoonist:
You’ve just finished unwrapping your holiday presents. You and your sister got brand-new smartphones, opening them at the same moment. You immediately both start doing important tasks on the Internet, and each task you do takes one to five minutes. (All tasks take exactly one, two, three, four or five minutes, with an equal probability of each). After each task, you have a brief moment of clarity. During these, you remember that you and your sister are supposed to join the rest of the family for dinner and that you promised each other you’d arrive together. You ask if your sister is ready to eat, but if she is still in the middle of a task, she asks for time to finish it. In that case, you now have time to kill, so you start a new task (again, it will take one, two, three, four or five minutes, exactly, with an equal probability of each). If she asks you if it’s time for dinner while you’re still busy, you ask for time to finish up and she starts a new task and so on. From the moment you first open your gifts, how long on average does it take for both of you to be between tasks at the same time so you can finally eat? (You can assume the “moments of clarity” are so brief as to take no measurable time at all.)
Hmmm.............................. Initial thoughts below in hide tags, then I'll open the floor to discussion before I post an attempted solution or an admission of defeat!
Interesting. At first glance, this looks similar to Problem 2 in that it appears to be solvable by multiplying probabilities, to get P(1 Minute) + 2*P(2 Minutes) + 3*P(3 Minutes) + ... and so on. Of course, we may need to use some sort of trick to calculate that infinite sum. Hopefully, it will simplify to a very straightforward geometric sequence, so we can just add it up using (1 + n + n^2 + n^3 + ...) = 1/(1-n).
Another way of looking at it, which might be easier if the above math doesn't come easily or obviously, would be to look at the probability of changing between states. There are essentially nine different states:
1) You're clear but your sister has 1 minute left;
2) You're clear but your sister has 2 minutes left;
3) You're clear but your sister has 3 minutes left;
4) You're clear but your sister has 4 minutes left;
5) You have 1 minute left but your sister is clear;
6) You have 2 minutes left but your sister is clear;
7) You have 3 minutes left but your sister is clear;
8) You have 4 minutes left but your sister is clear;
9) You're both clear.
If we view it this way, we'll be trying to figure out the probability of a given state 1-8 transitioning into state 9, and then adding up probabilities of that happening.
The ways of thinking about it above are, of course, similar, though one sort of moves minute-by-minute and the other moves task-by-task. The minute-by-minute approach seems more natural, and is what I'll try first, but I'm not sure which will eventually yield the answer. If we get an answer with one, it would behoove us to see if that makes sense when viewed through the lens of the other.
So, that's my thoughts on that! Time to put pen to paper. THIS GOES FOR YOU ALL TOO. REMEMBER, there is a SHINY NEW REP for someone who solves a problem I get wrong!!!
Good huntin'!
How will we know, when the morning comes, we are still human? - 2D
Don't worry, my friend. If this be the end, then so shall it be.
This is the 3rd puzzle in FiveThirtyEight's The Riddler series, in which Oliver Roeder posts an interesting math/creative thinking-ish brain-teaser every Friday. I'll post either my solution (if I can come up with one) or my initial thoughts (if I don't see how to solve it) in hide tags, and everyone is welcome to give it a go! I have promised a rep to people who solve a problem that I got wrong
I'm one for two; as noted above, I crashed and burned on the first one but was able to brute force the second. I haven't looked at this one yet, so, let's see if this will join the "stumps Joe" category:
Quote:Now, here’s this week’s Riddler, which comes to us from Olivia Walch, a mathematics Ph.D. student and cartoonist:
You’ve just finished unwrapping your holiday presents. You and your sister got brand-new smartphones, opening them at the same moment. You immediately both start doing important tasks on the Internet, and each task you do takes one to five minutes. (All tasks take exactly one, two, three, four or five minutes, with an equal probability of each). After each task, you have a brief moment of clarity. During these, you remember that you and your sister are supposed to join the rest of the family for dinner and that you promised each other you’d arrive together. You ask if your sister is ready to eat, but if she is still in the middle of a task, she asks for time to finish it. In that case, you now have time to kill, so you start a new task (again, it will take one, two, three, four or five minutes, exactly, with an equal probability of each). If she asks you if it’s time for dinner while you’re still busy, you ask for time to finish up and she starts a new task and so on. From the moment you first open your gifts, how long on average does it take for both of you to be between tasks at the same time so you can finally eat? (You can assume the “moments of clarity” are so brief as to take no measurable time at all.)
Hmmm.............................. Initial thoughts below in hide tags, then I'll open the floor to discussion before I post an attempted solution or an admission of defeat!
[hide]
Interesting. At first glance, this looks similar to Problem 2 in that it appears to be solvable by multiplying probabilities, to get P(1 Minute) + 2*P(2 Minutes) + 3*P(3 Minutes) + ... and so on. Of course, we may need to use some sort of trick to calculate that infinite sum. Hopefully, it will simplify to a very straightforward geometric sequence, so we can just add it up using (1 + n + n^2 + n^3 + ...) = 1/(1-n).
Another way of looking at it, which might be easier if the above math doesn't come easily or obviously, would be to look at the probability of changing between states. There are essentially nine different states:
1) You're clear but your sister has 1 minute left;
2) You're clear but your sister has 2 minutes left;
3) You're clear but your sister has 3 minutes left;
4) You're clear but your sister has 4 minutes left;
5) You have 1 minute left but your sister is clear;
6) You have 2 minutes left but your sister is clear;
7) You have 3 minutes left but your sister is clear;
8) You have 4 minutes left but your sister is clear;
9) You're both clear.
If we view it this way, we'll be trying to figure out the probability of a given state 1-8 transitioning into state 9, and then adding up probabilities of that happening.
The ways of thinking about it above are, of course, similar, though one sort of moves minute-by-minute and the other moves task-by-task. The minute-by-minute approach seems more natural, and is what I'll try first, but I'm not sure which will eventually yield the answer. If we get an answer with one, it would behoove us to see if that makes sense when viewed through the lens of the other.
So, that's my thoughts on that! Time to put pen to paper. THIS GOES FOR YOU ALL TOO. REMEMBER, there is a SHINY NEW REP for someone who solves a problem I get wrong!!!
Good huntin'![/hide]
I know this is sort necropost but 1) it's my own thread I created for my own special purpose and 2) I've just thought about the problem for the first time since I posted it and 3) EvieAlasdair Ham necro'd it already a few weeks ago so it's his fault
So, here's my best shot? Whether I'm right or wrong, I am absolutely certain there is an easier way to do this. But this is the most *obvious* way to me, even if it's exceedingly tedious and involved:
The first person's task can be either 1, 2, 3, 4 or 5 minutes, and same for person #2. There are 5 ways they can be the same ((1,1), (2,2)...), 8 ways they can be 1 minute off ((1,2), (2,3), (3,4), (4,5), (2,1)...), 6 ways they can be 2 minutes off, 4 ways for 3 minutes off, and 2 ways for 4 minutes off. If they're 1 minute off, then there's a 20% chance the lower person matches up, a 20% chance they move to 1 minute off, a 20% chance they move to two minutes off, a 20% chance they move to 3 minutes off, and a 20% chance they move to 4 minutes off. If they're 2 minutes off, there's a 40% chance they move to one minute off (if the next task is either 1 or 3 minutes), a 20% chance they match, a 20% they stay at 2 minutes off, and a 20% chance they go to 3. If 3 minutes off, it's 20% match, 40% 1 minute, 40% 2 minutes. If 4 minutes off, it's 20% match, 40% 1 minute, 20% 2 minutes, and 20% 3 minutes.
We're also going to keep a running count of the "total time", which we'll define as the amount of time committed by the lengthier person. So, if Dude 1's first 3 tasks are 2, 5, 3 and dude 2's first 3 tasks are 1, 2, 5 we'll call the total time marker = 10. This means that some changes (ie, if person 1's two minutes back and gets a 3 minute task) will change the "state" and the TT, some will change the TT but not the state, and some will change the state and not the TT.
So, the probabilities of changing from one phase to another phase are like this:
1 off -> match, TT + 0 = 20%
1 off -> 1 off, TT + 1 = 20%
1 off -> 2 off, TT + 2 = 20%
1 off -> 3 off, TT + 3 = 20%
1 off -> 4 off, TT + 4 = 20%
2 off -> 1 off, TT + 0 = 20%
2 off -> match, TT + 0 = 20%
2 off -> 1 off, TT + 1 = 20%
2 off -> 2 off, TT + 2 = 20%
2 off -> 3 off, TT + 3 = 20%
3 off -> 2 off, TT + 0 = 20%
3 off -> 1 off, TT + 0 = 20%
3 off -> match, TT + 0 = 20%
3 off -> 1 off, TT + 1 = 20%
3 off -> 2 off, TT + 2 = 20%
4 off -> 3 off, TT + 0 = 20%
4 off -> 2 off, TT + 0 = 20%
4 off -> 1 off, TT + 0 = 20%
4 off -> match, TT + 0 = 20%
4 off -> 1 off, TT + 1 = 20%
Whew.
Now that we have that done... what next? Well, I think we get to misbehave, and do something that feels wrong but isn't: add expected values together. We can do this because, at every level, the probabilities are symmetrical. So, from the beginning, the average state is: Match = 20%, 1 off = 32%, 2 off = 24%, 3 off = 16%, and 4 off = 8%, and the corresponding average TTs are Match = 3, 1 off = 3.5, 2 off = 4, 3 off = 4.5, and 4 off = 5.
At every new task, the chance of matching is 20%. So, basically, we're going to have a series that looks like this: 20% * (TT after initial picks) + 80% * 20% * (average (delta)TT from stage 1 to stage 2) + 80%^2 * 20% * (average (delta)TT from stage 2 to stage 3) + ... and so on.
If we can simply figure out the average distribution of 1/2/3/4 at each stage, then we can get the average (delta)TT at that stage, and plug and chug, as it were.
The stage 1 distribution of 1:2:3:4 is 40%:30%:20%:10% (that's the 8 ways, 6 ways, 4 ways, 2 ways from above). We also know the following (non-match) probabilities, along with average delta(TT):
So, every time we start with 1, we have an average TT increase of 2.5 (average of 1, 2, 3, 4). With 2, we have 1.5. With 3, we have .75, and with 4, we have .25.
The initial distribution goes from 40/30/20/10 to 10 (chance of going from 1 to 1)+15 (chance of going from 2 to 1)+10 (etc)+5/10+7.5+10+2.5/10+7.5+0+2.5/10+0+0+0 = ... wouldn't you know, 40/30/20/10. This is PERFECT, because that means that the average TT increase is the same at each level because the average state distribution is the same at each level!!!
So, the average TT increase at each level, if there's no match, is = .4*2.5 + .3*1.5 + .2*.75 + .1*.25 = 1 + .45 + .15 + .025 = 1.625. Because this happens 80% of the time, and the other 20% there's a match and the TT doesn't increase, the average TT increase at each level is 1.625*.8 = 1.3
The last thing to do is to calculate the first TT, the average TT after 1 pick: .2*3 + .32*3.5 + .24*4 + .16*4.5 + .08*5 = .6 + 1.12 + .96 + .72 + .4 = 3.8.
So, the average time is:
3.8 + .8*1.3 + .8^2*1.3 +... which is a perfectly straightforward geometric sequence, which sums to (1.3/(1-.8)) + 3.8 = (5.2 + 3.8) = 9 minutes.
Big Reveal, time to check if I'm correct:
YES, I'M CORRECT! But that's small comfort, because the solution given in the Riddler (which I've put in the hide tags below) is basically four lines long (mine in the hide tags above is 73 lines long):
The average time between moments of clarity is (1+2+3+4+5)/5 = (5+1)/2 = 3 minutes.
So, the probability that a particular minute will end with a moment of clarity is 1/3.
This is independent for both siblings.
So, on average, you sync up at the end of 1/9 of minutes.
Well... I got it right. But my solution certainly won't be in "the book".
How will we know, when the morning comes, we are still human? - 2D
Don't worry, my friend. If this be the end, then so shall it be.
![[Image: dc52deee8e6b07186c04ff66a45fd204.jpg]](https://images.weserv.nl/?url=i585.photobucket.com%2Falbums%2Fss295%2Faaliyahqin%2Fcat%2Fdc52deee8e6b07186c04ff66a45fd204.jpg)
