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


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

Пу­те­ше­ствен­ник при­был на ост­ров, где живут 50 або­ри­ге­нов, каж­дый из ко­то­рых либо ры­царь, либо лжец. Все або­ри­ге­ны вста­ли в круг, и каж­дый на­звал сна­ча­ла воз­раст сво­е­го со­се­да слева, а потом воз­раст со­се­да спра­ва. Из­вест­но, что каж­дый ры­царь на­звал оба числа верно, а каж­дый лжец какой-то из воз­рас­тов (по сво­е­му вы­бо­ру) уве­ли­чил на 1, а дру­гой  — умень­шил на 1. Все­гда ли пу­те­ше­ствен­ник по вы­ска­зы­ва­ни­ям або­ри­ге­нов смо­жет опре­де­лить, кто из них ры­царь, а кто лжец?

 

(Алек­сандр Гри­бал­ко)

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

Ре­ше­ние.

I спо­соб. Вы­бе­рем лю­бо­го або­ри­ге­на  — будем на­зы­вать его Петей,  — и по­ка­жем, как найти его воз­раст. Мыс­лен­но на­де­нем на каж­до­го вто­ро­го або­ри­ге­на шапку, на­чи­ная с Пети. За­ну­ме­ру­ем або­ри­ге­нов без шапок, иду­щих за Петей по ча­со­вой стрел­ке: 1, \2, \ldots, 24, 25 .

За­ме­тим, что каж­дый або­ри­ген верно со­об­ща­ет сумму воз­рас­тов своих со­се­дей (если сло­жить на­зван­ные або­ри­ге­ном числа). Сло­жим числа, на­зван­ные 1-м, 3-м, ..., 25-м або­ри­ге­на­ми без шапок  — это будет сумма воз­рас­тов всех або­ри­ге­нов в шап­ках плюс воз­раст Пети. Сло­жим числа, на­зван­ные 2-м, 4-м, ..., 24-м або­ри­ге­на­ми без шапок  — это будет сумма воз­рас­тов всех або­ри­ге­нов в шап­ках минус воз­раст Пети. Вычтя из пер­вой суммы вто­рую и по­де­лив на 2, по­лу­чим воз­раст Пети.

Зная воз­раст лю­бо­го або­ри­ге­на, легко узнать, кто его со­се­ди, по их от­ве­там.

 

Ответ: все­гда.

 

II спо­соб. Для удоб­ства будем счи­тать, что в круге стоят через од­но­го 25 муж­чин и 25 жен­щин. По­ка­жем, как раз­ли­чить муж­чин (жен­щи­ны опре­де­ля­ют­ся ана­ло­гич­но). За­ме­тим, что два вы­ска­зы­ва­ния о воз­расте одной жен­щи­ны от­ли­ча­ют­ся на 1 тогда и толь­ко тогда, когда ее со­се­ди  — ры­царь и лжец. По­это­му до­ста­точ­но опо­знать од­но­го муж­чи­ну: далее по кругу опре­де­ля­ют­ся все осталь­ные.

Раз­берём два слу­чая.

1)  Для одной из жен­щин вы­ска­зы­ва­ния об её воз­расте раз­ли­ча­ют­ся на 2. Тогда оба её со­се­да  — лжецы, и, как ска­за­но выше, все муж­чи­ны опре­де­ля­ют­ся.

2)  Таких жен­щин нет. Все муж­чи­ны раз­би­ва­ют­ся на груп­пы: внут­ри такой груп­пы оба со­се­да каж­дой жен­щи­ны го­во­рят об её воз­расте одно и то же. Но пока не из­вест­но, какие груп­пы со­сто­ят из лже­цов, а какие  — из ры­ца­рей.

Сло­жив все числа, на­зван­ные муж­чи­на­ми, по­лу­чим удво­ен­ную сумму воз­рас­тов жен­щин. Те­перь сло­жим пер­вые числа, на­зван­ные муж­чи­на­ми. Если по­лу­чен­ная сумма имеет ту же чётность, что сумма воз­рас­тов жен­щин, то среди муж­чин чётное число лже­цов, а если не сов­па­да­ет  — нечётное. По­сколь­ку из двух воз­мож­ных ва­ри­ан­тов ко­ли­че­ство лже­цов чётно толь­ко в одном, пу­те­ше­ствен­ник опре­де­лит, какой из ва­ри­ан­тов пра­виль­ный.