|
|
 |
Условие
Команда из n школьников участвует в игре: на каждого из них надевают шапку одного из k заранее известных цветов, а затем по свистку все школьники одновременно выбирают себе по одному шарфу. Команда получает столько очков, у скольких её участников цвет шапки совпал с цветом шарфа (шарфов и шапок любого цвета имеется достаточное количество; во время игры каждый участник не видит своей шапки, зато видит шапки всех остальных, но не имеет права выдавать до свистка никакую информацию). Какое наибольшее число очков команда, заранее наметив план действий каждого её члена, может гарантированно получить:
а) при n = k = 2;
б) при произвольных фиксированных n и k?
Решение
Отметим, что действия каждого игрока при любом плане действий однозначно определяются цветом шапок у остальных участников команды (так как другой информации у него нет).
а) Какую бы шапку ни надели на первого игрока, после этого однозначно определяется, какой шарф выберет второй игрок. Так как на второго игрока могут надеть шапку любого из двух цветов, то будут случаи, когда цвета шарфа и шапки у второго игрока не совпадут. Значит, нельзя гарантировать двух совпадений. Покажем, что одно совпадение всегда можно гарантировать.
Пусть игроки заранее договариваются о том, что первый игрок выбирает шарф так, чтобы его цвет совпал с цветом шапки второго игрока, а второй игрок выбирает шарф так, чтобы его цвет был противоположен цвету шапки первого игрока. Тогда, если им надели шапки одинакового цвета, то цвета шарфа и шапки совпадут у первого игрока, а если им надели шапки разного цвета, то у второго. Поэтому всегда будет ровно одно совпадение.
б) Пусть цвета шапок у всех игроков, кроме первого, фиксированы, а у первого игрока возможен любой из k цветов. Так как действия первого игрока однозначно определяются цветом шапок у остальных участников команды, то среди этих k случаев ровно в одном цвета шарфа и шапки у первого игрока совпадут. Поскольку на n – 1 игроков шапки k цветов можно надеть kn–1 способами, то среди всех kn способов надевания шапок на n игроков ровно в kn–1 случаях цвета шарфа и шапки у первого игрока совпадут. То же верно для любого игрока. Поэтому для любого фиксированного плана действий среди всех kn способов надевания шапок будет всего nkn–1 совпадений цвета шарфа и шапки у каких нибудь игроков. Значит, среднее число совпадений на один способ надевания шапок будет равно nkn–1 : kn = n/k и, следовательно, минимальное число совпадений не превосходит n/k.
Опишем план действий игроков, при котором они всегда могут
гарантировать [n/k] совпадений. Сопоставим цветам числа 0, 1, 2, ..., k – 1. Разобьём игроков на [n/k] групп по k человек (оставшиеся игроки пусть действуют произвольно). В каждой группе пусть игроки получат разные номера от 0 до k – 1. Во время игры пусть i-й игрок выбирает цвет шарфа так, чтобы сумма всех чисел, соответствующих цвету его шарфа и цветам шапок остальных игроков его
группы, давала при делении на k остаток i. При этом в любом случае ровно один игрок в группе угадает цвет своей шапки. А именно, если сумма чисел, сопоставленных цветам всех шапок игроков данной группы сравнима с j
по модулю k, то цвет шарфа и шапки совпадёт j-го игрока группы. Следовательно, в любом случае цвет шарфа и шапки совпадёт как минимум у [n/k] игроков.
