Простая задача, которая поставила в тупик 99%

Описание: В каждом из трёх стаканов находится напиток. Мы можем удвоить количество напитка в одном стакане, перелив его из другого. Можем ли мы опустошить один из стаканов? В этом видео мы решаем эту задачу.

Чтобы быть в курсе событий, подпишитесь на этот YouTube-канал.

Разделы
00:00 Задача о трёх стаканах
05:37 Первый алгоритм
10:42 Временная сложность
12:31 Более быстрый алгоритм
14:50 Сложные тройки
16:28 Нерешённая задача

Спасибо моей дочери, Мине Боппане, за рецензирование видео. Она репетитор по математике:
http://meenaboppana.com

Спасибо Presage Media за монтаж и анимацию видео:
https://www.presage.media

На отметке 2:28 я предложил зрителям решить тройку (57, 65, 73) за десять переливаний. Вот десять вариантов: (114, 65, 16), (114, 49, 32), (114, 17, 64), (114, 34, 47), (80, 68, 47), (80, 21, 94), (160, 21, 14), (139, 42, 14), (139, 28, 28) и, наконец, (139, 56, 0).

Ссылки

Задачи Всесоветских математических соревнований (1961–1986):
https://olympiads.win.tue.nl/imo/sovi...
Задача 148 1971 года является первоисточником задачи о трёх стаканах (перевод с русского на английский).

Леонард Ф. Клосински, Джеральд Л. Александерсон и Лорен К. Ларсон (1994), «Пятьдесят четвертая математическая конференция имени Уильяма Лоуэлла Патнэма», American Math Monthly 101:8, страницы 725-734.

https://math.hawaii.edu/home/pdf/putn...
Содержит задачи, решения и результаты конференции Патнэма 1993 года. Задача B-6 — задача о трех стаканах (изложена в чисто математических терминах). Решение в статье использует степени двойки, но в остальном отличается от решения, представленного в видео.

Киран С. Кедлая, Бьорн Пунен и Рави Вакил (2002), «Математическая конференция имени Уильяма Лоуэлла Патнэма 1985-2000: задачи, решения и комментарии», MAA Press.

Задача B6 1993 года — это задача о трёх стаканах (сформулированная в чисто математических терминах). Авторы представляют три решения, каждое из которых использует степени двойки. Решение 1 (приписываемое Гарту Пейну) — это первый алгоритм, который мы представляем в видео.

Джозеф А. Галлиан, «Конкурс Патнэма с 1938 по 2018 год».

https://www.d.umn.edu/~jgallian/Putna...
Содержит исторические данные о конкурсе Патнэма. В частности, в таблице 5 представлены 5 лучших результатов и медианный результат за каждый год с 1967 по 2018 год.

На этой странице содержится дополнительная информация о конкурсе Патнэма:
https://maa.org/putnam/

Питер Винклер (2004), «Математические головоломки: коллекция для знатоков», CRC Press.
См. головоломку «Опустошение ведра». Винклер предлагает два решения, каждое из которых использует степени двойки. Первое решение, которое он придумал, требует порядка n² переливаний. Второе решение, независимо предложенное Гартом Пейном и Сванте Янсоном, — это первый алгоритм, который мы представляем в видео; Винклер правильно утверждает, что алгоритм использует не более порядка n log n переливаний, но, как мы указываем в видео, алгоритм использует не более n переливаний.

Питер Винклер (2004), «Пять алгоритмических головоломок», дань уважения математическому волшебнику А. К. Питерсу.

https://math.dartmouth.edu/~pw/papers...
См. головоломку «Опустошение ведра». По сути, то же самое представление, что и в книге головоломок Винклера выше.


Фабиан Фрай, Питер Россманит и Дэвид Вехнер (2020), «Открытая задача о разливе», 10-я Международная конференция «Развлечения с алгоритмами» (FUN 2021).
https://doi.org/10.4230/LIPIcs.FUN.20...
Представляет алгоритм для решения задачи о трех стаканах с разливом порядка (log n)². Также представлены некоторые тройки, требующие как минимум порядка log n разливов. Наконец, представлены некоторые численные данные о функции Pours. Изучив данные, авторы предполагают верхнюю границу порядка log n разливов.

Герольд Йегер и Туомо Лехтиля (2025), «Обобщенная задача о двойном разливе: анализ, границы и алгоритмы».

https://arxiv.org/abs/2504.03039
Для четырех стекол авторы представляют алгоритм, использующий порядок (log n) * log(log n) разливов. Они также характеризуют случаи, когда можно решить задачу для двух стекол.

Запись в онлайн-энциклопедии целочисленных последовательностей (OEIS) о (обратной) функции Pours:
https://oeis.org/A256001

Джон Тромп (2015), программа на языке C для вычисления функции Pours:
https://oeis.org/A256001/a256001.c.txt