DonaldRauscher.com

A Blog About D4T4 & M47H

538 Riddler: Hungry Bears

05 August ’16

My first intuition after reading this problem was "why would the bear ever reject the first fish?" If the first fish is big, then it makes sense to eat it; there are no guarantees the next fish will be as big. If the first fish is small, then eat it because the next fish is likely to be bigger, meaning we can eat it too. Some simple math confirms this. Let's say the first fish is of size. The probability that we eat the next fish is and the expected size of this fish is . The total meal size if we eat the first fish is is always greater than or equal , the expected meal size if we wait for the second fish. So if we're the bear, our optimal strategy is simple: eat whatever we see.

Given our rather simple strategy, let's come up with a generalized expression for the expected number of kilograms that the bear eats in a hour tour:

This is the harmonic series minus 1! In 2 hours, we expect the bear to eat kilograms. In 3 hours, we expect the bear to eat kilograms. The harmonic series is divergent, so the amount eaten by the bear does not converge on a value as N goes to infinity, even though the amount consumed by the bear in the Nth hour converges to 0.

538 Riddler: Traitorous Generals

30 July ’16

We begin by selecting one general at random. Our goal will be to determine if this specific general is loyal or traitorous, which we can figure out by polling the other generals. As we go around the circle, there are two stop conditions:

  1. The selected general receives loyal votes
  2. The selected general receives traitorous votes

If [1] happens, we know the selected general to be loyal. If [2] happens, we know the selected general to be traitorous. This works because we know that there is a majority of loyal generals and that all loyal generals are honest. If, during this inquisition, we identify a loyal general, then we're obviously done. If we identify a traitorous general, then we incarcerate him (or perhaps a more sinister punishment) and pick a new general to evaluate. We begin a new inquisition and reduce our stop conditions by 1. Through this process, we are guaranteed to find a loyal general. How many questions will it take though?

The maximum number of questions it takes to get to one of these two stop conditions is dependent on how the traitors behave. This requires a little explanation. Let's say we pick a traitorous general for our first inquisition. All the other traitors shouldn't try to vouch for him (i.e. claim he is loyal) because (1) it will not save him and (2) it will doom them individually. We're going to get to the right answer regardless, and anyone who said the traitor was not a traitor will be outed along with him. If our traitors choose the "band together" route, this whole thing will be over after this inquisition since we'll be able to pinpoint all of the traitors (the selected general and anyone who said he was loyal). If our traitors are self-preservational, we will confirm that the selected general is a traitor in exactly questions but will then need to begin another inquisition.

Why might we assume that traitors are self-preservational? Depends on whether the generals know what the emperor is trying to accomplish here. If the generals know the emperor is trying to identify a single loyal general for a super-important mission, then it makes sense for them to be self-preservational. If the generals think the emperor is going to methodically proceed through the ranks until he has killed every last traitor...well then I guess the traitors will be somewhat ambivalent, given that they're all going to get outed either way. Let's assume the generals don't know what the emperor is trying to do. And since there is a non-zero probability that the emperor is just trying to find a single loyal general, it makes sense for the traitorous generals to behave in a self-preservational way.

More importantly, does our assumption that "traitors will be self-preservational" impact our answer? Fortunately, I believe this assumption aligns with the upperbound. If a traitor says that another traitor is loyal, this can increase the number of questions required to identify the traitor in that inquisition, but also decreases the number of potential inquisitions needed because we'll be able to rule out both of those traitors by the end of that inquisition (two birds with one stone). In essense, self-preservational traitors make it most difficult for the emperor...by telling the truth.

We will need to do, at most, inquisitions; if we pick traitors in all of those, then we know any one of the remaining generals is loyal. Each subsequent inquisition distills our pool of generals to a smaller, more loyal group, making it easier and easier to assess the loyalty of our selected general. In other words, we need one fewer vote to confirm the selected general's loyalty.

Putting this all together, the maximum number of questions we would need is:

Let's quickly go through the N=5 example. Best case scenario, we pick a loyal general for our first inquisition. We only need 2 "loyal" votes to confirm he's loyal. We'll get this confirmation in 2-4 questions, depending on what happens. And we're done. Worst case scenario, we pick a traitor general for our first inquisition. We need 3 "traitor" votes to confirm he's a traitor. We'll get that in a 3-4 questions. If it takes 4 questions, then we've outed both of the traitors (the selected general and the guy who said he was loyal), and we're done. If it takes 3 questions, then we will need to begin another inquisition with the 4 remaining generals (3 loyal, 1 traitor). And in that round, we'll need a maximum of 2 questions to identify one of the loyal generals (just takes one "loyal" vote) or the lone remaining traitor (only takes two "traitor" votes). So the maximum number of questions we'll need is 5. This aligns with the above equation: .

538 Riddler: Defending Against an Alien Invasion

29 July ’16

This week's Ridder was the first one that I got wrong! I never really felt confident in my answer, thus no post. In the end, I did not model random points on the surface of the sphere correctly. A good link supplied by the 538 folks demonstrates how to do this correctly.

In retrospect, there are two random variables: and . The former represents the angular distance between the two alien ships. The latter represents the angular distance between the defender and the midpoint of the two alien ships. These two random variables have the following probability distributions:

These are independent, so we can simply combine them into a joint distribution and integrate to give us the probability that the planet is defended: