Красивая задачка и полезный приём решения
Евгений Пескин (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 разные, поэтому переход невозможен.
По Болотной площади бродят три вида нерешительных хомячков - либеральные прислужники Госдепа, леваки и русские националисты. Когда два хомячка с разными взглядами встречаются, они начинают бесплодно спорить, быстро разочаровываются в собственных убеждениях и убеждениях оппонента и одновременно меняют свои политические взгляды на третий оставшийся вариант (например, после разговора прислужник Госдепа и левак становятся русскими националистами). В начальный момент времени на площади было 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 разные, поэтому переход невозможен.