50
$\begingroup$

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

$\endgroup$
  • 19
    $\begingroup$ Will this be the system used for the first Puzzling.SE moderator elections when we graduate? :-o $\endgroup$ – Rand al'Thor Jun 28 '15 at 23:12
  • 1
    $\begingroup$ @rand Hmm... y'know, after reading the answer, that's not a half bad idea... ;) $\endgroup$ – Aza Jun 29 '15 at 9:11
  • $\begingroup$ Your source link is invalid. $\endgroup$ – Neil Jun 29 '15 at 15:54
  • 4
    $\begingroup$ But, in a move of political genius, the other candidate abstains from voting, leaving only 19,999,999 voters remaining, thereby winning the election! $\endgroup$ – Milo Brandt Jun 30 '15 at 0:53
  • $\begingroup$ @Meelo Sorry to spoil the fun, but I guess that unfortunately in Puzzlevania, while he is allowed not to vote, he can't waive his right to vote, so he is still counted in the election system. $\endgroup$ – JiK Jul 1 '15 at 4:04
49
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Torsten Link Jun 29 '15 at 9:24
  • $\begingroup$ @TorstenLink 32(1 round) * 8(1 round) * 5^7(7 rounds) = 9 rounds $\endgroup$ – CodeNewbie Jun 29 '15 at 9:34
  • 1
    $\begingroup$ 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... $\endgroup$ – Torsten Link Jun 29 '15 at 9:40
  • $\begingroup$ 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? $\endgroup$ – CodeNewbie Jun 29 '15 at 10:54
  • 2
    $\begingroup$ @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. $\endgroup$ – Loren Pechtel Jun 30 '15 at 3:39
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CodeNewbie Jun 30 '15 at 4:25
  • $\begingroup$ 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. $\endgroup$ – Loren Pechtel Jun 30 '15 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.