>>По слухам с собеседования в микрософте: Есть группа людей.
>>На наих надевают красные и синие шапки. Суть игры заключается в том,
>>что каждого, по очереди спрашивают какого цвета на нём шапка. Если
>>человек ощибаются, его убивают. Перед игрой всем дают время
>>говориться, потом ведут в комнату, гдё начинают спрашивать.
>>Как выбрать стратегию называния цвета, чтобы минимизировать
>>количество смертей?
>Мельчает народ... В советской школе (когда компьютеров ни у кого не
>было) эта задача была про ТРИ цвета шапок. И были школьники, которые
>это без подсказок решали.
Ну для 3 цветов тоже можно обойтись максимум одной смертью. Да и
вообще пусть у нас N цветов. Пронумеруем из от 0 од N-1 и отождествим
с классами вычитов по модeлю N. Первый, когда его спрашивают,
подсчитывает количество шапок по цветам
(обозначим их n_0,n_1,....n_{N-1}) и называет:
n_0*[0]+n_1*[1]+ ... + n_{N-1}[N-1]
//Здесь квадратными скобками обозначен класс вычетов
Каждый оставшийся считает тоже выражение для толпы из всех без
себя и первого. Разность между ответами дает цвет шапки.
Ход рассуждения:
Ну хорошо. Пусть у нас 3 цвета. Двумя смертями заведомо можно обойтись
(просто применив решения для случая 2 цветов), посмотрим можно ли
одной. Пусть у нас N человек в шапках в количестве n0,n1,n2 по цветам
+ один смертник, которому отвечать первым. Собственно нужно ввести
такую раскраску на множестве {(n0,n1,n2) | n0+n1+n2 = N}, что бы можно
было различить цвет недостающей шапки для (m0,m1,m2), таких что
m0+m1+m2 = N-1 щвета троек (m0+1, m1,m2) (m0, m1+1, m2) (m0, m1, m2+1)
должны быть разными. Что бы легче думалось думалось перенесем все это
дело на плоскость (забив на n0). Тогда задача стоит придумать
раскраску целых точек плоскости, такую что, для любых (p,q) цвета для
(p,q) (p+1,q) (p,q+1) были разными. Я сначала думал, что раскраска
рисуется почти от балды по диагоналям, и начал уже писать ответ, как
понял, что дело чуть чуть посложнее, а ручку с бумажкой искать было
влом. Вот сегодня вспомнилась. Глядя на требования к раскраске цвета
можно выписывать автоматически, тогда они заданы для (0,0) (0,1)
(1,0). Надо только доказать корректность. Беглый взгляд в поиске
инвариантов для индуктивного рассуждения результатов не дал. Тогда
подумал, пожет да ну ее, индукция, в топку. Может вывернуться с
отстатками от деления на 3. (p+q) mod 3 не подходит. При увеличении и
p и q на один раскраска тоже увеличивается на один. Значит надо взять
(p+2q) mod 3. Теперь отбрасываем шелуху и выписываем тот самый общий ответ.
Как видно. Ход рассуждения вполне регулярен (никаких нетривиальных
шагов не надо) => такая задача, по идее, должна быть доступна любому
школьнику, который знает про вычеты, и подсказки тут не нужны.
Ответ на:
комментарий
от Beria1937
Ответ на:
комментарий
от Evgueni
Ответ на:
комментарий
от Beria1937
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.