Using your Head is Permitted

January 2011 solution

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:

1. Read the tape, keeping in memory a map of "citizen ID" to "how many nominations the citizen got". Only citizens with a positive number of nominations will be kept in the map.
2. In order for the map not to exceed O(1) size, whenever the number of different candidates in the map reaches 100, all candidates lose one nomination from their count. This ensures that the number of candidates with a positive number of nominations drops to at most 99. We perform this discounting at every step except after counting the very last nomination.
3. Read the tape again, this time keeping a non-discounted count of the nominations. However, this time around count only those candidates whose ID is already in the map.
4. From the information of the map and knowledge of the total number of nominations (which can be counted at either pass), the number of ballots for each delegate in the map can easily be calculated. The rest of the citizens receive zero ballots.

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.

One note:
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