Ромео, Джульетта и Микки-Маус против клизмы.

Сегодняшняя задачка на злободневное:

Однажды блогеров Ивана, Марью, Ромео, Джульетту и Микки-Мауса посадили в карантин. Раз в день санитары выбирают случайного из них и ведут на процедуры. В процедурной есть выключатель и лампочка, которую можно включить или выключить. Как только кто-либо из блогеров понимает, что все остальные хотя бы по разу побывали на процедурах – то сразу идёт к главврачу и говорит об этом. Если угадал – всех выпускают на свободу, нет – всем делают клизму и карантин начинается с нуля.

Карантин жёсткий: все в одиночных палатах, мобилы отобрали, интернетов тоже нет, QR-коды на автотранспорт заказать нельзя. Обмениваться информацией тоже никак. Но пока их везли в больницу они успели договориться о стратегии, смогли выяснить когда всех «отпроцедурили», им вернули мобилы, они вышли на свободу и отбложились по этому поводу. Как они это сделали?

Справитесь? А сколько им в среднем времени на это потребуется? А если их в карантине 10? А если 100? Просто любопытно. Можно даже программу на эту тему написать :) Когда они с 50% вероятностью закончат карантин – ага?

На всякий случай поясняю условия:
— процедуры проводятся только для одного из них и только раз в день;
— санитары выбирают кого-то совершенно случайно;
— нацарапать на стене «здесь был ваня» нельзя — шутники-санираты допишут «маша и все остальные» => сразу клизма и карантин по новой.

Дерзайте!

А я дерзну рассказать решение предыдущего математически-археологического наследия им.Евклида.

Задачка 1. Евклид доказал, что если 2ⁿ — 1 — простое число, то 2^{(n — 1)} * (2ⁿ — 1) — совершенное (n — натуральное число, само собой). Получится ли нам самостоятельно доказать этот факт? Умнее ли мы Евклида или же всё ещё нет?

Решение: 2^{(n — 1)} * (2ⁿ — 1), где 2ⁿ — 1 — простое число можно записать вот так: 2^{(n — 1)} * p — какие у него делители? Все степени двойки, простое p тоже делитель, а также все степени двойки, умноженные на p (кроме самого проверяемого числа). Вот такой ряд получается:

1, 2, 4, … 2^(n-1), p, 2*p, 4*p, 2^(n-2)*p

Ещё могут у него быть делители? Да откуда им взяться? На другие простые числа кроме 2 и p наше число не делится. Теперь остаётся просуммировать этот ряд и посмотреть на результат. 1,2,4… — это геометрическая прогрессия, сумма которой считается по простой формуле. Для двойки эта формула будет такой:

1 + 2 + 4 + … + 2^(n-1) = 2ⁿ — 1

То есть, искомая сумма всех делителей равна…

2ⁿ — 1 + p*(2^(n-1) — 1) = 2ⁿ — 1 + (2ⁿ — 1)*(2^(n-1) — 1) =

= 2ⁿ — 1 + 2^(2n-1) — 2ⁿ — 2^(n-1) + 1 =  2^(2n-1)— 2^(n-1) = 2^(n-1) * (2ⁿ — 1)

И… получили тоже самое чисто. То есть, сложили все делители числа 2^(n-1)*(2ⁿ-1) и получили ровно тоже самое число. То есть, числа такого вида являются совершенными.

Привет Евклиду!

Задачка 2. Доказать, что все чётные совершенные числа имеют вид 2^{(n — 1)} * (2ⁿ — 1), где 2ⁿ — 1 — простое.

Решение у меня получилось какое-то непростое, наверное, не самое оптимальное. Да и не факт что правильное :) Рассуждения на эту тему можно найти вот здесь.

Задачка 3. Доказать, что нечётных совершенных чисел не существует.

Решение: Поиском нечётных совершенных чисел занимается проект распределённых вычислений oddperfect.org — но пока ни одного такого числа не найдено, также ни доказано, ни опровергнуто их существование… да и сайт этого проекта уже мёртвый. Подробнее про такие числа можно полюбопытствовать вот здесь.

А кто в решении этой задачки показал себя молодцом? :) Конечно bar_suk! Поздравляю!

А заодно давайте посмотрим на правильные ответы ещё одной недавней задачки на сообразительность и ориентацию в пространстве.

Разумеется, это не совсем Галапагосы. Это здесь. Кстати, чудное место! Я там был ровно два года назад! Отличное местечко покарантинить… 50 оттенков синего.

Вторая загадка: что не так на этой фотке?

На самом деле Эльбрус здесь отзеркален. Гора с севера выглядит вот так: слева — восточная вершина, справа — западная.

И третья загадка: где сделана эта фотка?

Судя по мусору на дороге и узкой улочке налево, похоже на Лондон. Грузовик «праворукий» (по дворникам видно) — подходит («леворуких евро-грузовиков в Лондоне не припомню, а машины бывают. Кстати, что первая машина леворукая — это обманка). Что там на вывеске написано? «Anje»? Ничего… Ага, там две точки над названием! Arije — есть такое! И в Лондоне есть. Но что-то в гугле как-то не так выглядит.

А в других источниках — точно так.

Ага! Предыдущая фотка 2012 года, они переехали. Вот сюда: 165 Sloane St, London.

И у нас снова есть молодцы, которые справились с поставленными задачами: lilo_jacob nagel_neu Alex Kondrasovas.