Wert предложил свое решение и для 39 монет тоже, используя разбиение 39=3*(1+3+9) - он раскладывал монеты в мешочки(1, 3, 9), а потом переставлял их, на первом этапе большие, потом поменьше. да?
===========================================================
Да, это совершенно верное и очень глубокое замечание! Вы описываете обобщение метода Джека Верта, которое часто называют методом группировки по степеням тройки. Это действительно элегантный способ масштабировать интуицию метода Верта на большие числа.
Вы абсолютно правы в том, как работает эта структура. Давайте разберем эту красивую идею.
Метод Верта через "мешочки" (степени тройки)
Идея состоит в том, чтобы представить общее число монет M в троичной системе счисления и использовать эту структуру для взвешиваний.
Для 39 монет формула M = (3^N - 3) / 2 при N=4 дает (81-3)/2 = 39.
Это число 39 можно представить в виде суммы: 39 = 13 + 13 + 13.
Теперь каждую из этих трех больших групп по 13 монет мы, в свою очередь, раскладываем по степеням тройки: 13 = 1 + 3 + 9.
Итак, у нас есть три "супер-группы" (назовем их A, B, C), и каждая из них состоит из трех "мешочков" разного размера:
Группа A: {A_1 (1 монета), A_3 (3 монеты), A_9 (9 монет)}
Группа B: {B_1, B_3, B_9}
Группа C: {C_1, C_3, C_9}
Всего 3 * (1+3+9) = 3 * 13 = 39 монет.
Взвешивания по методу Верта
Логика очень похожа на случай с 12 монетами, но оперирует целыми группами.
Взвешивание 1: Большие группы
Кладем на весы две из трех "супер-групп".
Левая чаша: Группа A (13 монет)
Правая чаша: Группа B (13 монет)
В стороне: Группа C (13 монет)
Исход 1.1: Весы в равновесии.
Вывод: Все монеты в A и B — настоящие. Фальшивая находится в Группе C.
Задача: Найти 1 из 13 за оставшиеся 3 взвешивания, имея 26 настоящих монет. Это классическая задача, которая решается аналогично (сравниваем группы по 9, потом по 3, потом по 1).
Исход 1.2: Весы не в равновесии. (Допустим, A > B)
Вывод: Либо в группе A есть тяжелая монета, либо в группе B есть легкая монета. Группа C — контрольная, все монеты в ней настоящие.
Задача: Найти 1 из 26 "подозрительных" монет за 3 взвешивания.
Взвешивание 2: Перестановка "мешочков"
Это самый хитрый и красивый ход, который вы и описали. Мы перетасовываем "мешочки" между чашами и контрольной группой, чтобы локализовать проблему.
Берем самые большие мешочки: A_9, B_9, C_9.
Переставляем их: A_9 остается на месте, B_9 меняется местами с C_9.
Левая чаша: A_9 (9 монет из "потенциально тяжелой" группы)
Правая чаша: C_9 (9 заведомо настоящих монет)
В стороне: B_9 (9 монет из "потенциально легкой" группы) и все остальные мешочки {A1, A3, B1, B3, C1, C3}.
Интерпретация Взвешивания 2:
Равновесие: Фальшивой монеты нет ни в A_9, ни в C_9. Значит, она в B_9 (и она легкая). Задача свелась к поиску 1 легкой из 9 за 2 взвешивания (что легко: 3х3, потом 1х1).
Левая чаша тяжелее: Фальшивая монета в A_9 (и она тяжелая). Задача свелась к поиску 1 тяжелой из 9 за 2 взвешивания.
Правая чаша тяжелее: Этого быть не может, так как C_9 — настоящие, а A_9 может быть только тяжелее или равна. Этот исход говорит об ошибке в логике или действиях.
Если после второго взвешивания мы выяснили, что фальшивая монета не в 9-ках, значит она в группах по 3 или 1. Мы проводим Взвешивание 3, переставляя "мешочки" A_3, B_3, C_3 и так далее.
Сравнение с методом Дайсона
Вы абсолютно правы, что метод Верта может быть обобщен. Однако, посмотрите, что происходит на самом деле:
Скрытая матрица: Каждая монета принадлежит определенному "мешочку" (A_9, B_3 и т.д.). Ее участие в каждом взвешивании (быть на левой чаше, правой или в стороне) предопределено этими перестановками групп.
Троичная система: Разбиение на 1, 3, 9 — это и есть представление числа в троичной системе. По сути, "мешочек", в котором лежит монета, — это ее "адрес" в троичной системе.
Фактически, метод Верта с "мешочками" — это процедурное, алгоритмическое выполнение ровно тех же действий, которые закодированы в матрице Дайсона!
Это просто два разных языка для описания одного и того же математического принципа.
Дайсон говорит: "Вот таблица. Монета №18 имеет код (-1, 0, +1, +1). Следуйте ему".
Верт говорит: "Монета №18 лежит в мешочке B_9. На первом шаге вся группа B идет направо. На втором шаге мешочек B_9 уходит в сторону..." и так далее.
Итоговый результат будет идентичным.
Вывод: Да, ваше описание совершенно точно передает суть обобщенного метода Верта. Это очень красивый и наглядный способ понять структуру решения задачи. Для практического применения с 39 монетами он все еще требует большой концентрации, чтобы не запутаться в перестановках, в то время как метод Дайсона с готовой таблицей просто требует аккуратного следования инструкции. Но с точки зрения понимания "магии" процесса, ваш подход — один из лучших.
========================================================
важно было самому найти Верта (у Богомольного), и спросить правильно. Ссылку на Богомольного машина давала ранее (неточную, но это как раз неважно). Особенность этой модели в ясности стиля! Она хороший рассказчик, лучше чем ... человек. опана! приехали. Считает модель не всегда хорошо, но как рассказывает! Этому можно у нее поучиться. Да и не только этому.
=================
ps. Случайно наткнулся на "научника", который "доказал" (нечто важное) но который пишет так... (естественно, ну раз доказал, зачем еще и писать хорошо), что его не понимают люди...(признак глупости - посмотри как человек говорит и поймешь кто он) - но... его ведь машины совсем не поймут - пусть поучится у них излагать как следует! а не доказывать то, что машины докажут (или опровергнут) и без его участия.
Комментариев нет:
Отправить комментарий