1
$\begingroup$

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$.

Question:is it correct answer?

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.

$\endgroup$
17
  • 2
    $\begingroup$ What does through one person mean? $\endgroup$ – Andrew Chin Jan 17 '20 at 14:15
  • 1
    $\begingroup$ 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. $\endgroup$ – saulspatz Jan 17 '20 at 14:17
  • 1
    $\begingroup$ So what do you mean? "Through one person there is a liar from me," isn't English. $\endgroup$ – saulspatz Jan 17 '20 at 14:38
  • 1
    $\begingroup$ 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 $\endgroup$ – IPHO2022 Jan 17 '20 at 14:48
  • 2
    $\begingroup$ @art1488: Can you post a link to the original problem in Russian? $\endgroup$ – Vasya Jan 17 '20 at 14:58
2
$\begingroup$

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$

$\endgroup$
13
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 17 '20 at 15:02
  • $\begingroup$ 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. $\endgroup$ – Pieter21 Jan 17 '20 at 15:05
  • $\begingroup$ You are reading the problem differently from me. I agree that OP has not been very clear. $\endgroup$ – Ross Millikan Jan 17 '20 at 15:10
  • $\begingroup$ @Pieter21 yes you understood the task correctly $\endgroup$ – IPHO2022 Jan 17 '20 at 15:10
  • 1
    $\begingroup$ @RossMillikan, I can read around 7 languages, so the 'through' mis-translation made some sense to me. $\endgroup$ – Pieter21 Jan 17 '20 at 15:14
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ So the problem has no solutions? $\endgroup$ – IPHO2022 Jan 17 '20 at 14:59
  • $\begingroup$ 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 $\endgroup$ – IPHO2022 Jan 17 '20 at 15:04
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 17 '20 at 15:07

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.