Kvant Math Problem 1413

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m05s
Source on kvant.digital

Problem

On the Island of Misfortune, each inhabitant either always tells the truth or always lies, and the number of truth-tellers is at least one-quarter of all inhabitants. In the presidential election, in which all inhabitants participated, there were only two candidates — Yelkin and Palkin. When asked by a UN observer, "Whom did you vote for?" the majority of the inhabitants answered, "for Palkin," and when asked, "Who won?" the majority answered, "Yelkin."

1. Who won the election?
2. Can this be determined for certain if only one-fifth of the island's inhabitants are truth-tellers?

S. Berlov

Exploration

Let $N$ be the number of inhabitants, $T$ the number of truth-tellers, and $L=N-T$ the number of liars.

Let $P$ be the number of votes actually cast for Palkin, and $Y=N-P$ the number of votes for Yelkin.

When an inhabitant is asked whom he voted for, a truth-teller names his actual candidate and a liar names the other candidate. Hence the number answering “Palkin” equals

$$P+Y-T=N-T-L_P+L_Y,$$

but it is more convenient to write it directly. Let $T_P,T_Y$ be the truth-tellers who voted for Palkin and Yelkin, and $L_P,L_Y$ the corresponding groups of liars. Then

$$P=T_P+L_P,\qquad Y=T_Y+L_Y.$$

The answer “Palkin” is given by $T_P+L_Y$. The statement that a majority answered “Palkin” means

$$T_P+L_Y>\frac N2.$$

Substituting $L_Y=Y-T_Y$ and $P+Y=N$ gives

$$P+(T_P-T_Y)>\frac N2.$$

Since $T_P-T_Y\le T$, we obtain

$$P+T>\frac N2.$$

Next consider the question “Who won?”. If Yelkin actually won, truth-tellers answer “Yelkin” and liars answer “Palkin”, so the number answering “Yelkin” is exactly $T$. If Palkin actually won, the number answering “Yelkin” is exactly $L$.

A majority answered “Yelkin”. Since $T\le N/2$ follows from $T\ge N/4$ only when $N$ is not specified, we must check both possibilities. If Yelkin had won, then a majority answering “Yelkin” would require $T>N/2$, impossible because then liars would be fewer than half, contradicting the fact that a majority answered “Palkin” to the first question. Thus Yelkin cannot have won.

Hence Palkin won. Then the majority answering “Yelkin” to the second question are precisely the liars, so

$$L>\frac N2,\qquad T<\frac N2.$$

From the first-question inequality,

$$P+(T_P-T_Y)>\frac N2.$$

Since $T_P-T_Y\le T$,

$$P>\frac N2-T.$$

With $T\ge N/4$,

$$P>\frac N4.$$

This alone does not force victory. The crucial step is stronger: since Palkin won, $P>N/2$ automatically. Thus the information from the second question already determines the winner.

For part 2, if only $T\ge N/5$, then the same reasoning about the second question still applies. A majority answering “Yelkin” cannot occur when Yelkin really won, because then only truth-tellers would answer “Yelkin”, and $T\le N/5<N/2$. Hence Palkin must still have won.

The potentially dangerous point is overlooking that the second question alone almost determines the winner once truth-tellers form less than half of the population.

Problem Understanding

There are truth-tellers and liars on an island. Every inhabitant voted for one of two candidates, Yelkin or Palkin. A majority of inhabitants say they voted for Palkin, and a majority say that Yelkin won the election. The number of truth-tellers is at least one-quarter of the population.

We must determine who actually won the election. Then we must decide whether the answer remains certain if the only assumption is that truth-tellers constitute at least one-fifth of the population.

This is a Type A problem, because we must determine which outcome is possible and exclude the alternative.

The core difficulty is interpreting the answers to the question “Who won?”. For that question every inhabitant gives the same name if he is truthful, and the opposite name if he is a liar, so the numbers of answers directly reveal which group forms the majority.

The answer is that Palkin won, both under the one-quarter assumption and under the one-fifth assumption. The reason is that a majority answering “Yelkin” can only consist of liars.

Proof Architecture

