Tag: Puzzles

 

Twice is always nice, so I’m going to tack­le the Clas­sic Rid­dler for the week as well.

For those that aren’t famil­iar, The Rid­dler is a week­ly puz­zle series from Oliv­er Roed­er at FiveThir­tyEight that usu­al­ly involves some com­bi­na­tion of math, log­ic and probability.

This weeks Rid­dler Clas­sic is:

You are the only sane vot­er in a state with two can­di­dates run­ning for Sen­ate. There are N oth­er peo­ple in the state, and each of them votes com­plete­ly ran­dom­ly! Those vot­ers all act inde­pen­dent­ly and have a 50–50 chance of vot­ing for either can­di­date. What are the odds that your vote changes the out­come of the elec­tion toward your pre­ferred candidate?

More impor­tant­ly, how do these odds scale with the num­ber of peo­ple in the state? For exam­ple, if twice as many peo­ple lived in the state, how much would your chances of swing­ing the elec­tion change?

As with most oth­er Rid­dler prob­lems, I want to start with doing some of the basic cas­es 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 num­ber of voters.

— Oliv­er Roed­er (@ollie) Novem­ber 4, 2016

So let’s start with the basic case of N=1 (1 oth­er vot­er). The vot­er can either vote for your pre­ferred can­di­date (D) or your non-pre­ferred can­di­date ®. You’ll always be vot­ing for your pre­ferred can­di­date (D). Our goal is to find out what per­cent of the time that will make a dif­fer­ence. So let’s take a look at the sce­nar­ios that could happen:

Sce­nario	Votes D	Votes R	Chance of Scenario
A	1	0	0.5
B	0	1	0.5

Pret­ty sim­ple. In Sce­nario A, your can­di­date’s win­ning, so your vote for can­di­date D does­n’t mat­ter. If Sce­nario B hap­pens, you can force a tie, which accord­ing to Ollie goes to a coin flip. So the prob­a­bil­i­ty of you affect­ing the elec­tion (P₁) is:

P₁ = (Prob­a­bil­i­ty of Sce­nario B)*(Probability that Tiebreak­er Coin­flip Lands in Your Favor)

P₁ = 0.5 *0.5 = 0.25

Sim­ple enough, let’s look at P₂. The vot­ers here can either go DD (both vote for D), RR, DR, or RD. Since the last two states are the same for our pur­pos­es, we can sum up the sys­tem at N=2 as:

Sce­nario	Votes D	Votes R	Chance of Scenario
A	2	0	0.25
B	0	2	0.25
C	1	1	0.5

In Sce­nario A , your can­di­date won, so it does­n’t real­ly mat­ter to us. In Sce­nario B, your 1 vote for Can­di­date D won’t influ­ence the result so that’s not rel­e­vant either. So we look at Sce­nario C, how­ev­er there’s no coin­flip ele­ment here therefore:

P₂ = Prob­a­bil­i­ty of Sce­nario C = 0.5

Let’s jump ahead to N=5 so we can deal with a more inter­est­ing sce­nario. The states that can exist at N=5 are:

Sce­nario	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 impor­tant things to notice here. There’s real­ly only one sce­nario where we can affect the result in our favor (Sce­nario C, where we can force a tie). By now we see a pat­tern in the types of sce­nar­ios that our vote can influ­ence — we can either force a tie as shown in Sce­nario C for N=5 or break a tie as shown in Sce­nario C for N =3 ear­li­er. Those sit­u­a­tions can be defined as:

Sit­u­a­tions Where Our Vote Mat­ters = [N/2]

The near­est inte­ger func­tion (as denot­ed by [x]) rounds down a num­ber to near­est inte­ger (e.g. [2.5] = 2). Cool, now we know for a giv­en N which sce­nar­ios we can actu­al­ly influence.

Before N=5, cal­cu­lat­ing the prob­a­bil­i­ty was rather triv­ial. For larg­er N we can fall back on the Bino­mi­al Prob­a­bil­i­ty For­mu­la defined by:

P_{k suc­cess­es in n tri­als} = nCr(n,k)*p^k*(1‑p)^n‑k

Each of those terms are:

nCr(n,k) = Amount of unordered com­bi­na­tions for a giv­en k objects in set of n total objects (e.g. how many unique ways can you have 2 heads giv­en 5 coins). Defined by n!/((n‑k)!*k!).

