|
|
 |
Условие
Царь вызвал двух мудрецов. Он дал первому 100 пустых карточек и приказал написать на каждой по положительному числу (числа не обязательно разные), не показывая их второму. Затем первый может сообщить второму несколько различных чисел, каждое из которых либо записано на какой-то карточке, либо равно сумме чисел на каких-то карточках (не уточняя, как именно каждое число получено). Второй должен определить, какие 100 чисел написаны на карточках. Если он этого не сможет, обоим отрубят головы; иначе из бороды каждого вырвут столько волосков, сколько чисел сообщил первый второму. Как мудрецам, не сговариваясь, остаться в живых и потерять минимальное количество волосков?
Решение
Докажем что можно ограничиться потерей 101 волоска у каждого мудреца. Пусть первый напишет на карточках числа 1, 2, 4, ..., 299, а второму сообщит эти числа и их сумму. Второй, услышав число 1, поймёт, что есть карточка, не превосходящая 1. Услышав очередное число 2k, он поймёт, что есть ещё одна карточка, не превосходящая 2k, поскольку сумма оценённых уже карточек не превосходит 1 + 2 + ... + 2k–1 < 2k. Когда он услышит 2100 – 1, он уже будет знать, что сумма 100 карточек не больше этого числа. Значит, это и есть сумма, все оценки превращаются в равенства, и второй определит все карточки.
Теперь докажем, что 100 волосков недостаточно. Пусть второму сообщены 100 различных чисел, и a < b – два из них. Тогда все услышанные числа могут быть написаны на карточках. Но кроме этого набора карточек подойдёт и набор с числом b – a вместо b.
Замечания
1. В примере можно использовать любой набор карточек, в котором число на каждой следующей карточке больше суммы чисел на всех предыдущих.
2. 6 баллов.
