четверг, 8 апреля 2010 г.

Решение задачи о гномиках в разноцветных шапках

Александр выложил интересную задачу про гномиков.

Не придумал как вставить картинку к нему в каменты, поэтому решение привожу здесь.

Итак, вот схема:
[Image]
В первой строке отмечены номера гномиков (для удобства), во второй их реальное расположение. Гномики смотрят вправо, т.е. номер первый видит всех, последний никого. Далее идут шаги которые гномикам нужно предпринять, чтобы всем спастись (в колонках отмечено кто и что делает).

Итак, первый гномик делает операцию последовательного XOR-а. Т.е. он берет 2-го и 3-го гномика и проводит XOR, результат я записал в колонку G (под третьего гномика). После чего он берет результат и XOR-ти с 4-м (результат под 4-го), потом этот результат XOR-ит c 5-ым и т.д. В итоге он получает значение, которое и называет (отмечено желтым). В зависимости от того совпало оно или нет людоед его съедает или нет и тут работает чистая удача.

Но дальше, все уже знают конечный XOR последовательности и могут понять кто они. Например на шаге 3 второй гномик предполагает, что он 0 (отмечено голубым). Исходя из этого он проводит последовательный XOR (шаг 4) и получает в результате 0 (отмечено красным). Поскольку его результат не совпадает с начальным, который посчитал 1-й гномик  (желтым) он понимает, что предположение о том, что он 0 было не верным, а значит он 1. И на 5-м шаге говорит: 1. Дальше аналогично третий гномик делает предположение и считает XOR и т.д.

UPD.: (извините, нужно было убегать, потому набросал саму идею, теперь формализую)
Или, говоря строгим языком математики:
Обозначим состояние шапки каждого гномика как X. Тогда состояние шапки n-го гномика будет Xn. Пусть, для определенности, у черных шапок X=1, а для белых X=0.
Так же для определенности, пусть общее количество гномиков равно m.
Вначале первый гномик (который видит всех) должен вычислить "общий XOR" (обозначим его Z) последовательности гномиков по формуле:

Z1=(((X2 XOR X3) XOR X4) XOR X5) ... XOR Xm)

Полученный результат он называет и в зависимости от удачи людоед его съедает, либо нет. (Если Z1 совпало с X1, то, соответственно не съедает). Однако таким образом всем становится известно состояние X1.
Дальше каждый гномик делает предположение о своем состоянии (Xn) и вычисляет собственный "общий XOR" (Zn) по формуле:

Zn=(((Xn-1 XOR Xn) XOR Xn+1) XOR Xn+2) XOR Xn+3) ... XOR Xm)

Если Zn отличается от Z1 то это означает, что предположение гномика о собственном состоянии было ошибочным и он называет противоположное. При совпадении, соответственно, предположение считается верным и называется именно оно.

Таким образом все гномики начиная со 2-го назовут заведомо верные собственные состояния.

Задача решена.

6 комментариев:

Ragnar комментирует...

Не будет работать, если все гномы (или все, кроме первого) одеты в колпаки одного цвета (а это не исключается, исходя из условия). Точнее будет, но рискует быть сожранным и второй, что проиворечит условию =)

Green FiLin комментирует...

Рагнарчег, будет работать.

Ragnar комментирует...

Ну, так как ты описал подетальнее, будет. Я малость запутался в твоем детальном и прозрачном описании процесса :-D
Но это фактически та же проверка четности =)

Green FiLin комментирует...

Я не понял, этим "фактически это та же проверка" это ты согласился, что будет работать для всех одинаковых или, наоборот, споришь, что не будет?

Алексей комментирует...

не понимаю откуда Вы взяли эту формулу Zn=(((Xn-1 XOR Xn) XOR Xn+1) XOR Xn+2) XOR Xn+3) ... XOR Xm). Нам незачем цвет шапки первого гнома

Green FiLin комментирует...

Согласен. Для n=2 из формулы нужно убрать часть (Xn-1 XOR Xn) и заменить ее на Xn.
Для остальных же кажется, что все правильно.

Отправить комментарий