Ernie and the Kzijekistanian Coup

Question

A couple of days ago I noticed an article in the International News section of our local newspaper headlined Kzijekistanian Empress Abdicates. Reading on, I discovered that she "… stepped down from power less than 24 hours after her coronation…". I was somewhat confused, as I had always understood that Kzijekistan was a socialist kratocratic bureaucracy - how and when had it turned into an monarchy? Surely the article was just another example of journalistic error or even worse, purposeful disinformation! I thought that maybe Ernie could provide a little insight into the situation as he was a regular visitor to that part of the world, so when I picked him up from the airport this morning (he was returning from an overseas trip) I asked if he could provide any insight on the matter. Imagine my surprise when he told me that not only was the article "more or less correct" but that he was also "somewhat involved" in the event. I asked him to explain, and he told me the following story...

A few months ago, the People's Republic of Kzijekistan made an official announcement:

After more than a century of revolutionary struggle the nation's laws - as written in full in the country's 37,000-page Kzijekistanian People's Constitution - have been perfected. No changes or amendments will ever be needed in the future, so the state bureaucracy will immediately disband itself. For purposes of international relations, a Sovereign will be chosen to represent the country. The Sovereign (for life) will have (nearly) absolute powers (limited only by the immutable rules of the Constitution) and will rule with the assistance of the National Security Police.

Many, many years ago, before its revolution, Kzijekistan had been an elective kingdom. The traditional way of choosing a new king (from a set list of candidates chosen by the church) would be by a nested series of voting rounds. The elders of each hamlet would meet at their local village and vote for their choice of candidate; then each village would send their mayor to the local county to vote for their choice; then finally, each county would send their laird to the state palace to vote for their choice and identify the new ruler. But a result of decades of social reform, the Republic no longer had churches, hamlets, elders, mayors, lairds, or a state palace, so decided on a modernized version of the old system.

The vote would be held online with the aid of Acme Voting System's latest artificially intelligent voting software, ChatAVS. A small number of 'neutral observers' would be invited to Kzijekistan to ensure the elections were run fairly. Ernie, being one of the few people in the outside world who actually has a multiple re-entry visa for Kzijekistan, was invited to be one of those observers.

The election was run as follows:

• The Ministry of Genealogy had pre-determined which citizens had suitably royal bloodlines and had passed their names on to ChatAVS.
• The Ministry of Historic Records had ore-determined the number of ‘counties’, the number of ‘villages’ in each county, the number of ‘elders’ in each village, and hence the total number of voters required to represent the population of Kzijekistan. They had passed this information on to ChatAVS and to the Ministry of Telephonic Records.
• ChatAVS would (by random selection) choose the voters from the Ministry of Identification's list of Citizen Identification Records. This list would be passed on to the Ministry of Telephonic Records.
• The Ministry of Telephonic Records would (by random selection) group the chosen citizen’s phone numbers into sub-lists for each ‘county’, and then (also by random selection) further split each sub-list into sub-sub-lists for each village (Every citizen of Kzijekistan over the age of 14 has a state-provided cellphone!!!). These lists were passed back to ChatAVS.
• ChatAVS would automatically poll the cellphones of each elder to determine their choice of royal candidate. Voting was mandatory!!!
• ChatAVS would determine the winner of each village vote, then the winner of each county vote, then the winer of the final state palace vote, and announce the winner. The voting at each stage was a first-past-the-post absolute majority vote.
• A state coronation would be held within an hour of the results being declared, during which the new Sovereign of the (almost) Absolute Monarchy of Kzijekistan would be crowned.

To ensure honesty and transparency in the electoral process, ChatAVS is designed to provide voting records to those overseeing the election. However, The Ministry of Disinformation was averse to "information, that could be used by potential enemies of the state, being handed over to foreigners", so formal records were only provided to the National Security Police. But as a compromise, so it could be claimed that the neutral observers were actually observing something, the ChatAVS software was edited to publicize a set of obfuscated numbers based on the voting statistics, a single statistical 'snippet' regarding the vote and, of course, the final winner of the election.

