Король сказочной страны пригласил на пир всех людоедов своей страны. Среди них есть людоеды, которые хотят съесть других людоедов. Известно, что максимальная цепочка, в которой первый людоед хочет съесть второго, второй — третьего и так далее, состоит из шести людоедов (в частности, нет циклов). Каково минимальное количество столов, за которые король может так рассадить людоедов, чтобы ни за одним из этих столов никто не захочет съесть никого из сидящих за тем же столом?

задан 25 Мар '16 21:00

1

Это задача из "Кванта". См. решение здесь. Оценка там даётся только в одну сторону, но в другую она очевидна, то есть пример, когда 5 столов не хватает, строится совсем просто (берём 6 людоедов с номерами, где i хочет съесть j при i<j).

(26 Мар '16 1:03) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,066
×395
×242
×141
×135

задан
25 Мар '16 21:00

показан
308 раз

обновлен
26 Мар '16 1:03

Связанные исследования

Связанные вопросы

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

по почте:

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

по RSS:

Ответы

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

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