В ряд стояли рыцари и лжецы, причём среди них был хотя бы один рыцарь. Каждый из стоящих произнёс фразу: "Все рыцари стоят от меня через составное число человек". Сколько всего человек могло стоять в этом ряду?

задан 8 Фев 11:43

10|600 символов нужно символов осталось
1

Я вначале стал анализировать случаи, когда рыцарь один, когда их два, и так далее. Там ограничение было типа 28. Из общих соображений (типа китайской теоремы об остатках) следует, что для заданного числа рыцарей есть ограничение сверху. Для случая трёх рыцарей уже получалось что-то сложное.

В этот момент я неожиданно осознал, что есть совсем простое решение, никак не учитывающее специфику рассматриваемых чисел. А именно, пусть M -- произвольное множество натуральных чисел. Покажем, что число человек могло быть любым. Выстроим их, и кого-то объявим рыцарем (например, первого). Далее посмотрим, есть ли лжецы, которые не удовлетворяют условию задачи. То есть такие, которые от каждого из рыцарей стоят на допустимом расстоянии d (это значит, что промежуточное число d-1 человек принадлежит M). Если есть, то выбираем любого из них (скажем, самого левого из возможных), и переквалифицируем его в рыцаря. Процесс окончится за конечное число шагов.

Этим, фактически, даётся алгоритм. Например, пусть мы хотим выстроить 100 человек. Тогда номер 1 -- рыцарь. От него на допустимом расстоянии стоит лжец под номером 6 (между ними 4 человека -- составное число). Объявляем его рыцарем. Следующим рыцарем станет номер 11: между ним и номером 6 стоят 4 человека, между ним и номером 1 -- девять человек. И так далее. Закономерность там может быть весьма "причудливая" -- особенно для произвольного M. Но процесс этот легко пронаблюдать в явном виде, и он за конечное число шагов даёт то, что нужно.

Задача весьма впечатлила!

ссылка

отвечен 9 Фев 19:42

@falcao, большое спасибо!

(10 Фев 2:11) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×678
×144
×23
×3
×2

задан
8 Фев 11:43

показан
137 раз

обновлен
10 Фев 2:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru