Задача 67282

Темы:    [ Теория алгоритмов (прочее) ] [ Шахматная раскраска ]

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

Условие

Автор: Шаповалов А.В.

Решил шах проверить придворного мудреца. «Вот тебе шесть шкатулок, — сказал шах, — с надписями 1, 2, 3, 4, 5, 6 на крышках. В каждой шкатулке золотая монета, которая весит ровно столько граммов, сколько написано. Ты расставляешь шкатулки как угодно в клетках прямоугольника 2×3. Потом я втайне от тебя меняю местами монеты в каких-то двух шкатулках, стоящих в соседних по стороне клетках (или ничего не меняю). Затем ты укажешь на несколько шкатулок, а я назову тебе общий вес монет в них. Если после этого правильно определишь, какие монеты я переложил, останешься при дворе. А не сможешь — прогоню вон!»

Как может действовать мудрец, чтобы выдержать испытание?

Решение

Мудрец может расположить шкатулки, например, так:

4	5	1
2	6	3

И указать шаху те шкатулки, где на крышках массы 2, 3 и 5. Если шах назовёт сумму 10, значит, он ничего не менял. Если он менял местами какие-то монеты, сумма всякий раз будет другой:

Что менял шах	Сумма
ничего	10
4 и 2	12
5 и 6	11
1 и 3	8
4 и 5	9
2 и 6	14
5 и 1	6
6 и 3	13

Как видим, все суммы разные, так что по сумме мудрец сможет понять, менялись ли монеты и какие, и назвать их правильно.

Замечания

Как мог рассуждать мудрец, придумывая пример? Раскрасим прямоугольник 2 × 3 в шахматном порядке. Ясно, что надо назвать либо три белые клетки, либо три чёрные — в противном случае среди названных (или не названных) будут две соседние, и мудрец не сможет определить, поменял в них шах монеты или нет. Возможные суммы в трёх шкатулках меняются в диапазоне от 6 до 15, причём сумма от замены монет может увеличиться или уменьшиться на 1, 2, 3, 4 или 5. Чтобы восемь сумм (исходная и при любом из семи обменов) были различны, исходная сумма должна быть примерно в середине ряда (равняться 10 или 11). Дальше можно действовать подбором.

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

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