March 12th, 2009

lenin

Пишут, что...

У г. Москва есть число Эрдёша, равное двум, благодаря статье, написанной в соавторстве с Дж. Х. Конвеем.
Статья описывает задачу о N мудрецах с написанными на лбу неотрицательными числами (стандартные в таких задачах дисклеймеры приложимы), и доске, на которой написаны M чисел, одно из которых является суммой чисел на мудрецких лбах. Мудрецов опрашивают, знают ли они, что написано у них на лбу, по кругу, пока один из них не скажет, что знает.
Каковы ограничения на N и M для гарантии конечности процесса?

Да, чуть не забыл. Статья еще интересна тем, что ссылается сама на себя.