Author:

 

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