По кругу стояло 100 человек, каждый из которых или рыцарь, всегда говорящий правду, или лжец, который всегда врет. Каждого спросили про стоящего справа от него человека, рыцарь он…
По кругу стояло 100 человек, каждый из которых или рыцарь, всегда говорящий правду, или лжец, который всегда врет. Каждого спросили про стоящего справа от него человека, рыцарь он или лжец. Было получено 80 ответов “рыцарь”. Затем каждого спросили про человека, который стоит слева через одного от него рыцарь он или лжец. Какое наименьшее количество ответов “рыцарь” могло быть получено?
Чтобы решить эту задачу, давайте проанализируем ситуацию более подробно.
В кругу стоят 100 человек, каждый из которых может быть либо рыцарем (всегда говорит правду), либо лжецом (всегда лжет). Каждого человека спросили о том, является ли человек, стоящий справа от него, рыцарем или лжецом. Из 100 ответов 80 раз был получен ответ "рыцарь".
Поскольку мы знаем, что рыцари говорят правду, если кто-то из них ответит "рыцарь", то это значит, что человек справа действительно рыцарь. Лжецы же всегда врут: если лжец говорит, что человек справа рыцарь, это значит, что он на самом деле лжец.
Давайте обозначим количество рыцарей за R, а количество лжецов за L. Так как всего 100 человек, можно записать:
R + L = 100.
Мы знаем, что 80 ответов "рыцарь" может быть получено как от рыцарей, так и от лжецов. Каждый рыцарь может дать один правдивый ответ о том, что справа стоит рыцарь, в то время как лжец даст ложный ответ, утверждая, что справа стоит рыцарь, когда на самом деле это не так.
Таким образом:
- Если R рыцарей дали все 80 правильных ответов "рыцарь", то тогда L, оставшиеся лжецы, могут дать не более 20 ложных ответов о 20 лжецах справа.
Теперь давайте посмотрим на вторую часть задачи: у каждого человека спросили о том, кто стоит слева через одного. Это значит, что для каждого человека он будет спрашивать о человеке, стоящем на два места левее. Таким образом, у нас возникает другая комбинация ответов.
Для минимизации количества ответов "рыцарь" в этом случае рыцари могут давать ложные ответы о лжецах, а лжецы могут как утверждать, что рыцари, так и лжецы - в зависимости от их местоположения. Но чтобы минимизировать количество ответов "рыцарь", достаточно рассмотреть такие конфигурации.
На самом деле, в худшем случае (где самые неблагоприятные условия) можно предположить, что при каждом третьем ответе будет рыцарь, что дает нам ответ "рыцарь" всего лишь в одном случае на три возможных. Таким образом, можно получить, что минимальное число ответов "рыцарь" может составлять:
Минимум = ceil(100 / 3) = 34.
Это наиболее благоприятный результат для выстраивания ответов, где количество "рыцарь" будет минимизировано.
Таким образом, наименьшее количество ответов "рыцарь", которое могло быть получено, равно 34.
