FiveThirtyEight Riddler

[albionmoonlight]

This board used to have a thing for puzzles. 538.com has a weekly puzzle column that seems to capture the style we like.

Here's this weeks version: How Many Cars Will Get Stuck In Traffic? | FiveThirtyEight

The answer might be on google. I am positing it here to see if we can figure it out. Right now, I am having trouble even figuring out a starting place. My gut says that the answer should be something like N/2. But I have no idea how to get there (or if my gut is anything close to right).

[cartman]

2/3rds

[QuikSand]

Cool, first I've heard of the feature there.



I know phrases like this can become unravelers:

Each preferred speed is chosen at random.

I think we spent some time here back in the day with a classic "two envelopes" puzzle that basically becomes an internal paradox due to something similar.

[QuikSand]

Originally Posted by albionmoonlight

This board used to have a thing for puzzles.

Accurate.

[cartman]

I think it is like if you take a deck of cards, and use the values to equate to speed. So it will be N=number of cards and S=Speed. So the equation would be something like ((N-1)/S, (N-2)/S...)/N

But I failed Calculus three times in college, so take that for what it is worth.

[albionmoonlight]

One approach would be to start with small N and see what pattern develops. For n=1, you have 1 group. For n = 2, you average 1.5 groups. For n=3, you average 11/6 groups (~1.8).

So this might be a calculus problem with some answer as N approaches infinity.

[QuikSand]

that sounds promising

[QuikSand]

Just spitballing...

the slowest car creates a group, period (even with zero behind it)

the next slowest car creates a separate group unless it's immediately behind the slowest one (p=some weird but solvable function of n)

the third slowest car... etc etc etc


Probably amounts to the same limit sequence as you're setting up above, but just via intuition I think I'm getting to a similar place.

[albionmoonlight]

More spitballing:

the slowest car will be first 1/n times (one group)
it will be in second 1/n times (two groups)
the problem gets more complicated once the slowest car is in third or later.

But there does seem to be weight keeping the number lower than one might expect. 2/n times, you end up with one or two groups

[britrock88]

We have N cars with speeds assigned by a non-duplicative RNG.

You have a 1/N chance of 1 group if car 1 is the slowest and a 1/(N-1) chance of 2 groups is car 2 is the slowest. But starting with car 3, you have to reiterate the probability calculation for the multiple cars ahead of car n.

[Solecismic]

This is what I submitted:

1 + 1/2 + 1/3 + ... + 1/N

We have to assume a road of infinite length, and we have to assume cars may travel at an infinite number of different speeds to preserve independence. Otherwise, a collision would make it impossible to determine the true number of packs due to the interference of emergency vehicles and rubberneckers. The Twitter ramifications alone are enormous.

The answer is a series beginning with one pack. There's always at least the one pack. How do we get a second pack. That's if the first car isn't the slowest. Or 1 - 1/2. And a third pack? That's if the first car found after the first slower car isn't the slowest. Or 1 - 1/3 - 1/3. We keep adding the chances of finding a new pack. Keep in mind that the chance of finding N packs isn't 1/N in itself - it's 1/N!. But there's a (N-1)! "weight" attached to that event when calculating the average of our infinite number of iterations.

[EagleFan]

I say there is not enough information given to formulate an answer.

10 mile road... 20 cars... speed range 60 mph - 70 mph

gives you a different result than

5 mile road... 50 cars... speed range 25 mph - 60 mph

[rowech]

Fairly certain the answer is 2(1-.5^N). Ultimately, I think it's just a geometric series with r = .5 and I just used the summation formula for such a series. I fear there has to be more than this because that summation goes to 2 with an infinite number of cars and I think there has to be more than two groups that form. It just doesn't seem right.

[Solecismic]

Turns out the answer is 1 + 1/2 + 1/3 + ... + 1/N. But the explanation is a lot more complex than what I submitted. This week, it's ducks on a pond.

[QuikSand]

