Взвешивания и четырёхмерность

Добрый день в новом добром году!

Все уже привыкли к мысли, что «как раньше» уже не будет? Я не про ковид (кстати, кто уже привился?), а про то, что даже если большинство успешно получит вакцину, то мир прежним-то не станет. И это как-то одновременно интересно и беспокойно получается. Даже не говоря об остальных событиях в мире (включая такие индикаторы, как война с вышками сотовой связи, привычность массового двоемыслия и т.д.).

Поэтому давайте поговорим о хорошем и красивом:

1) А знаете ли вы задачи на взвешивание, которые можно решить (или легко решить) если у нас N+1 монета, но невозможно (или очень сложно) решить, если у нас всего N монет? Я к тому, что обычно при росте количества монет растёт и количество взвешиваний, поэтому в формулировке вида «выясните ... за 3 взвешивания» рост количества монет N вызывает проблемы. А хотелось бы, чтобы в какой-то момент уменьшение N вызвало проблему. Ниже я приведу тривиальный пример, чтобы стало яснее.

А пока всем любителям таких задачек хочу напомнить об интересном расширении одной старинной задачки. Итак, двенадцать лет назад в первом же комментарии к очень простой задачке было сказано: «Решил, но потому, что знал более сложный вариант этой задачи (12 монет и неизвестно, в какую сторону отличается по весу фальшивая)». Тогда мне это вообще не показалось «более сложным вариантом», а показалось совсем другой и очень сложной задачкой (без бумажки её в голове удержать нелегко). Но задачка-то очень хорошая, поэтому вот ссылка для всех желающих посмотреть на её обобщение из Кванта №10 за 1979 — «Как обнаружить фальшивую монету» (заодно тут же ответ на вопрос «Кому вообще эти системы счилений нужны?»)

Но вернёмся к тривиальному примеру. Представьте, что вам надо с помощью весов обнаружить единственную фальшивую монету среди N монет. Если N=1, то рассматривать нечего (есть только фальшивая), но вот если N=2, то никаким взвешиванием этих двух монет мы не выясним, тяжелее фальшивая или легче, а значит не сможем её определтиь. При увеличении же N до 3 проблема решается — за два взвешивания мы надёжно выявляем фальшивую монету. А знаете ли вы менее тривиальный пример? Хотелось бы узнать такие задачи, в которых нам никак не справиться (или очень сложно), если есть всего N монет, но которую можно решить (или очень легко решить), имея N+1 монету.

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

2) Любителям красоты и четырёхмерности рекомендую с третьей минуты посмотреть ролик SIGGRAPH 2020 Technical Paper: n-Dimensional Rigid Body Dynamics. В нём сперва покажут элементарное (взгляд плоского человечка на трёхмерные предметы), а потом уже взаимодействие четырёхмерных объектов глазами трёхмерных нас. По-моему, ролик было бы полезно показать детям.



3) Кстати, если не показывали детям игру-тренажёр Море слов, то обратите на неё внимание! Оно и взрослым может быть интересно (не только в плане профилактики болезни Альцгеймера), а дети тут и память со способностью перебирать потренируют, и словарный запас расширят. Чем-то оно напоминает Mindtrainer, т.к. похоже, что генерирует задачки, а не берёт их из заранее подготовленного списка. Мне такие штуки нравятся. А что вам удачного попадалось?

Хорошего года и удачного начала рабочей недели!