вторник, 16 ноября 2010 г.

Вечеринка с отравленным печеньем

Гипотезы Римана и Пуанкаре и еще пять великих математических задач века -- за разгадку хотя бы одной Бостонский математический институт обещает миллион долларов. Хотите попытать счастья? Вот условия трех из них -- проще не бывает...
Загадка первая. Сколько приглашенных?
Проблема была поставлена в 1928-м британским логиком Фрэнком Рэмси. Сколько гостей должно быть на приеме, чтобы как минимум трое из них знали друг друга и как минимум трое не знали? Ответ прост -- гостей должно быть шесть (можете проверить). Для того чтобы как минимум 4 человека знали друг друга и 4 не знали, должно быть хотя бы 18 приглашенных. Для 5 незнакомых и 5 знакомых между собой ответа уже нет -- известно только, что на приеме должны быть от 42 до 55 человек. И, несмотря на суперкомпьютеры, никто пока не может определить минимум гостей для бОльшего, чем 5, числа знакомых и незнакомцев. Приглашайте, считайте...
Загадка вторая. Не ешь отравленного печенья!
Эта недоступная современной математике задачка родилась в игре "Чомп" (chomp -- "чавкать"), придуманной математиком Дэвидом Гейлом в 1974-м. Очень простые правила, но до сих пор нет ни одной стратегии, позволяющей выиграть, которая работала бы всегда (один вариант выигрышной стратегии для того, кто ходит первым, есть). Представьте прямоугольник из "печений". В левом нижнем углу лежит смертельно ядовитое. Игроки по очереди берут печенье, "съедая" также те, что расположены справа и выше от выбранного. Тот, кому придется съесть отравленное, проигрывает. Как избежать этого навсегда?
Загадка третья. Почему 4, 2, 1?
Этот вопрос задал в 1937-м математик Лотар Коллац. Если взять любое целое число и поделить его пополам -- если оно четное, и умножить на 3 и прибавить 1 -- если оно нечетное, то повторение этой операции в конце концов приведет к цифрам 4, 2 и 1. Например: 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1. Или 13, 40, 20, 10, 5, 16, 8, 4, 2, 1... Для числа 27 такая цепочка будет состоять из 111 шагов, тем не менее все закончится четверкой, двойкой, единицей.
Но это утверждение не доказано для всех чисел до сих пор. Попытайтесь! Только, повторяя "четверка, двойка, кол", помните о несчастной судьбе Германна...

0 коммент.:

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