With the duck/dog, I think the logic must be obvious, but the calculation is trickier, to me.

Dog starts at 12 (on the clock) so the duck heads toward 6 (at least that seems obvious to me). Dog flips a coin and goes toward the 1. But as the dog's location changes, I presume the duck no longer chooses a direct route toward the 6 as his optimal route, he likely curves away from the dog's side...toward the 7.

I'm assuming there's some way to calculate the path/vector of the duck as a function of the location of the dog, and that it creates visually some sort of seashell like spiral. But the math in calculating all this is either non-obvious, or is simply beyond my knowledge/recollection.

Hmmm...i guess if the duck is perpetually just aiming for the spot diametrically opposed to the dog's location, that might not be impossible to sort out.

[Solecismic]

Yes, that's where I'd head with this question. The dog always aims for the spot on the shore closest to the duck and duck always aims for the spot furthest from the dog. That would create some sort of spiraling curve.

The initial relationship is 2π. So, what you have to prove, if the problem is relatively simple, is that by following this strategy, the dog is never in a worse situation than when the duck is in the middle if it can travel that fast.

[QuikSand]

So, I'm thinking about right triangles here... right, this ends up being a trig problem?

[ColtCrazy]

Sounds like there should be a math solution. The dog must travel half the circumference at least as fast as the duck can travel the radius. Wouldn't that mean the dog would have to travel pi times faster?

But that doesn't take in a sudden turn by the duck, which means the dog would have to travel even faster to make up for the turn.

[ColtCrazy]

Originally Posted by QuikSand

So, I'm thinking about right triangles here... right, this ends up being a trig problem?

I think you are right. Assuming the duck turns at the last moment and moves diagonally, the duck should travel the radius and the hypotenuse of a right triangle to get to another quarter way around the lake. This means the dog would have to go 3/4 around the lake in the same time to catch the duck. I got that far.
I tried comparing those and got that the dog needs to be about 4 times faster (I got 3.9 and some change).

[QuikSand]

So, I'm thinking this is pretty tricky. If again, we assume that the duck continues to pursue the direction across from the dog at all times, then his amount of progress toward the perimeter will actually decrease over time, as the amount of lateral motion he needs increases linearly as he moves away from the center.

...and as I type this, I think I'm reaching a reductio ad absurdum with my premise there. Clearly the duck is gong to engage in some sideways evasion, but before too long he can't simply go in the "opposite" direction of the dog, who will be in the same side as him. So, his best path is some function, that I strongly suspects is of his distance from the center, but I don't have any way to express it.

[Solecismic]

Originally Posted by ColtCrazy

Sounds like there should be a math solution. The dog must travel half the circumference at least as fast as the duck can travel the radius. Wouldn't that mean the dog would have to travel pi times faster?

But that doesn't take in a sudden turn by the duck, which means the dog would have to travel even faster to make up for the turn.

Yes, I counted r twice when I shouldn't have. The initial relationship is π. So, what is the relationship if the duck changes direction at some instant a after the simulation begins? Well, the dog is still πr away, but the duck is probably closer. What's the limit, though? Set a at 1/2r. The duck is now sqrt(5/4r) away from the shore along his new path. There's no way that's a good choice for the duck. So we know that the duck is best off if it either stays on its initial course or makes a change in the first half of its journey.

What if a is 1/9r? Where's the dog? He's at an angle of about 20 degrees from his starting point and he still has to travel πr. The duck is at .9r/.9397 or .9577r from his new destination. That's progress. So the simple case is ruled out. In fact, as long as the duck makes his change before the dog has traveled one sixth of the way around the half-circle, the duck has made progress and will reach shore safely. This is a complex problem as the dog will travel in a circle while the duck will travel in some form of what I guess is an Archimedian spiral.

The curvature of the spiral should be the maximum at which the dog never changes direction.

However, I've long since lost the geometry and calculus skills required to solve this problem.

[cuervo72]

Originally Posted by Solecismic

