chum
20:37 19-07-2005
Ех, чета всем лень, думать в такую духоту

Вот решение задачи из предыдущего поста:
Сначала введу понятие "четность цвета": цвет называется четным, если число гномиков с колпаками этого цвета ченое, в противном случае цвет является нечетным.
Теперь, для того чтобы каждый гномик мог точно определить цвет своего колпака, необходимо, чтобы была известна четность одного из цветов. В самом деле, если, например, известно, что белый - четный цвет, тогда каждый гномик сначала считает сколько белых колпаков он видит, а затем рассуждает так: если он увидел четное число колпаков, то он носит черный колпак, иначе тогды бы было нечетное число белых колпаков(если к четному числу прибавить 1, то получится нечетное число)и наоборот, если он видит что белых колпаков нечетное число, а белый цвет является четным, то он гномик понимает что на нем белый колпак.
Теперь, из вышеизложенного, становится ясна стратегия гномиков. Первый гномик должен сообщить остальным, сведения о четности одного из цветов. Причем, так как первый гномик не знает свой цвет, то он сообщает сведения о четности не учитывая себя(поэтому он выживает с вероятностью 1/2). А сообщить он эти сведения может например так. Заранее условлено, что первый гномик будет сообщать о четности или нечетности черного цвета, тогда пусть, например слово "белый " означает что число оставшихся гномиков(без первого) с колпаками черного цвета - четное, а слово "черный" означает что число оставшихся гномиков с колпаками черного цвета - нечетное. Теперь первый гномик, оказавшись в лапах гномикоеда, считает сколько гномиков с колпаками черного цвета осталось, если их четное число, он говорит белый в ответ на вопрос гномикоеда, в противном случае отвечает черный. Первый гномик либо погибает, либо выживает (как повезет), а все остальные после его ответа сразу же определяют свой цвет.
Вот и все решение
Комментарии:
Ekson
21:01 19-07-2005
Нихрена себе и всего то Правда я и задачу не читала... Мегафон за трафик деньги дерет сволач
chum
23:38 19-07-2005
Сатори
не она правда легкая))) просто про четность надо догадаться))