At the completion of the vote ChatAVS announced the following:

• The number of candidates was a prime number.
• The number of counties was a prime number.
• The number of voters in each individual village was a distinct prime number.
• The number of villages in each county was a prime number.
• The total number of villages was a prime number.
• All the above prime numbers were distinct and formed a contiguous set of primes.
• The number of voters was a prime number.
• The number of voters was the smallest number consistent with the above information.
• An unidentified non-winning candidate had the largest possible number of votes consistent with the above information.
• The winner of the election was Grand Duchess Margaritha von Tszolijk.

Ernie tells me that he was a little embarrassed at how long it took him to realize that something was a bit fishy about the results, as it wasn't until the post- coronation drinking party was well underway that he turned to his neighbor and told her that "Assuming there is nothing wrong with ChatAVS, I believe that a suspiciously non-random process must have been used to group the voters into the sub-lists and sub-sub-lists. Either that, or an extraordinarily unlikely voter distribution occurred by chance". Half an hour later, the party was abruptly halted and, with the excuse of "unforeseen approaching meteorological events", the neutral observers were whisked to the airport to catch planes that immediately left the country.

I can only assume that someone took Ernie's comment very seriously (the old saying about the walls having ears is very true in Kzijekistan…or maybe it is the cellphones) and presumably, after confirming that ChatAVS was performing properly, the National Security Police had a closer look at the voting data and declared the election null-and-void. But what I don't understand is how Ernie came to his conclusion, and just how unlikely it was that the above-described results could have occurred if voters had been randomly distributed into the sub-sub-lists. Can anybody provide me with a little insight?

Answer 1

This is the worst case of Gerrymandering I've ever seen.

The voting system can be considered as a tree, where the root node is the final state palace vote, its children nodes are the counties, the next level is the villages of each county, and the final level the voters in each village. Each node has a prime number of children (except the voter leaf nodes), and each level has a prime number of nodes (except the root node level).

None of the primes in this tree can be 2: If there were 2 counties, then the number of villages would be even. If a village had 2 voters, then the total number of voters would be even (there is an odd number of villages, and all but one has an odd number of voters). Similarly no county can have two villages.

The number of candidates is another prime number, and this can still be 2.

For the total number of voters to be minimal, the smallest primes need to be nearer the root of the tree, so we have 3 counties, with for example 5, 7, and 11 villages (5+7+11=23 is prime). The number of voters in the villages would then be the 23 primes starting from 13, but skipping over 23 itself. The total number of voters is: $$ 13+17+19+29+31+....+109=1429$$ Fortunately that total number is prime, so this is indeed the voting arrangement that was used.

Note that the winner needs only win two counties, so need only win 3 out of the 5 villages in the first county, and 4 out of the 7 villages in the second county, and can lose the rest. As the number of votes for an unnamed loser candidate is as large as possible, there must indeed have been only 2 candidates, with the winner taking as few votes as possible so that the loser took all the rest. Obviously that is extremely suspicious and unlikely to be random.

The winner won in only 7 of the 23 villages. The smallest amount is when those villages are the next smallest primes 13, 17, 19, 29, 31, 37, 41, in any order, which can be won using only 7+9+10+15+16+19+21=97 votes. The losing candidate had 90 votes in those villages, plus all the votes in the other 16 larger villages, for a total of 1429-97=1332. So the winner had less than 7% of the vote.

I won't calculate the exact probability, but even just the probability that the 97 votes for the winner come from the 187 out of 1429 voters in the smallest villages is minuscule, let alone having them distributed over those small villages just right.
$$\frac{\binom{187}{97}}{\binom{1429}{97}} = \frac{187!\cdot1332!}{90!\cdot1429!} \approx 2.5\cdot 10^{-98}$$