However, I've long since lost the geometry and calculus skills required to solve this problem.

Yeah. These aren't just logic puzzles, they are math puzzles. I've looked at the solutions for this, and while I can grasp them there's no way I'd easily be able to calculate them on my own, not 20 years out from studying any of this.

[Toddzilla]

So the duck would necessarily have to always be traveling to the exact opposite part of the circle that the dog was positioned - since neither the dog nor the duck lose speed when changing directions, there is no advantage to turning suddenly.

Let's take this one "minute" at a time
So if the Dog is at 12 o'clock, the duck swims toward 6.
The dog picks a direction - say clockwise.
When the dog gets to 12:01, the duck will be heading towards 6:01.
When the dog gets to 12:02, the duck will be heading towards 6:02.
...
except when the dog get's off of 12:01, the duck has moved a distance of x from the center of the circle - in the direction of 6 - and now travels directly opposite of the dog which is no longer headed towards 6:02. This would be almost towards 6:02, but shorter (I'll show my work later)

so as each "minute" passes, the dog proceeds around the clock clockwise and for each minute the dog moves, the duck moves in a curve each time moving less than a minute and getting shorter each time.

i think.

[Toddzilla]

https://pbs.twimg.com/tweet_video/CbMQQCOUAAA1OPS.mp4

sweet

[QuikSand]

Originally Posted by Toddzilla

So the duck would necessarily have to always be traveling to the exact opposite part of the circle that the dog was positioned - since neither the dog nor the duck lose speed when changing directions, there is no advantage to turning suddenly.

Let's take this one "minute" at a time
So if the Dog is at 12 o'clock, the duck swims toward 6.
The dog picks a direction - say clockwise.
When the dog gets to 12:01, the duck will be heading towards 6:01.
When the dog gets to 12:02, the duck will be heading towards 6:02.
...
except when the dog get's off of 12:01, the duck has moved a distance of x from the center of the circle - in the direction of 6 - and now travels directly opposite of the dog which is no longer headed towards 6:02. This would be almost towards 6:02, but shorter (I'll show my work later)

so as each "minute" passes, the dog proceeds around the clock clockwise and for each minute the dog moves, the duck moves in a curve each time moving less than a minute and getting shorter each time.

i think.

Problem is, the math here no longer works once the duck's distance from the center is of a greater ratio to the dog's distance than the ratio of their speeds. If duck is speed x and dog is speed 5x, say, then at some point the duck gets more than 1/5 of the way out from the circle, and he can no longer keep up with the concept of evading the dog and continuing to move outward. From that point on the dog is catching up.

I'm with the group above - I will read the eventual solution with interest, and I find the scripting and graphical representations amusing... but the math is beyond me, it seems.

[Toddzilla]

check the graphic, i think that explains my premise well

[albionmoonlight]

New puzzler is up. I've seen this one before, so I knew the answer. It did stump me when I originally saw it, though. This one you can get with logic. No need to resort to calculus.

[cuervo72]

My inclination is to say 50/50. There is a 1/100 chance that WPA sits in your seat. There is a 1/100 chance that WPA sits in WPA's seat, breaking the chain. The former means you don't get your seat, the latter means you do. If neither happens, we repeat the process. Each iteration equally adds to the chance of filling your seat or filling the WPA's seat -- down to two seats, where the second-to-last boarder has a 50/50 shot of grabbing either WPA's or yours if one hadn't been already.

I don't know, maybe there is some compounding of probability that I'm missing, but that would be my basic logic.

[QuikSand]

I think it's close to 50/50, but slightly less.

Two cases with the initial passenger -- he either sits in his seat (1/100) or not (99/100).

Assuming not, then there is always one person out of place on the plane... meaning than when passenger 99 sits, he's 50/50 to find his seat occupied. So, 99% of the time, it's a 50% chance your seat is taken by the second to last passenger.

Assuming the first passenger happens to land in his proper seat, then everyone gets his own seat, and your chances of being in your seat are 100%.