Lemma 1. If Yelkin actually won, then exactly the truth-tellers answer “Yelkin” to the question “Who won?”. This follows because truth-tellers state the true winner and liars state the false one.

Lemma 2. If Palkin actually won, then exactly the liars answer “Yelkin” to the question “Who won?”. The same truth-versus-lie dichotomy applies.

Lemma 3. Under either assumption $T\ge N/4$ or $T\ge N/5$, Yelkin cannot have won. If Yelkin had won, a majority answering “Yelkin” would force $T>N/2$, contradicting the existence of a majority answering “Palkin” to the voting question.

Lemma 4. Hence Palkin won. This is the only remaining possibility.

The hardest direction is excluding the possibility that Yelkin won. The step most likely to fail is deriving a contradiction from the two reported majorities.

Solution

Let $N$ be the total number of inhabitants, $T$ the number of truth-tellers, and $L=N-T$ the number of liars.

Assume first that Yelkin actually won the election.

When the observer asks “Who won?”, every truth-teller answers “Yelkin”, because that is the true winner, and every liar answers “Palkin”, because he must give the false answer. Hence the number of answers “Yelkin” is exactly $T$.

By the statement of the problem, a majority of inhabitants answered “Yelkin”. Therefore

$$T>\frac N2.$$

Now consider the question “Whom did you vote for?”. Since more than half of the population are truth-tellers, the answer receiving a majority must coincide with the candidate who actually received a majority of votes. Indeed, each truth-teller reports his vote correctly, and the truth-tellers alone already form a majority of the population.

Since Yelkin is assumed to have won, more truth-tellers voted for Yelkin than for Palkin. Consequently more than half of all inhabitants would answer “Yelkin” to the question about their vote. This contradicts the condition that a majority answered “Palkin”.

Thus Yelkin cannot have won.

The election had only two candidates, so Palkin must have won.

This answers part 1.

For part 2, suppose only that

$$T\ge \frac N5.$$

Since $T\le N$, this implies

$$T<\frac N2.$$

If Yelkin had actually won, then, exactly as above, the number of answers “Yelkin” to the question “Who won?” would be $T$. A majority answered “Yelkin”, so we would obtain

$$T>\frac N2,$$

which is impossible.

Hence Yelkin cannot have won. The only remaining possibility is that Palkin won.

Therefore the winner is still determined uniquely.

$$\boxed{\text{Palkin won in both situations.}}$$

Verification of Key Steps

The first delicate step is the interpretation of the answers to “Who won?”. If Yelkin won, truth-tellers say “Yelkin” and liars say “Palkin”; the number of answers “Yelkin” is exactly $T$. If Palkin won, the roles reverse and the number of answers “Yelkin” is exactly $L$. No inhabitant can answer differently, because there are only two candidates.

The second delicate step is deriving a contradiction when assuming Yelkin won. Under that assumption, the majority answering “Yelkin” to the second question yields $T>N/2$. Once truth-tellers alone form a majority, the majority answer to the voting question must reflect the actual election result. Since Yelkin is assumed to be the actual winner, the majority answer would have to be “Yelkin”, not “Palkin”.

A careless argument might try to use only the bound $T\ge N/4$ or $T\ge N/5$. Those lower bounds are not what forces the conclusion. The contradiction comes from the majority answer “Yelkin” to the second question, which under the assumption that Yelkin won implies the much stronger inequality $T>N/2$.

Alternative Approaches

One may focus entirely on the second question. If Yelkin won, then the set of people answering “Yelkin” is exactly the set of truth-tellers. Since a majority answered “Yelkin”, truth-tellers would form a majority of the population. A majority of truth-tellers makes it impossible for the majority answer to the voting question to disagree with the true election result. Since the majority answer there was “Palkin”, Yelkin cannot have won.

Another approach introduces the indicator variable $W$, where $W=Y$ if Yelkin won and $W=P$ if Palkin won. The answers to “Who won?” are unanimous within each of the two groups, truth-tellers and liars. The majority answer immediately identifies which group is larger. Assuming Yelkin won would make truth-tellers the larger group, and then every majority answer must coincide with reality, contradicting the reported majority “Palkin” to the first question. Both routes lead directly to the conclusion that Palkin won.