k  = Suc­cess­es. For our prob­lem, that’ll be votes cast for Can­di­date D

p = Prob­a­bil­i­ty of success

Since we’re deal­ing with 50/50 odds, a lot of that for­mu­la can get sim­pli­fied. Also, we defined the sce­nar­ios that we can affect as ones where Canidate D votes = [N/2], there­fore k = [N/2]. That results in the sim­pli­fied formula:

P_{k suc­cess­es in n tri­als} = nCr(n,k)*p^k*(1‑p)^n‑k =  nCr(n,k)*0.5^k*(0.5)^n‑k = nCr(n,k)*0.5^k+n‑k = nCr(n,k)*0.5ⁿ  = nCr(n,[n])*0.5ⁿ 

P_{Sce­nario our vote counts @ giv­en N} = N!/((N-[N/2])!*[N/2]!)*0.5^N

Recall that at odd N’s our vote just forced a tie in this sce­nario, and we had to account for . So in actu­al­i­ty, the gen­er­al solu­tion is a bit dis­joint­ed. The solu­tion is:

For Even N

P_{Even N} = N!/((N-[N/2])!*[N/2]!)*0.5^N

For Odd N

P_{Odd N} = 0.5*N!/((N-[N/2])!*[N/2]!)*0.5^N

This rela­tion­ship can be described in the fol­low­ing graphs:

 

Took along hia­tus from the Rid­dler, but I’m back!

For those that aren’t famil­iar, The Rid­dler is a week­ly puz­zle series from Oliv­er Roed­er at FiveThir­tyEight that usu­al­ly involves some com­bi­na­tion of math, log­ic and probability.

This weeks FiveThir­tyEight Rid­dler, How Many Bananas Does it Take to Lead a Camel to Mar­ket?:

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 loy­al camel can car­ry at most 1,000 bananas at a time. How­ev­er, it has an insa­tiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile trav­eled. In the absence of bananas on his back, it will hap­pi­ly walk as far as need­ed to get more bananas, loy­al beast that it is. What should you do to get the largest num­ber of bananas to the bazaar? What is that number?