So... I make it at (0.5 * 0.99)+(0 * 0.01) = 0.495

[QuikSand]

hmmm... maybe have failed to account for the WPA sitting in your seat as a separate case...

[QuikSand]

So... I make it at:

WPA in his seat = 1% chance * if so then 0% chance yours is taken
WPA in your seat = 1% chance * if so then 100% chance yours is taken
WPA in other seat = 98% chance * if so then 50% chance yours is taken

And summing those gets right back to 50%. Yup.

[albionmoonlight]

50% is the answer I have seen before.

[Solecismic]

It has to be 1/2, no matter how many seats there are on the plane.

[QuikSand]

Looks like we missed a week, but here's a new one...

Can You Win This Hot New Game Show? | FiveThirtyEight

Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?

[QuikSand]

So...instinct surely starts you with a number of 0.5, right? Higher than that and the EV of your second value is lower than what you have in hand.

Making it a two-person game, I presume, has some recursive issue, then. Because the EV of another person's final value of 1-2 numbers isn't normally distributed, then you no longer simply shoot for the highest possible value.

I don't yet have a clear idea how to calculate this... but I assume that to maximize your chances of winning (rather than just maximizing the value of your number) then you have to turn the range into a binary setup = where you're looking at P (your score > EV of other player's score).

And somehow, since both players have the same information and motivation, I assume this has to converge for both players.












Aww, hell, how about 2/3.

[albionmoonlight]

So if it were just me trying to get the largest number, I would keep anything over .5 and redo anything under .5 (no idea what I would do with .5 on the nose, but let's leave that out of it).

That means, I think, that I would keep half of my rolls. Because they are all above .5 distributed randomly, they would average .75.

I would redo half my rolls, which would average .5.

So my final average would be (.5 * .75) + (.5 * .5). Which would equal .625. Not quite 2/3

Now, my opponent could also get to .625 using the same simple strategy.

So what's the next step? Or is .625 the best either of us can do?

[QuikSand]

So, let's say I assume you're going with the .625 strategy.

Sketching through whether I do better by tinkering based on that. What if I set my bar a shade higher, say at 0.6 (I keep everything below that and reroll above it)?

My EV is easy:
low rolls .6 x .5
high rolls .4 x .8
=total EV of .620

But mapping "who wins" is different, right?

Assuming there's some calculus that can solve the likelihood of winning each of those four quadrants (set this up like a number theory matrix)...then it seems it must be possible to pick a strategy that "beats" your .625 strategy. Right? Otherwise why publish the puzzle at all?

I'm still stuck that this is some sort of recursive thing...you move to .625, I beat that my adjusting a little, then you adjust downward, I adjust upward, and we both meet at some equilibrium in the middle. I'm lacking the math, but comfortably accepting guidance from the human context here, and assuming there's some perfect balance that represents optimal strategy by the player who knows his opponent will also employ optimal strategy.

[QuikSand]

So, I guess the "who wins" between two random number between 0 and p1 and between 0 and p2 looks like this (where p2>p1, and both are expressed as decimals between 0 and 1):

((p2-p1)/p2) = situations where the p2 always wins
(p1/p2) = situations where the wins are evenly split

(and there's an inverse for the values between a certain value and 1)

Not as bad as I had thought initially. So, in my example above... I think the math looks like this:

p1 = 0.5 (albion chooses to re-roll everything below 0.5)
p2 = 0.6 (Quik choses to re-roll everything below 0.6)

Grid out the four outcomes, using the above:
P1 keeps, P2 keeps
P1 keeps, P2 rerolls
P1 rerolls, P2 keeps
P1 rerolls, p2 rerolls

...and I'm guessing that despite a lower overall EV, that the 0.6 strategy wins more than it loses. (I'll fill in the math above with brute force if I can get my kids in line sometime today)

Then you figure out what function guides this. Presumably it could be done fairly well with brute force and Excel, but it also likely sorts out to one big formula, I suppose.

[Radii]

Originally Posted by QuikSand

Otherwise why publish the puzzle at all?

This is where I ended up, after not really being able to figure out why the answer isn't .5 as your cutoff point to re-rolling. If the answer was to keep anything above 0.5 and roll anything below, surely they wouldn't have bothered to pose the question. I look forward to the explanation.

[QuikSand]

Here's what I come up with:

Grid out the four outcomes, using the above:
P1 keeps, P2 keeps: likelihood = 0.2, p(P2 wins) = 0.6, aggregate p(P2 wins) = 0.120
P1 keeps, P2 rerolls: likelihood = 0.3, p(P2 wins) = 0.25, aggregate p(P2 wins) = 0.075
P1 rerolls, P2 keeps: likelihood = 0.2, p(P2 wins) = 0.8, aggregate p(P2 wins) = 0.160
P1 rerolls, p2 rerolls: likelihood = 0.3, p(P2 wins) = 0.5, aggrebate p(P2 wins) = 0.150
TOTAL p(P2 wins) = 0.505

So...in the event I have the math right above, choosing 0.6 as your breakeven point is a FAVORITE to beat a player who picks 0.5 as his, even though it doesn't maximize the expected value of the outcome.

[QuikSand]

So, break all this down into one formula, it has a maximum point (derivative zero?) at some value. .6 is better than .5, I'm guessing.

[Solecismic]

You're not trying to maximize your expected value; you're trying to maximize your chances of beating your opponent's expected value.

[Solecismic]

Against the .5 opponent, 7/12 is your best play, based on taking that derivative. This gets into calculus I've long since forgotten if that hypothesis doesn't hold true against any opponent. My guess is that the answer is close to 7/12, though, because these curves are very flat.

[Maple Leafs]

This riddle made me feel dumb. Then I went to the 538 site and read the comments from people who were completely perplexed by the concept of "between 0 and 1" and I felt smart again.

[albionmoonlight]

But if .6 beats .5, then don't both players then use .6? Which then means that .6 may not be the best strategy.

Which, of course, is another way of saying Quik's equilibrium point above.

[Maple Leafs]

In searching for the airplane riddle you guys were mentioning, I found this site that tries to solve the game show puzzle with code.

The result is... well, probably not especially satisfying. Spoiler warnings, obviously.

The 538 Riddler: Hot New Game Show – Some Disagree

[Vince, Pt. II]

This week's version is the first one I've gotten intuitively from the get go.

[Vince, Pt. II]

Apparently only the first half though...I find that I am unable to determine whether or not she would know if he says no. Which tells me that perhaps I'm wrong on the first half of things as well?

My logic:

Spoiler

The only information Pete has is that there are two hidden numbers from 1 to 9 (inclusive), and he has their product on a piece of paper. We are working with three different sets here:

1. Legal combinations of numbers.
2. The products of these combinations.
3. The sums of these combinations.

The only possibly way he could know what the two numbers were off the bat is if the number on his paper was a product that appeared uniquely in the set of all products. Since he doesn't know this, we can intuitively eliminate all number combinations that produce a unique product.

Susan is in the same scenario, only she now knows that any combination that produced a unique product is eliminated. Since she also answers 'no,' we can eliminate all unique sums from this new set of combinations, further reducing the set of possible combinations.

Repeating this recursively, when you get to the first time either of them says 'yes,' the answer can be any combination of numbers left in our set of legal combinations which produces a unique sum/product, depending upon who is doing the answering. If there is only one unique sum/product, you can determine exactly which combination of numbers were chosen.

It seems as if determining whether someone will say 'yes' or 'no' to a following question is only definitive if there are ZERO or ALL unique answers left; if there are some unique answers and some duplicate answers, the person may or may not know.

[albionmoonlight]

New Riddle

Complete this series:

10, 11, 12, 13, 14, 15, 16, 17, 21, 23, 30, 33, …

[albionmoonlight]

dola:

Five minutes of staring at it has given me nothing