Conclusively solving the extreme gerrymandering puzzle

Question

This is the source of the following puzzle: CMU puzzle 20

When I look at the official solution though, I feel that the proof is not comprehensive. First the question (slightly rephrased to improve comprehension):

The presidential elections are to be held in Anchuria. Of the 20,000,000 voters only 1 percent support the current president Wobushko, the other $99\%$ favoring the opposition.

Here's how the election system in Anchuria 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 win for the opposition.

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 Wobushko organize the groups and distribute his supporters so that he wins the elections?

Now, the official solution: http://www.cs.cmu.edu/puzzle/solution20.pdf , says the following :

So, in this case, we can have L = 11 levels and Wobushko will win.

Now, here is my question:

Let's say that only 100,000 of the 20 million voters supported Wobushko. 20,000,000 = $5^7*4^4$ . In which case, Wobushko needs to have $3^7$*$3^4$ = 177,147 but he only has 100000 supporters.

Is this proof comprehensive enough to say that Wobushko will lose ? Or do we need to look at all possible breakups of 20 million?

For instance, one other way to breakup 20 million is, 20 million = $125*625*256$ which requires $63*313*129$ = 2543751 supporters for Wobushko. So, in the case where the group sizes are 125, 625 and 256, Wobushko will also not win.

Basically, do we need to look at all the possible breakups of 20 million and make sure that Wobushko does not win in any of these breakups or is just looking at 20,000,000 = $5^7*4^4$ enough?

Answer 1

The answer, in short:

Yes, the proof comprehensively proves that Wobushko will lose if they do not have at least the required 177,147 voters.

Now let's take a look at why:

To maximize their advantage, Wobushko should aim to divide Anchuria into the largest number of electoral levels $L$ possible, represented by the number of factors of $N$ = 20,000,000 one chooses. If Anchuria were a perfect democracy (that is, we had $L = 1$), Wobushko would need at least 10,000,001 voters to win the election.

Now, we can show that

by increasing the number of electoral levels of Anchuria and re-distributing their supporters accordingly, the number of voters Wobushko needs to win generally decreases (which plays to their advantage). For example, by splitting Anchuria's $N$ = 20,000,000 voters into $A$ = 2,000 groups of $B$ = 10,000 voters, Wobushko would need to win 5,001 of the 10,000 voters in every group and 1,001 of the 2,000 groups, resulting in Wobushko only needing 5,006,001 voters to win the election. In fact, we can observe that the number of voters required to win a group of size $N$, $\mathrm{floor}(\frac{N}{2})+1$, is almost always greater than the number of voters required to win $A$ groups of size $B$, which is $$\small(\mathrm{floor}(\frac{A}{2})+1)\cdot(\mathrm{floor}(\frac{B}{2})+1) = \mathrm{floor}(\frac{A}{2})\cdot\mathrm{floor}(\frac{B}{2}) + \mathrm{floor}(\frac{A}{2}) + \mathrm{floor}(\frac{B}{2}) + 1$$The only situation in which this is not true is when one of $A$ or $B$ is very small. Specifically, if $A$ or $B$ is less than or equal to 2, Wobushko gains no advantage in dividing, because they must win every electoral level by strict majority -- which would mean winning both resulting groups if $A = 2$ or all voters in each group if $B = 2$.

Thus,

the "ultimate" way that Wobushko could game the system is if they performed the above "division" as many times as possible without selecting $A$ or $B$ less than or equal to 2 or creating any unequally sized groups. To accomplish this, Wobushko should calculate the factorization of $N$ with the largest number of factors without including 2 as a factor. This is accomplished by the above factorization $N = 5^{7} \cdot 4^{4}$, which is the prime factorization of $N$ if we consider 4 to be "prime" (since we cannot divide a group of size $N = 4$ into $A = 2$ groups of size $B = 2$). This yields 177,147 as a strict minimum for the number of voters Wobushko must have to win the election.