LINUX.ORG.RU
ФорумTalks

2Beria1937


0

0

>>По слухам с собеседования в микрософте: Есть группа людей. 
>>На наих надевают красные и синие шапки. Суть игры заключается в том,
>>что каждого, по очереди спрашивают какого цвета на нём шапка. Если
>>человек ощибаются, его убивают. Перед игрой всем дают время
>>говориться, потом ведут в комнату, гдё начинают спрашивать. 
>>Как выбрать стратегию называния цвета, чтобы минимизировать 
>>количество смертей?

>Мельчает народ... В советской школе (когда компьютеров ни у кого не
>было) эта задача была про ТРИ цвета шапок. И были школьники, которые
>это без подсказок решали.

Ну для 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. Теперь отбрасываем шелуху и выписываем тот самый общий ответ.

Как видно. Ход рассуждения вполне регулярен (никаких нетривиальных 
шагов не надо) => такая задача, по идее, должна быть доступна любому 
школьнику, который знает про вычеты, и подсказки тут не нужны. 
★★

Посовещаться им дают до того, как надевают шапки, а после - никому не разрешается говорить ни слова, кроме ответа на вопрос о цвете, причём в ответ разрешается только сказать "красный" или "синий", без каких-либо ещё слов, в случае нарушения всех дисквалифицируют. Правильно я понял?

anonymous
()

Предлагаю всей толпе скорешиться заранее и забить устроителей аттракциона ножками от стульев, сожрав трупы для ликвидации улик.

Gharik
()

>Суть игры заключается в том,что каждого, по очереди спрашивают какого цвета на нём шапка.

Предварительно им выкалывают глазки, чтобы они не увидели какие на них шапки?

>2Beria1937

в игре есть "блекдор":

Кто на вопрос ответит:

"Сегоднячпраздник у ребят, ликует пионЭрия!

Сегодня вгости к нам пришел Лаврентий Палыч Берия!"

Тому дают в руки наган и он может расстреливать кого угодно, не смотря на правильность ответов.

gnomino
()

Поскольку сообщение адресовано мне, я должен ответить.

ival

Эээ... можно проще. Цвета имеют номера 1 2 3. Первый человек называет цвет так, чтобы СУММА всех шапок делилась на три. Это смертник с вероятностью 2/3. Усё. Остальные члены шайки философов тоже называют цвет (свой) так, чтобы сумма делилась на три. Аттракцион проходит даже если они не видят каждый каждого, а построены в затылок, и отвечают начиная с последнего.

gnomino

Знаешь, когда я был живой, расстелять того, кто знает правильный ответ было чревато. Советская власть хорошо знала, что на этих математиках и инженерах ракетно-ядерный щит держится. Посадить могли (как Туполева за растрату казенных денег), но даже в шарашке у них были приличные условия и возможность работать.

Beria1937
()
Ответ на: комментарий от Beria1937

О, да. Интересно а какие такие условия были у Ландау в тюрьме? А как замечательно работал в лагере Румер? Почему растреляли Шубникова? А уж про преступное физическое уничтожение целого направления в виде гинетики можно и не упоминать - отрицать это может только полный ГСМ, да и то не всякий, а специально дрессированный. Кроме Туполева можно вспомнить, что и Королёв сидел и чуть богу душу не отдал пока его в шарашку не вытащили.

Evgueni ★★★★★
()
Ответ на: комментарий от Evgueni

Evgueni

Гражданин, Вам по теме (задачка про шапки мудрецов) есть что сказать? Нечего? Ааа... Выходит, что к разряду мудрецов вы не относитесь... Ну, револьвер у меня всегда с собой. (смайлик означающий пронизывающий взгляд)

Что Вас интересует по Ландау? Он сидел (на сколько мне сейчас помнится, весьма недолго) за антисоветскую агитацию. И ДОЛЖЕН был сидеть. Закон у нас одинаков для всех. 58 статья - это вам не шутки. После отсидки занимался теоретической физикой.

Фамилии Румер и Шубников мне сейчас не вспоминаются.

Посмотрите пожалуйста, как пишется слово "генетика" чтобы впредь не позориться. А то вдруг выяснится, что тот самый Лысенко имеет нобелевку по той самой генетике за 1983 год... А тот самый Вавилов имеет в своем активе только меховую породу "лиса колхозная". Мех к сожалению к пошиву непригоден... Смех и грех. "Преступное физическое уничтожение". [Матерное ругательство поскипано] Денег на игрушки давал не всем. Ну так и не обязан был.

Beria1937
()
Ответ на: комментарий от Beria1937

> Гражданин, Вам по теме (задачка про шапки мудрецов) есть что сказать? Нечего? Ааа... Выходит, что к разряду мудрецов вы не относитесь...

Не, ну нельзя же так явно сливать если по сути затронутого вопроса ответить нечего. И тема здесь отнюдь не причём. Так и лезут из Вас повадки ГСМ, причём плохо дрессированного, что без откровенного вранья фразы связной написать не можем.

Evgueni ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.