I HEART MATH!
Tuesday, March 06, 2007
This is such a timely math problem...
The presidential elections are to be held in Anchuria. Of 20,000,000 voters only 1 percent (i.e. the regular army) support the current president Wobushko. He wants to be re-elected in a democratic way, which means the following. All voters are split into n1 groups, all of equal size. Then each group can be split into n2 smaller sub-groups of equal size, where n2 is the same for all groups. Then each subgroup is split into n3 equal sub-sub-groups, and so on. Each (sub)i-group chooses by majority rule one representative to represent it at level i−1, and so on. (If there is a tie, the opposition wins.) Can Wobushko organize the groups and distribute his supporters so that he wins the elections?
Try to solve it first, before peeking into the solution and answer!Solution.
Yes, Wobushko can steal the election. Suppose in general that the number of voters is N and we write N as a product of non-trivial factors N = Nk = n1 × n2 × · · · × nk. Then, letting mi = ⌊ni/2⌋ + 1 we see that it is enough to have Mk = m1×m2×· · ·×mk supporters in order to win the election. This follows by induction on k. The base case k = 1 is trivial. To win for general k, we have to divide the electorate into Nk−1 groups of size nk. Wobushko then packs Mk−1 of these groups with mk of his supporters. After the vote there are Nk−1 voters altogether of which Mk−1 are supporters of Wobushko, completing the induction.In the numerical example we write 20, 000, 000 = 57 × 44. In which case Wobushko needs to have 37 × 34 = 177147 supporters which is less than 1 percent.
Labels: Math
