NBA Rotation Finder
Team Pace Analysis
NBA Scoring Options
The Riddler – Will You (Yes, You) Decide The Election?
Twice is always nice, so I’m going to tackle the Classic Riddler for the week as well.
For those that aren’t familiar, The Riddler is a weekly puzzle series from Oliver Roeder at FiveThirtyEight that usually involves some combination of math, logic and probability.
This weeks Riddler Classic is:
You are the only sane voter in a state with two candidates running for Senate. There are N other people in the state, and each of them votes completely randomly! Those voters all act independently and have a 50-50 chance of voting for either candidate. What are the odds that your vote changes the outcome of the election toward your preferred candidate?
More importantly, how do these odds scale with the number of people in the state? For example, if twice as many people lived in the state, how much would your chances of swinging the election change?
As with most other Riddler problems, I want to start with doing some of the basic cases when N is low. As per our friend at 538, Ollie, we’ll deal with ties as such:
@ianrhile assume a coin flip if you’d like. or just assume an odd number of voters.
— Oliver Roeder (@ollie) November 4, 2016
So let’s start with the basic case of N=1 (1 other voter). The voter can either vote for your preferred candidate (D) or your non-preferred candidate (R). You’ll always be voting for your preferred candidate (D). Our goal is to find out what percent of the time that will make a difference. So let’s take a look at the scenarios that could happen:
Scenario | Votes D | Votes R | Chance of Scenario |
A | 1 | 0 | 0.5 |
B | 0 | 1 | 0.5 |
Pretty simple. In Scenario A, your candidate’s winning, so your vote for candidate D doesn’t matter. If Scenario B happens, you can force a tie, which according to Ollie goes to a coin flip. So the probability of you affecting the election (P1) is:
P1 = (Probability of Scenario B)*(Probability that Tiebreaker Coinflip Lands in Your Favor)
P1 = 0.5 *0.5 = 0.25
Simple enough, let’s look at P2. The voters here can either go DD (both vote for D), RR, DR, or RD. Since the last two states are the same for our purposes, we can sum up the system at N=2 as:
Scenario | Votes D | Votes R | Chance of Scenario |
A | 2 | 0 | 0.25 |
B | 0 | 2 | 0.25 |
C | 1 | 1 | 0.5 |
In Scenario A , your candidate won, so it doesn’t really matter to us. In Scenario B, your 1 vote for Candidate D won’t influence the result so that’s not relevant either. So we look at Scenario C, however there’s no coinflip element here therefore:
P2 = Probability of Scenario C = 0.5
Let’s jump ahead to N=5 so we can deal with a more interesting scenario. The states that can exist at N=5 are:
Scenario | Votes D | Votes R | Chance of Scenario |
A | 0 | 5 | 0.03125 |
B | 1 | 4 | 0.15625 |
C | 2 | 3 | 0.3125 |
D | 3 | 2 | 0.3125 |
E | 4 | 1 | 0.15625 |
F | 5 | 0 | 0.03125 |
There’s two important things to notice here. There’s really only one scenario where we can affect the result in our favor (Scenario C, where we can force a tie). By now we see a pattern in the types of scenarios that our vote can influence – we can either force a tie as shown in Scenario C for N=5 or break a tie as shown in Scenario C for N =3 earlier. Those situations can be defined as:
Situations Where Our Vote Matters = [N/2]
The nearest integer function (as denoted by [x]) rounds down a number to nearest integer (e.g. [2.5] = 2). Cool, now we know for a given N which scenarios we can actually influence.
Before N=5, calculating the probability was rather trivial. For larger N we can fall back on the Binomial Probability Formula defined by:
Pk successes in n trials = nCr(n,k)*pk*(1-p)n-k
Each of those terms are:
nCr(n,k) = Amount of unordered combinations for a given k objects in set of n total objects (e.g. how many unique ways can you have 2 heads given 5 coins). Defined by n!/((n-k)!*k!).
k = Successes. For our problem, that’ll be votes cast for Candidate D
p = Probability of success
Since we’re dealing with 50/50 odds, a lot of that formula can get simplified. Also, we defined the scenarios that we can affect as ones where Canidate D votes = [N/2], therefore k = [N/2]. That results in the simplified formula:
Pk successes in n trials = nCr(n,k)*pk*(1-p)n-k = nCr(n,k)*0.5k*(0.5)n-k = nCr(n,k)*0.5k+n-k = nCr(n,k)*0.5n = nCr(n,[n])*0.5n
PScenario our vote counts @ given N = N!/((N-[N/2])!*[N/2]!)*0.5N
Recall that at odd N’s our vote just forced a tie in this scenario, and we had to account for . So in actuality, the general solution is a bit disjointed. The solution is:
For Even N
PEven N = N!/((N-[N/2])!*[N/2]!)*0.5N
For Odd N
POdd N = 0.5*N!/((N-[N/2])!*[N/2]!)*0.5N
This relationship can be described in the following graphs:
The Riddler – Alligators, Sharks, Bridges and Friends
Without further ado, The Riddler [Express].
For those that aren’t familiar, The Riddler is a weekly puzzle series from Oliver Roeder at FiveThirtyEight that usually involves some combination of math, logic and probability. The Riddler Express is a simpler version of the classic Riddler.
Four people have to cross an old, rickety bridge over deep, cold water infested with sharks, alligators, crocodiles and shrieking eels. The bridge is so old that it can hold no more than two people at any given time. It’s the middle of the night, so on every trip across the bridge, the person crossing needs to use the group’s only flashlight to cross safely. The four people who need to cross all walk at different speeds. One of them takes one minute to cross, one takes two minutes, one takes five minutes and one takes 10 minutes. If two people cross together, they need to stay together to share the flashlight, so they cross at the speed of the slower person. For example, the one-minute person can cross with the 10-minute person, and that trip would take 10 minutes.
How quickly can all four people get across the bridge?
So your first thought, as mine was, might have been to include the 1 Minute man (hereby referred to as 1M) in every transaction. That gives us a solution in 19 minutes (as illustrated by the gif below!).
1
If my excellent artwork didn’t make sense, here’s a table explaining what happened.
Side A | Side B | Time Elapsed |
1M, 2M, 5M, 10M | X | 0 Minutes |
5M, 10M | 1M, 2M | 2 Minutes |
1M, 5M, 10M | 2M | 3 Minutes |
10M | 1M, 2M, 5M | 8 Minutes |
1M, 10M | 2M, 5M | 9 Minutes |
X | 1M, 2M, 5M, 10M | 19 Minutes |
So that gets us at a modest 19 minutes, but actually we can do better. Instead of making 1M run all over the place, we’re going to give him a break on Side B. The issue with the above solution is that we’re wasting a total of 15 minute getting 10M and 5M across. Ideally, you’d like 10M and 5M to go across together to mitigate the lost time, but still make it so that one of them doesn’t have to walk back.
The below gif illustrates the optimal solution of 17 minutes.
Again, if that didn’t make sense here’s a table:
Side A | Side B | Time Elapsed |
1M, 2M, 5M, 10M | X | 0 Minutes |
5M, 10M | 1M, 2M | 2 Minutes |
1M, 5M, 10M | 2M | 3 Minutes |
1M | 2M, 5M, 10M | 13 Minutes |
1M, 2M | 5M, 10M | 15 Minutes |
X | 1M, 2M, 5M, 10M | 17 Minutes |
You can see here that we were able to save time by making 5M & 10M go over together without making one of them walk back, giving the optimal solution of 17 minutes.
The Riddler – How Many Bananas Does It Take To Lead A Camel To Market?
Took along hiatus from the Riddler, but I’m back!
For those that aren’t familiar, The Riddler is a weekly puzzle series from Oliver Roeder at FiveThirtyEight that usually involves some combination of math, logic and probability.
This weeks FiveThirtyEight Riddler, How Many Bananas Does it Take to Lead a Camel to Market?:
sYou have a camel and 3,000 bananas. (Because of course you do.) You would like to sell your bananas at the bazaar 1,000 miles away. Your loyal camel can carry at most 1,000 bananas at a time. However, it has an insatiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile traveled. In the absence of bananas on his back, it will happily walk as far as needed to get more bananas, loyal beast that it is. What should you do to get the largest number of bananas to the bazaar? What is that number?
So just in order to get to the market, you need a minimum of 1,000 bananas, and since that just gets you there without any bananas to sell, a more creative solution is required. Let’s say we split the 3,000 bananas into 3 piles – Pile A, Pile B, & Pile C. From there we move Pile A one mile, go back and do the same for Piles B & C.
Mile | Pile A | Pile B | Pile C |
---|---|---|---|
0 | 1000 | 1000 | 1000 |
1 | 999 | 999 | 999 |
This won’t get us anywhere, since at mile 1,000 we’ll be left with 0 bananas in each. Let’s instead redistribute the Pile C bananas to Pile A and Pile B.
Mile | Pile A | Pile B | Pile C |
---|---|---|---|
0 | 1000 | 1000 | 1000 |
1 | 999 | 999 | 999 |
1 | 1000 | 1000 | 997 |
Now if we were to just move each pile forward without redistribution we’d end up with 2 bananas to sell at the market (1 from Pile A and 1 from Pile B). Let’s redistribute the bananas every mile, now it looks like:
Mile | Pile A | Pile B | Pile C |
---|---|---|---|
0 | 1000 | 1000 | 1000 |
1 | 999 | 999 | 999 |
1 | 1000 | 1000 | 997 |
2 | 999 | 999 | 996 |
2 | 1000 | 1000 | 995 |
3 | 999 | 999 | 994 |
3 | 1000 | 1000 | 992 |
A pattern starts to emerge, every mile takes 3 bananas, specifically from Pile C. For now, let’s say:
Bananas in Pile C = 1000 – 3*Miles Traveled
Now let’s look at Mile 333, about when Pile C would be exhausted.
Mile | Pile A | Pile B | Pile C |
---|---|---|---|
333 | 1000 | 1000 | 1 |
334 | 999 | 999 | 0 |
Since we only have 1 banana left in Pile C, we can’t redistribute it. So we’re now 667 miles away from our destination, with 2 piles of 1,000 bananas each. Let’s continue this redistribution strategy with Piles A and Pile B (redistributing Pile B)
Mile | Pile A | Pile B | Pile C |
---|---|---|---|
334 | 999 | 999 | 0 |
334 | 1000 | 998 | 0 |
335 | 999 | 997 | 0 |
335 | 1000 | 995 | 0 |
Now another pattern emerges for Pile B. The amount of bananas in Pile B can be described as:
Bananas in Pile B = 1000 – 2*(Miles Traveled-333)
Using this we see that Pile B runs out bananas around mile 833.
Mile | Pile A | Pile B | Pile C |
---|---|---|---|
832 | 1000 | 2 | 0 |
833 | 999 | 1 | 0 |
833 | 1000 | 0 | 0 |
At this point, we can simply just carry Pile A, feeding a banana to the camel every mile for the last 177 miles. The amount of bananas left when we reach the market is simply 1000 – 177 = 833.
To answer the original Riddler question, the largest amount of bananas that we can get to the bazaar under the current circumstances is 833.