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?