Александр Бугаев (a_bugaev) wrote,
Александр Бугаев
a_bugaev

Category:

Красивая задачка и полезный приём решения

Евгений Пескин (eugenegp) в фейсбуке перепостил задачку, которую шесть лет назад опубликовал Андрей Коняев. Дело было после первой болотной, текст обыгрывает тогдашние события (мне кажется, видно влияние Остера). Юмор на любителя, а вот задачка интересная.
По Болотной площади бродят три вида нерешительных хомячков - либеральные прислужники Госдепа, леваки и русские националисты. Когда два хомячка с разными взглядами встречаются, они начинают бесплодно спорить, быстро разочаровываются в собственных убеждениях и убеждениях оппонента и одновременно меняют свои политические взгляды на третий оставшийся вариант (например, после разговора прислужник Госдепа и левак становятся русскими националистами). В начальный момент времени на площади было 24 999 хомячков, из которых 12 996 были леваками, 6 001 - русскими националистами и 6 002 - прислужниками Госдепа. Fox News сообщает, что на площади вполне может сложиться ситуация, в которой все хомячки перейдут под влияние американского империализма. Уличите рупор Вашингтонского обкома во лжи.
https://lenta.ru/columns/2011/12/23/math/


Задачка не представляет трудности для любителей математики, тем более для участников математических олимпиад. Остальные могут попробовать решить самостоятельно.

Меня в ФБ попросили объяснить решение, я постарался сделать из объяснения иллюстрацию к общему принципу решения подобных задач при помощи инвариантов.


Есть класс задач, где дана некая система и правила возможных преобразований (действий, пр которых система переходит в другое состояние). Вопрос в том, можно ли при помощи таких преобразований перевести систему из исходного состояния в заданное конечное состояние.

Одним из мощных способов решения подобных задач является поиск подходящего инварианта - такого "свойства" системы, которое не изменяется при допустимых преобразованиях. Если в начальном и конечном состояниях это "свойство" различается, переход невозможен (обратное в общем случае неверно).

Например, на шахматной доске слон ходит по диагонали, поэтому при любом ходе слона цвет поля не меняется. Поэтому никакими ходами нельзя перевести слона с a1 на a8. Это в буквальном смысле очевидно, но вот если бы на доске не было раскраски, решение было бы не таким наглядным.

Другой пример. При перекладывании монет из левого кармана в правый и из правого в левый общая сумма денег не меняется. Это тоже очевидно.

Вернёмся к нашей задаче.
Тут система состоит из набора элементов трёх сортов. Обозначим количество леваков, прислужников и националистов буквами Л, П и Н соответственно. В начальном состоянии Л=12996, Н=6001, П=6002.

Возможные преобразования таковы.
При встрече левака с националистом они оба становятся прислужниками. Что при этом происходит с количествами? Л и Н уменьшаются на 1, а П увеличивается на 2.

Запишем этот переход символически: (Л, Н, П) -> (Л-1, Н-1, П+2)

Аналогично два других варианта.
Встреча националиста и прислужника (Л, Н, П) -> (Л+2, Н-1, П-1)

Встреча левака и прислужника (Л, Н, П) -> (Л-1, Н+2, П-1)

Это элементарные ходы, любое возможное преобразование состоит из последовательности таких ходов.

Присмотримся к этим ходам. Есть ли какое-то свойство, которое не меняется при любом элементарном ходе?

Очевидно, что все три числа меняются, но остаётся неизменной их сумма (Л+Н+П). Иными словами, значение выражения (Л+Н+П) - инвариант. В случае задачи с перекладыванием денег между карманами общая сумма была полезным инвариантом. Но в этой задаче такой инвариант вряд ли пригодится.

Может быть, что-то ещё остаётся неизменным?

Заметим, что в случае хода (Л, Н, П) -> (Л-1, Н-1, П+2)
разность (Н-Л) остаётся неизменной, разность (П-Л) увеличивается на 3, разность (П-Н) тоже увеличивается на 3.

Точно так же и в двух других случаях - попарная разница либо не меняется, либо изменяется на 3 (+3 или -3). А это значит, что остаток от деления разности на 3 не изменяется.

Остаток от деления X на 3 называется "остаток X по модулю 3" и записывается X mod 3.

Таким образом, мы установили, что при любых возможных ходах каждое из выражений
(Л-Н) mod 3
(Л-П) mod 3
(П-Н) mod 3
не изменяется.

В начальном состоянии Л=12996, Н=6001, П=6002.
(Л-Н) mod 3 = (6995 mod 3) = 2
(Л-П) mod 3 = (6994 mod 3) = 1
(П-Н) mod 3 = (1 mod 3) = 1

В конечном состоянии Л=0, Н=0, П=24999.
(Л-Н) mod 3 = (0 mod 3) = 0

Мы видим, что в начальном и конечном состоянии значения (Л-Н) mod 3 разные. Но ведь при любых возможных ходах значение (Л-Н) mod 3 не может измениться.

Из этого следует, что никакой последовательностью ходов нельзя перейти из начального в конечное состояние.

(можно было бы рассмотреть и другие пары, в конечном состоянии для каждой разности остаток по модулю 3 равен 0).

Кратко идея решения звучит так:
Для каждой из пар разность по модулю 3 - инвариант. В начальном и конечном состоянии остатки по модулю 3 разные, поэтому переход невозможен.
Tags: mathematics
Subscribe

  • расстрелы в Астрахани в марте 1919 года

    в ходе одного из разговоров вспомнил про эту тему, стал искать ссылки сохраню тут П. Силин. Астраханские расстрелы (из сборника С. В. Волкова…

  • Для библиофилов

    Вчера ссылался на 7 том МСЭ. С этой страницы можно скачать распознанный pdf. Там же можно и посмотреть его постранично (вот 237 страница, на…

  • К вопросу о равенстве полов

    Подробный обзор на тему особенностей службы женщин в израильской армии. Никакой идеологии, чистая прагматика и масса статистики. Автор - военный…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 7 comments