|
На острове Преекатерининском проживают ровно 2020 человек, каждый из которых является либо рыцарем, который всегда говорит правду, либо лжецом, который всегда лжёт. Известно, что каждый житель этого острова дружит ровно с двумя другими. Однажды каждый из островитян заявил, что дружит ровно с одним лжецом. Какое наибольшее количество рыцарей может жить на Преекатерининском? задан 30 Июл '20 0:01 
Казвертеночка |
|
Граф знакомств разбивается на циклы длиной >=3. Найдётся цикл, длина которого не делится на 3. Тогда в нём одни лжецы (начиная от рыцаря, в обе стороны всё определяется однозначно с точностью до симметрии. Сумма длин циклов, длина которых делится на 3, не более 2016. В каждом цикле длиной 3k будет ровно 2k рыцарей. Итого их не более 1344, а пример с таким количеством легко строится (в цикле длиной 4 одни лжецы; остальные стоят по циклу как ррлррл... . отвечен 30 Июл '20 11:57 
falcao @falcao, большое спасибо!
(1 Авг '20 0:34)
Казвертеночка
|