сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word
Тип 0 № 2116
i

На ост­ро­ве живут ры­ца­ри, ко­то­рые все­гда го­во­рят прав­ду, и лжецы, ко­то­рые все­гда лгут. На глав­ный празд­ник за боль­шим круг­лым сто­лом раз­ме­сти­лись 100 ост­ро­ви­тян. По­ло­ви­на при­сут­ству­ю­щих про­из­нес­ла фразу: «оба мои со­се­да лжецы», остав­ши­е­ся ска­за­ли: «среди моих со­се­дей ровно один лжец». Какое наи­боль­шее ко­ли­че­ство ры­ца­рей может си­деть за этим сто­лом?

Спрятать решение

Ре­ше­ние.

За­ме­тим, что три ры­ца­ря не могут си­деть под­ряд, по­сколь­ку тогда сред­ний ры­царь не мог про­из­не­сти ни одну из тре­бу­е­мых фраз. Обо­зна­чим через k ко­ли­че­ство пар со­сед­них ры­ца­рей. Тогда каж­дый из ры­ца­рей про­из­нес фразу «среди моих со­се­дей ровно один лжец», по­это­му 2 k мень­ше или равно 50. Кроме того, левее этой пары за­ве­до­мо сидит лжец, и все эти лжецы раз­ные. На­зо­вем таких двух ры­ца­рей и лжеца трой­кой. В трой­ках за­дей­ство­ва­но 3 k ост­ро­ви­тян. Рас­смот­рим остав­ших­ся 100 минус 3 k ост­ро­ви­тян. Ни­ка­кие два ры­ца­ря среди них не сидят рядом друг с дру­гом, а также рядом с ры­ца­ря­ми из трой­ки (иначе об­ра­зу­ют­ся три ры­ца­ря под­ряд, что не­воз­мож­но). Тогда левее каж­до­го ры­ца­ря дол­жен си­деть лжец, все эти лжецы раз­ные и от­лич­ны от лже­цов, вхо­дя­щих в трой­ки. Таким об­ра­зом, ры­ца­рей не боль­ше, чем

2 k плюс дробь: чис­ли­тель: 1, зна­ме­на­тель: 2 конец дроби левая круг­лая скоб­ка 100 минус 3 k пра­вая круг­лая скоб­ка =50 плюс дробь: чис­ли­тель: k, зна­ме­на­тель: 2 конец дроби мень­ше или равно 50 плюс дробь: чис­ли­тель: 25, зна­ме­на­тель: 2 конец дроби = целая часть: 67, дроб­ная часть: чис­ли­тель: 1, зна­ме­на­тель: 2 .

Стало быть, ры­ца­рей не боль­ше 67.

При­ве­дем при­мер, по­ка­зы­ва­ю­щий, что 67 ры­ца­рей могут быть:

 \text ЛРР ЛРР ЛРР ... ЛРР ЛР ЛР ЛР ... ЛР Л,

блок «ЛРР» по­вто­ря­ет­ся 25 раз, блок «Л»  — 12 раз.

 

Ответ: 67.