51

It is election season in Puzzlevania. There are two candidates: the incumbent and a challenger. Of the $20$ million citizens, only $1$ percent support the current president; the other $99\%$ favoring the challenger.

Here's how the election system in Puzzlevania works: There is a list of numbers, $n_1,\dots,n_L$. The entire population is divided into $n_1$ equally sized groups. Each of these groups is divided into $n_2$ equally sized subgroups, each subgroup is divided into $n_3$ equal sub-subgroups, and so on down the line. On election day, each sub-sub-$\dots$-subgroup elects a representative to vote for it at the next level up. Tie votes count as wins for the challenger.

You can think of this system as a many-layered version of the American electoral college, where all states have the same population.

The current president has the power to choose the numbers $L,n_1,\dots, n_L$, and to choose which voters go in which groups. Can he do this in such a way that he gets elected?

Source: http://www.cs.cmu.edu/puzzle/puzzle20.html

Brian J
  • 107
  • 1
  • 7
Mike Earnest
  • 32,336
  • 6
  • 92
  • 237

2 Answers2

49

The current president should choose the numbers

9($L$), 32($n_1$), 8($n_2$), 5($n_3$), 5($n_4$), 5($n_5$), 5($n_6$), 5($n_7$), 5($n_8$), 5($n_9$).

In the lowest sub-sub-...-subgroup, the president should place voters in such a way that his supporters outnumber his opposers in the ratio of 3:5, till he runs out of supporters, and he can let the remaining sub-sub-...-subgroups vote for his opponent unanimously. So before the first round of voting, he has $200,000/20,000,000$ (1%) votes. After the first round, it becomes $66,666/4,000,000$ (1.66%). The current president needs to keep following this strategy till his percentage of votes exceeds 50%.

In the subsequent round, the same strategy needs to be followed so he can improve his vote share after each round of voting.

Following this strategy from $n_1$ till $n_9$, gives this vote share:

Supporting vote    Total Vote      Vote Share(%)     Voter ratio per round

200,000            20,000,000      1
                                                     3:5
66,666             4,000,000       1.67              
                                                     3:5
22,222             800,000         2.78              
                                                     3:5         
7,407              160,000         4.63              
                                                     3:5
2,469              32,000          7.72              
                                                     3:5
823                6,400           12.86             
                                                     3:5
274                1280            21.41             
                                                     3:5
91                 256             35.55             
                                                     5:8
18                 32              56.25

After the final group of 32 representatives votes, the president gets re-elected and another period of corruption and malpractice ensues in Puzzlevania.

CodeNewbie
  • 11,753
  • 2
  • 45
  • 87
  • Is it just me, or is there one level to much? Multiplying 32 * 8 * 5^7 = 20,000,000 - For me it's only 8 rounds, or am I wrong? – Tode Jun 29 '15 at 09:24
  • @TorstenLink 32(1 round) * 8(1 round) * 5^7(7 rounds) = 9 rounds – CodeNewbie Jun 29 '15 at 09:34
  • 1
    But you START with 200,000 supporters out of 20,000,000 citizens. There is no election taking place with 1 person in each sub- sub- sub... The first election is for the 5- member groups, so for me there are only 8 rounds of election... – Tode Jun 29 '15 at 09:40
  • The last round has 32 voters, 2nd last round has 256 voters, 3rd last round has 1280 voters, 4th last has 6400, 5th last has 32000, 6th last has 160000, 7th last has 800000, 8th last has 4000000, 9th last has 20000000 voters. Does that make it clear now, @TorstenLink? – CodeNewbie Jun 29 '15 at 10:54
  • Ah, that's where my error was. Thanx for making it clear!!! – Tode Jun 29 '15 at 11:24
  • The president seems like a pretty smart person. Perhaps he is the theoretical honest politician, and deserving of his presidency. – Joel Rondeau Jun 29 '15 at 19:45
  • Can this strategy be used indefinitely for arbitrary number of total voters, as long as the percentage remains the same? – jpmc26 Jun 29 '15 at 19:56
  • 2
    @jpmc26 No. A simple counter-example: 100 citizens, 1 supporter. Look at all the 5 steps--he only needs to win each one by 60%. The larger the total population the more 60%s get multiplied in and thus the smaller the total number of supporters needed to win. – Loren Pechtel Jun 30 '15 at 03:39
  • @codenewbie and other ... how does one realise that there will be 9 levels ? it is clear to me that there has to be at least 7 levels but how does one infer that there will be 9 levels? Also, how to figure out how many people will be there in each level ? – Hemant Agarwal Nov 24 '20 at 12:02
0

While CodeNewbie has answered it correctly he can do even better--by making each group 5 he can do it with 20,000 supporters. By itself this conveys no advantage but since he has plenty of extra supporters he doesn't need to settle for 3 of 5 in the final round--he can make this 5 of 5 and win by a unanimous vote! Making each round the same size also makes it look fairer.

Loren Pechtel
  • 201
  • 1
  • 8
  • I don't understand the math you're proposing. Could you clarify? It could fetch you a few upvotes, seeing as this question has become quite popular. – CodeNewbie Jun 30 '15 at 04:25
  • I'm using your approach, just with different subdivisions. The difference is mine leaves so many extra voters that instead of ending up with just over 50% in the final round you can have 100% of the final round. It takes a hair less than 7,000 votes to get a supporter into the final round, since you have 200k that means you could put more than 20 supporters in the final round--but since there are only 5 you certainly can make it a unanimous victory. – Loren Pechtel Jun 30 '15 at 15:56