6
$\begingroup$

There are $N$ democrats and $N$ republicans sitting in a circle. Each of these people is either always honest or always deceitful. It is known that the number of honest democrats is the same as the number of honest republicans.

Each politician is asked, "What party is your right hand neighbor?" They all respond, "Republican."

Prove that $N$ is even.

Source: AMS Gazette, Puzzle Corner 7

$\endgroup$
6
$\begingroup$

If everyone calls their right-hand neighbor a rep, only $N$ of them can be one, so there are only $N$ truth tellers in total. There can be $N/2$ truth tellers and liars from each party, therefore $N$ is even.

$\endgroup$
5
$\begingroup$

Half of the people present are Democrats and half are Republicans. Everyone says their right hand neighbor is a Republican, so exactly half of the people are lying. Since there are $2N$ people present, $N$ of them must be liars. There are an equal number of Democratic liars and Republican liars, so $N$ must be even.

$\endgroup$
3
$\begingroup$

Denote by $k$ the number of honest democrats, which is known to also be equal to the number of honest republicans. The total number of honest people is therefore $2k$, and the total number of dishonest people is $2N-2k$.

The $2k$ honest people answered "republican" to the question about the party affiliation of the person sitting to their right, so since they are telling the truth, that implies that there are at least $2k$ republicans. But we know there are precisely $N$ republicans, so $2k\le N$, or $k\le N/2$.

The $2N-2k$ dishonest people answered "republican" to the question about the party affiliation of the person sitting to their right, so since they are lying, there at least $2N-2k$ democrats. But we know there are precisely $N$ democrats, so $2N-2k\le N$, or $k\ge N/2$.

These two observations together imply that $k=N/2$. But obviously $k$ is an integer, so $N$ must be even.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.