Дети в песочнице

[Gypsy]

Сегодня наткнулся на анализ одной задачи и ее решения. Сама идея задачки - стандартная для информатиков, ничего особенного, но автор приводит одно интересное наблюдение...

Задача:

N детей играли в песочнице, из них K испачкали себе лоб грязью. почему именно лоб - чтоб сами не видели свою грязь. дети между собой не переговариваются, вредные очень.

Приходит отец, вещает на весь двор "по крайней мере один из вас испачкал себе лоб". Потом отец, будучи неизлечимым философом, начинает задавать один и тот же вопрос: "можете ли вы доказать испачканность собственного лба". Он продолжает задавать вопрос, пока все испачканные не скажут "да" а все не-испачканные "нет".

Решение:

Если дети умные и правдивые и рациональные создания, то ровно после K вопросов все испачканные смогут доказать свою испачканность.

Логика такая.

Для одного испачканного ребенка - тривиально. На первый же вопрос ответит "да", потому что в группе должен быть хоть один испачканный, а он испачканных не видит.

Допустим испачканы двое детей.

Тогда, после первого вопроса, все не-испачканные скажут нет, и двое испачканных тоже скажут нет, потому что ни один из них не знает сколько в группе испачканных - один (не он), или двое (он и тот другой испачканный).

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

То есть после второго вопроса двое испачканных сказали "да", все остальные - "нет".

Та же логика распространяется на случай K детей. На первые K-1 вопросов все хором отвечают "нет", на K-й вопрос все испачканные отвечают уже "да".

Странное наблюдение:

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

Скажем испачканы 12 детей из 20. То что отец говорит "хотя бы один из вас испачкан", это ни испачканным, ни не-испачканным ничего не говорит. Ведь испачканные и так видят что полно испачканных, а не-испачканные тем более

С другой стороны можно доказать, что если бы отец не произнес это первое предложение, то на его последующие вопросы "можете ли вы доказать испачканность собственного лба" дети всегда отвечали бы "нет". До бескончености

Какие выводы можно сделать?

[Obelix]

Prosto slepaya dogadka. Mozhet v sluchaye odnogo ispachkannogo rebenka vse bi govorili "net"?

[Gypsy]

Фишка в том, что если отец сначала ничего не скажет,
то испачканным детям никогда не хватит информации чтоб на 100% сказать что они испачканы. Доказывается индукцией по кол-ву испачканных детей.

Но когда отец в самом начале говорит свое предложение, что "среди вас есть испачканные", он непосредственно никакой новой информации не передает отдельным детям. И все-таки это "ничто" в корне меняет ситуацию. Обьяснение конечно-же есть, но хотелось бы услышать разные мнения...

[Gypsy]

Originally Posted by Obelix

Prosto slepaya dogadka. Mozhet v sluchaye odnogo ispachkannogo rebenka vse bi govorili "net"?

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

Но в случае с двумя и более детьми, неочевидно почему результаты разные. Потому что с точки зрения классического определения информации, каждый ребенок получает ровно ноль (0) битов информации от первого предложения отца. Разве не так?

[Gypsy]

В двух словах, имеется пример системы где распространение абсолютно пустого, никому ничего нового не говорящего "известия" меняет всю картину и делает систему намного более умной и распознающей собственные качества которые не могла распознать до этого.

По-моему, неплохая мысль для философов (и даже политологов ). Или докажите что я (скорее автор статьи) не прав

[Obelix]

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

Но в случае с двумя и более детьми, неочевидно почему результаты разные. Потому что с точки зрения классического определения информации, каждый ребенок получает ровно ноль (0) битов информации от первого предложения отца. Разве не так?

В случае одного ребенка первое предложения отца несет с собой ненулевую информацию только для одного ребенка.

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

Т.е. помимо того что информация нулевая, еще есть информация о том что эта информация оказалась нулевой для всех остальных. Вроде так.

P.S. Gyps jan sorry, karoxa mi qich gexavari em artahaytvum, я о теории информации знаю ту мизерную долю которая пересекается со статфизикой... И то громко сказано

[Obelix]

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

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

[Gypsy]

Originally Posted by Obelix

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

Т.е. помимо того что информация нулевая, еще есть информация о том что эта информация оказалась нулевой для всех остальных. Вроде так.

Ну да, что-то вроде того.

Идея в том, что если у тебя есть система агентов способных мыслить, то информация переданная системе (и соответсвенно, знания системы) не всегда является "суммой информаций" переданных всем ее агентам. В данном случае мы передали нулевую информацию всем агентам, а они стали действовать "умнее", то есть система приобрела полезные знания.

Можешь почитать об этом в самой статье.

Originally Posted by Obelix

P.S. Gyps jan sorry, karoxa mi qich gexavari em artahaytvum, я о теории информации знаю ту мизерную долю которая пересекается со статфизикой... И то громко сказано

Так ты у нас физик? Или математик?

[Gypsy]

Originally Posted by Obelix

Может я в чем-то запутался, но вроде приведенное решение не действует в случае более двух (скажем трех) испачканных детей.

В случае трех испачканных детей.

Отвечая на первый и второй вопросы, каждый из троих испачканных думает следующее:

никакой информации насчет моей собственной испачканности никто пока что не дал, так что отвечу "нет"

после первого и второго вопроса, все отвечают "нет".

(в общем случае, на первые K-1 вопросов все всегда отвечают "нет".)

Отвечая на третий вопрос, каждый из троих испачканных думает следующее:

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

(в общем случае, дойдя до вопроса #K все испачканные поймут, что если бы испачканных было бы K-1, они бы уже ответили "да" на предыдущий вопрос)

[Obelix]

Я не принял в счет возможность их узнать доказалось ли состояние или нет ) Так вроде все логично

Так ты у нас физик? Или математик?

По паспорту физик ну или хотя бы по зачетке. А так в душе смесь математика, программиста и редкого лентяя.