На острове Преекатерининском проживают ровно 2020 человек, каждый из которых является либо рыцарем, который всегда говорит правду, либо лжецом, который всегда лжёт. Известно, что каждый житель этого острова дружит ровно с двумя другими. Однажды каждый из островитян заявил, что дружит ровно с одним лжецом. Какое наибольшее количество рыцарей может жить на Преекатерининском?

задан 30 Июл 0:01

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

Граф знакомств разбивается на циклы длиной >=3. Найдётся цикл, длина которого не делится на 3. Тогда в нём одни лжецы (начиная от рыцаря, в обе стороны всё определяется однозначно с точностью до симметрии. Сумма длин циклов, длина которых делится на 3, не более 2016. В каждом цикле длиной 3k будет ровно 2k рыцарей. Итого их не более 1344, а пример с таким количеством легко строится (в цикле длиной 4 одни лжецы; остальные стоят по циклу как ррлррл... .

ссылка

отвечен 30 Июл 11:57

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

(1 Авг 0:34) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,390
×52
×10
×10
×5

задан
30 Июл 0:01

показан
59 раз

обновлен
1 Авг 0:34

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

по почте:

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

по RSS:

Ответы

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

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