# Logic: Knights and Liars

Question from the Russian Olympiad. (Translated with Google Translate, with a translation fix.):

In a circle there are $$181$$ people, each of whom is either a knight or a liar (liars always lie, and knights always tell the truth). Each of those standing said: “Two places away from me there is at least one liar.” Find the smallest possible number of liars among these $$181$$ people.

My solution:

I first estimated that there were $$5$$ people then the minimum number of liars is $$2$$. because $$1$$ said $$3$$ liars $$2$$ said $$4$$ liars $$3$$ said $$5$$ liars and $$4$$ said $$1$$ liars and $$5$$ said $$2$$ liars. then if $$1$$ liar then $$4$$ and $$3$$ knights. Whence it follows that $$4$$ is also a liar and $$2$$ knight. Well, then the minimum number of liars in our case is $$90$$.

EDIT: I’ll try to explain it. Let's say if there are people in a circle with numbers $$1,2,3,4,5,6$$ ..., $$181$$ then this means that #$$1$$ says that either #$$3$$ or #$$180$$ is a liar, #$$2$$ says that either #$$4$$ or #$$181$$ is a liar and so forth.

• What does through one person mean? – Andrew Chin Jan 17 '20 at 14:15
• Do you mean "One of the two people standing next to me is a liar?" Or do you mean something else? Also, I can't make any sense of your solution. Try using shorter, more explicit sentences. – saulspatz Jan 17 '20 at 14:17
• So what do you mean? "Through one person there is a liar from me," isn't English. – saulspatz Jan 17 '20 at 14:38
• I’ll try to explain it. Let's say if there are people in a circle with numbers $1,2,3,4,5,6$ ..., $181$ then this means that 1 said that 3 liar n said $n+2$ liar and so on but you have to take into account that they stand in a circle then when the turn reaches $180$ people he will say that $1$ liar. something like that – IPHO2022 Jan 17 '20 at 14:48
• @art1488: Can you post a link to the original problem in Russian? – Vasya Jan 17 '20 at 14:58

If I understand correctly, everyone in the circle says 2 persons away (in any direction) there is a liar.

The minimal pattern that matches is $$KxLyK$$ - the $$L$$ lies because there isn't one, and the $$K$$'s both tell the truth.

We can interleave two of those patterns and repeat pattern $$KKLLKK$$ 30 times.

Then you have to close the circle with a $$L$$. On both sides, the second item is a $$K$$, which repeats the pattern.

The solution therefor: $$61$$

• This does not work. If I do $KKLLKKKKLLKK$ there are two pairs of $K$s in the middle where one calls the other a liar. – Ross Millikan Jan 17 '20 at 15:02
• In a circle you can look both ways (in my interpretation of the problem), and you have to look 2 places away. There needs to be only one liar. – Pieter21 Jan 17 '20 at 15:05
• You are reading the problem differently from me. I agree that OP has not been very clear. – Ross Millikan Jan 17 '20 at 15:10
• @Pieter21 yes you understood the task correctly – IPHO2022 Jan 17 '20 at 15:10
• @RossMillikan, I can read around 7 languages, so the 'through' mis-translation made some sense to me. – Pieter21 Jan 17 '20 at 15:14

Your solution for five does not work. When you assume $$1$$ is a liar you find $$4$$ and $$3$$ tell the truth. You did not pursue that to say $$3$$ says $$5$$ is a liar and must tell the truth, so $$5$$ is a liar. Then $$5$$ says $$2$$ is a liar, so $$2$$ tells the truth. $$2$$ says $$4$$ is a liar, which is a contradiction. The same thing will happen if you assume $$1$$ tells the truth. There is no consistent solution.

It is similar for $$181$$ or number equivalent to $$1 \bmod 4$$ in the circle. If we assume $$1$$ tells the truth, every fourth person tells the truth up to $$181$$. Then $$2$$ is a liar and so is every fourth person up to $$178$$. $$180$$ tells the truth, saying $$1$$ is a liar and we have the same contradiction.

• So the problem has no solutions? – IPHO2022 Jan 17 '20 at 14:59
• I mean that 1 says both about 180 and about 3 and says that one of the liars each person speaks of two other persons – IPHO2022 Jan 17 '20 at 15:04
• That doesn't seem to match your edit, but it doesn't matter. If $1$ calls $3$ a liar it is the same as if $3$ calls $1$ a liar. Either way they have to be of opposite kinds. I only use the fact that person $n$ calls person $n+2 \bmod 181$ a liar, which is enough to reach the contradiction. – Ross Millikan Jan 17 '20 at 15:07