So just in order to get to the mar­ket, you need a min­i­mum of 1,000 bananas, and since that just gets you there with­out any bananas to sell, a more cre­ative solu­tion 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 any­where, since at mile 1,000 we’ll be left with 0 bananas in each. Let’s instead redis­trib­ute 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 for­ward with­out redis­tri­b­u­tion we’d end up with 2 bananas to sell at the mar­ket (1 from Pile A and 1 from Pile B). Let’s redis­trib­ute 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 pat­tern starts to emerge, every mile takes 3 bananas, specif­i­cal­ly 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 redis­trib­ute it. So we’re now 667 miles away from our des­ti­na­tion, with 2 piles of 1,000 bananas each. Let’s con­tin­ue this redis­tri­b­u­tion strat­e­gy with Piles A and Pile B (redis­trib­ut­ing 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 anoth­er pat­tern 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 sim­ply just car­ry Pile A, feed­ing a banana to the camel every mile for the last 177 miles. The amount of bananas left when we reach the mar­ket is sim­ply 1000 — 177 = 833.

To answer the orig­i­nal Rid­dler ques­tion, the largest amount of bananas that we can get to the bazaar under the cur­rent cir­cum­stances is 833.

 

 

Con­tin­ue read­ing “The Rid­dler – Can You Solve the Puz­zle of the Picky Eater”

Con­tin­ue read­ing “The Rid­dler — Can You Solve The Puz­zle Of The Pirate Booty?”

 

Con­tin­ue read­ing “The Rid­dler — Can You Slay The Puz­zle Of The Mon­sters’ Gems?”

 

Con­tin­ue read­ing “The Rid­dler — Can You Solve This Ele­va­tor But­ton Puzzle?”

Project

The Rid­dler is a week­ly puz­zle series from Oliv­er Roed­er at FiveThir­tyEight that usu­al­ly involves some com­bi­na­tion of math, log­ic and probability.

This weeks FiveThir­tyEight Rid­dler, The Per­plex­ing Puz­zle of the Proud Par­ty­go­ers was:

It’s Fri­day and that means it’s par­ty time! A group of N peo­ple are in atten­dance at your shindig, some of whom are friends with each oth­er. (Let’s assume friend­ship is sym­met­ric — if per­son A is friends with per­son B, then B is friends with A.) Sup­pose that every­one has at least one friend at the par­ty, and that a per­son is “proud” if her num­ber of friends is strict­ly larg­er than the aver­age num­ber of friends that her own friends have. (A com­pet­i­tive lot, your guests.)

Impor­tant­ly, more than one per­son can be proud. How large can the share of proud peo­ple at the par­ty be?

The ques­tion lends itself to Graph The­o­ry, so I start­ed with a ran­dom 20 node (which present par­ty­go­ers) network.

The above shows a sim­ple graph that could rep­re­sent a par­ty. The orange nodes rep­re­sent the par­ty­go­ers, and the  gray lines (edges) rep­re­sent the oth­er par­ty­go­ers each per­son is friends with.

Since the con­di­tion of the prob­lem is that every par­ty­go­er has at least one friend there, we’re deal­ing with a con­nect­ed graph — every node is con­nect­ed to at least one oth­er. The min­i­mum and max­i­mum num­ber of edges for a con­nect­ed graph with N edges is:

Min Edges = N‑1

Max Edges = (N*(N‑1))/2

The first thing I did was gen­er­ate a ran­dom graph for every pos­si­ble edge con­di­tion for a 25 node graph (from 24 edges to 300 edges), and cal­cu­lat­ed the pro­por­tion of proud par­ty­go­ers at each graph. This gen­er­at­ed the fol­low­ing (pre­sent­ed in FiveThir­tyEight style!):

I only plot­ted val­ues in which the pro­por­tion of proud par­ty­go­ers increased, and saw it peaked right before the max­i­mum amount of edges (300). The peak val­ue occurred at 299 edges. At the max­i­mum edge amount, the pro­por­tion of proud par­ty­go­ers fell to 0.

The next step was to see whether this trend held through for graphs with node amounts dif­fer­ent than 25. I ran a sim­i­lar script to the one above for vary­ing amounts of par­ty­go­ers, and record­ed the edges at which the Pro­por­tion of Proud Par­ty­go­ers theme was at a maximum.

What imme­di­ate­ly stands out is that the data mir­rors a qua­drat­ic, and looks very sim­i­lar to the max­i­mum edges for­mu­la ear­li­er. Some select­ed data from the above chart is below:

Par­ty­go­ers (N)	Friend­ships (edgeS) at Max Proud Par­ty­go­er Proportion
5	9.00
10	44.00
20	189.00
40	779.00
50	1224.00
100	4949.00

Tak­ing a clos­er look at that data, and recall­ing that pro­por­tion of proud par­ty­go­ers fell to 0 at the max­i­mum edge val­ue at N=25, you can con­clude the num­ber of edges at which proud par­ty­go­er pro­por­tion is max­i­mized is:

Edges @ Max Par­ty­go­er Pro­por­tion = Max Edges ‑1 = (N*(N*1))/2

One less than the max­i­mum num­ber of edges.

So now that we know the make­up of a graph (in terms of # of edges/nodes) that max­i­mizes pro­por­tion of proud par­ty­go­ers, I graphed what that pro­por­tion is for a giv­en num­ber of par­ty­go­ers (N).

The data looks sim­i­lar to a f(x) = (x‑1)/x func­tion where the func­tion will approach, but nev­er be greater than 1 — which is intu­itive­ly in line with the prob­lem; the pro­por­tion of proud par­ty­go­ers won’t even be greater than the amount of partygoers.

For N=5 the max­i­mum pro­por­tion of par­ty­go­ers is 0.6. For which the net­work graph looks like:

3/5 of the nodes are direct­ly con­nect­ed to every oth­er node in the graph, while 2/5 are only con­nect­ed to 3 of the oth­er nodes. Giv­en that our graph has 1 less edge than the max­i­mum num­ber of edges, it makes sense that 2/N nodes would no longer be ful­ly con­nect­ed. There­fore in a graph of size N with [Max Edges — 1] Edges, the amount of proud par­ty­go­ers would be N‑2.

Par­ty­go­ers	Max Pro­por­tion Proud Partygoers
5.00	0.60
10.00	0.80
20.00	0.90
40.00	0.95
50.00	0.96
100.00	0.98

Test­ing that the­o­ry against some of the data holds true. There­fore we con­clude that the pro­por­tion of proud neigh­bors for a giv­en par­ty of N peo­ple is:

Prop. of Proud Par­ty­go­ers = (N‑2)/N