Задача 67581

Тема:    [ Кооперативные алгоритмы ]

Сложность: 4 Классы: 6,7,8,9

Условие

Автор: Грибалко А.В.

Петя и Вася хотят показать следующий фокус. У зрителей есть пять карточек с числами 1, 2, 3, 4, 5. Две из них они отдают Пете, две — Васе, а одну оставляют себе. Сначала Петя называет число на одной из своих карточек, затем Вася называет число на одной из своих, после чего Петя должен назвать число на карточке у зрителей. Как договориться Пете и Васе, чтобы фокус всегда удавался?

Решение 1

Расположим мысленно карточки по кругу в порядке 1, 2, 3, 4, 5. Если двигаться по часовой стрелке, то от одной из карточек Пети до другой нужно сделать не более двух шагов. Обозначим вторую из них E, пусть Петя назовёт число на ней, тогда первая его карточка – C или D (см. левый рисунок).

Соберём мысленно карточки C, D, E в одну стопку (отметим, что в этой стопке две карточки Пети). Карточки Васи лежат в двух из трёх стопок (см. правый рисунок) и от одной до другой можно дойти за шаг по часовой стрелке. Пусть и Вася назовёт число на второй из своих карточек.

Теперь Петя знает обе Васины карточки. Действительно, он знает, в каких стопках они лежат на правом рисунке. И даже если одна из Васиных карточек в стопке C-D-E, то Петя может понять, какая именно, потому что в этой стопке только одна карточка не Петина.

Решение 2

Всего вариантов пар карточек у Пети $(5\cdot 4):2=10$, а отдельных карточек 5. Чтобы фокус удался, нужно закодировать варианты так, чтобы называемому Петей числу соответствовали ровно два варианта пар. Это можно сделать так:

Пары карточек у Пети	Петя называет
1, 5 или 1, 4	1
1, 2 или 2, 5	2
1, 3 или 2, 3	3
2, 4 или 3, 4	4
3, 5 или 4, 5	5

Теперь по названному Петей числу Вася может выяснить два варианта оставшегося Петиного числа. Обозначим наименьшее из возможных вторых Петиных чисел как A, наибольшее из них – B, наименьшее из двух оставшихся чисел – C, наибольшее из оставшихся – D.

Поскольку одно из чисел A, B – у Пети, возможно 5 вариантов того, какие две карточки у Васи; пусть он назовёт число в соответствии с таблицей:

Карточки Васи	Вася называет	У зрителей
A, C	C	D
B, C	C	D
C, D	D	A или B (та, которая не у Пети)
A, D	A	C
B, D	B	C

Так по ходу Васи Петя сможет понять, карточка с каким числом осталась у зрителей.

Источники и прецеденты использования

олимпиада
Название	Математический праздник
год
Год	2026
класс
Класс	7
задача
Номер	6