10 янв. 2021 г.

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

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

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

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

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, т.к. похоже, что генерирует задачки, а не берёт их из заранее подготовленного списка. Мне такие штуки нравятся. А что вам удачного попадалось?

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

5 комментариев:

  1. Вот вам классическая задача:
    Некий товар стоит N+1 монету.
    Нам никак не справиться, если есть всего N монет, но которую очень легко решить имея N+1 монету.

    ОтветитьУдалить
    Ответы
    1. Анонимный11.01.2021, 06:42

      Надо купить товар, не имея дисконтных карт и не торгуясь?

      Удалить
    2. Андрей, могли бы Вы пояснить, в чём условие задачи? Я не уверен, что правильно понимаю. Выше аноним предположил, что над всего лишь купить товар, но это больше похоже на шутку, чем на задачу :-)

      Удалить
  2. Анонимный14.01.2021, 16:59

    Ну привился я гамалеевской вакциной, только надо дождаться, появятся ли антитела. По-моему, это стоит сделать, если приглашают, чтобы обезопасить хотя бы себя. А вот до коллективного иммунитета с такой скоростью вакцинацией мы до следующего НГ не дойдём. Не понятно, короче, что делать, особенно, если надо съездить в Европу куда-нибудь.

    ОтветитьУдалить
    Ответы
    1. Спасибо, что поделились! В Ваших краях скорость вакцинации ограничена количество вакцин в поликлиниках или нежеланием людей вакцинироваться? Мне сейчас кажется, что скоро мы упрёмся во второй фактор. И вот тогда, я думаю, надо вакцинацию делать платной, причём каждый месяц цену повышать. Мне кажется, часть иррациональных людей это приведёт в прививочные кабинеты.

      Удалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний