To show that ballot-counting cannot be done in one pass, let N be some large multiple of 100 and suppose that the first (N/2)+50 numbers on the tape are distinct. The rest of the tape is filled with (N/100)-1 copies of 50 distinct numbers. The proper outcome of the ballot counting is that each of the 50 candidates to appear in the latter half of the tape gets 1 ballot, and the others get zero zero ballots. After reading the first (N/2)+50 numbers, the program must therefore be in a position to determine which candidates have already received a nomination and which not. This requires more than the O(log(N)) bits of information actually at the program's disposal.
In two passes, however, a viable algorithm is as follows:
Let us assume on the contrary that some candidate received x≥N/100 of the nominations, but does not appear in the final map. This would mean that each of the x nominations the candidate received has been discounted. This can only happen in x separate discounting operations, meaning that the total number of nominations discounted must have been at least 100x. However, 100x≥N, and we know that the number of nominations discounted was actually less than N: there was a total of N nominations, and at least the last of these was not discounted, because after it is read from the tape there are no further discounting operations. So, we have a contradiction.
Prepostria's new voting scheme has a hidden flaw: the current legislation makes no provision for the eventuality that the total number of ballots received by all delegates is zero, in which case delegate-based voting cannot work as planned. Such an eventuality can happen, for example, if every candidate receives exactly one nomination and N>100.
Back to riddle
Back to main page