Распечатать запись Распечатать запись

Инвариант

Такие задачи довольно часто встречаются на олимпиадах. Если не знать принцип их решения, то решить их довольно трудно. А надо всего лишь искать то, что не меняется при описанных преобразованиях.

Сначала рассмотрим классическую задачку на инвариант.

Задача 1. На столе стоят вверх дном семь стаканов. Разрешается переворачивать одновременно любые два стакана (разумеется, можно перевернуть любой стакан, стоящий вверх дном, так, чтобы он стоял на дне, а можно перевернуть любой стоящий правильно стакан так, чтобы он стал стоять вверх дном). Можно ли добиться того, чтобы все семь стаканов на столе стояли на дне?

Конечно же, сначала нужно попробовать попереворачивать стаканы. Однако довольно быстро становится понятно, что так просто эта задачка не решается. Тогда возникает желание доказать, что добиться требуемой расстановки стаканов невозможно. Как это сделать? Давайте сравним количества стаканов, стоящих на дне и вверх дном. Сначала мы имеем 7 стаканов, которые стоят вверх дном и 0 стаканов, стоящих на дне. Мы можем перевернуть любые два стакана. Какие бы стаканы мы ни выбрали, у нас будет 5 стаканов вверх дном и 2 стакана, стоящих правильно. В следующий раз мы можем перевернуть стаканы различными способами. Так, мы можем поставить на дно два стакана, стоящих вверх дном. Тогда у нас останется 3 стакана, стоящих вверх дном, а 4 стакана будут стоять правильно. Мы можем перевернуть один стакан, стоящий вверх дном, и один стакан, стоящий правильно. Тогда ничего не изменится, и у нас останется 5 стаканов, стоящих вверх дном, и 2 стакана, стоящих на дне. И последний вариант: мы можем перевернуть два стакана, которые стоят на дне. Тогда получим исходную ситуацию, а именно 7 стаканов вверх дном и 0 стаканов, стоящих правильно.

Давайте посмотрим, что общего во всех этих ситуациях. Найдем разность числа стаканов, стоящих вверх дном, и числа стаканов, стоящих на дне. В исходном варианте эта разность равна семи. После первого переворачивания она становится равна трем. А дальше, в зависимости от выбранного варианта переворачивания стаканов, она станет равной -1, 3 или 7. Мы видим, что эта разность может измениться только на 4. И в данном случае неважно, что исходно мы рассматривали 7 стаканов, которые были перевернуты вверх дном. Если вы рассмотрите случай, когда a стаканов стоят на дне, а b стаканов — вверх дном, вы придете к тому же самому выводу. В качестве полезного и простого упражнения попробуйте сделать это сами. Предположим, что нам удалось, переворачивая стаканы, добиться их правильного расположения. Тогда в конечной ситуации разность между числом стаканов, стоящих вверх дном, и числом стаканов, стоящих правильно, равна -7. И мы видим, что число -7 отличается от 7 на 14 — это число не кратно 4. Следовательно, действуя описанным в условии задачи способом, добиться того, что все 7 стаканов будут стоять на дне, невозможно.

А теперь вернемся к непонятному слову инвариант. Оно имеет очень простое значение: то, что сохраняется, не изменяется при некоторых преобразованиях.

В рассмотренной задаче инвариантом был остаток от деления на 4 разности числа стаканов, стоящих вверх дном, и числа стаканов, стоящих на дне. Он должен всегда оставаться равным 3.

Приведу еще примеры задач, которые решаются с помощью инварианта.

Задача 2. Даны три числа: 2011,2012 и 2013. За один ход разрешается заменить числа a,b,c на числа ab/c,ac/b,bc/a. Можно ли через несколько ходов получить числа 2008,2012,2016?

Решение. Нетрудно заметить, что в данной задаче неизменным остается произведение чисел. Действительно,

\displaystyle\frac{ab}{c}\cdot\frac{ac}{b}\cdot\frac{bc}{a}=abc.

Поскольку 2011\cdot2012\cdot2013\ne2008\cdot2012\cdot2016, то получить вторую тройку чисел из первой невозможно.

Задача 3. На доске написаны 15 плюсов и 10 минусов. Разрешается стереть любые два знака и записать вместо них плюс, если они одинаковы, и минус, если они различны. Какой знак останется на доске после выполнения 24 таких операций?

Решение задачи становится очевидным, если каждый плюс заменить числом 1, а каждый минус — числом -1. Тогда описанная в условии операция будет следующей: вместо любой пары чисел записываем их произведение. Ясно, что произведение всех чисел, написанных на доске, не изменяется. Исходно оно равно 1. Значит, после выполнения 24 указанных операций на доске будет написано число 1.

Задача 4. Круг разделен на шесть секторов. В каждом секторе написано число. Разрешается одновременно увеличивать числа в двух соседних секторах на один. Можно ли сделать все числа равными, если в начале они такие: 1,0,1,0,0,0?

Решение. Раскрасим секторы, на которые разделен круг, в два цвета, например, черный и белый, так, чтобы черный и белый секторы чередовались. Инвариантом является разность сумм чисел в черных и белых секторах. В исходном варианте эта разность равна 2 (если секторы с числами 1 черные), а в том случае, когда все числа равны, эта разность равна нулю. Значит, сделать все числа равными нельзя.

А теперь несколько задач для самостоятельного решения ;) .

1. В алфавите языка племени АУ всего две буквы: А и У. В результате следующих замен сочетаний букв смысл любого слова не изменяется:

УАУ\leftrightarrowАА, УАА\leftrightarrowАУ, ААУ\leftrightarrowУА, ААА\leftrightarrowУУ

(замену можно делать в любом месте слова).

Являются ли в этом языке синонимами слова УАА и АУУ?

Показать решение

2. Вася разорвал листок бумаги на 10 частей, некоторые из получившихся кусков он снова разорвал на 10 частей и т.д. Мог ли он получить 2012 кусков бумаги?

Показать решение

3. Дана тройка чисел 2,\sqrt{2},\frac{1}{\sqrt{2}}. Разрешается любые два числа заменить на следующие два числа: их сумму, деленную на \sqrt{2}, и их разность, деленную на \sqrt{2}. Можно ли, проделав эту операцию несколько раз, получить тройку чисел

1,\sqrt{2},1-\sqrt{2}?

Показать решение

4. Каждое число от 1 до 1000000 заменили суммой его цифр. С полученным набором чисел проделали то же самое, и так до тех пор, пока не получилось 1000000 однозначных чисел. Каких чисел получилось больше: единиц или двоек?

Показать решение

5. На доске написано 25 букв А, 30 букв Б, 35 букв В. Разрешается стереть две разные буквы и написать третью. Такая операция проводится до тех пор, пока это возможно. Можно ли определить, какие две буквы были стерты последними?

Показать решение

Читайте также о полуинварианте.

Комментариев: 21

  1. 1 Корнеев В.Ф.:

    Почему инвариант считается неизвестным термином? Мне он известен, например, из аналитической геометрии.

    [Ответить]

    Елизавета Александровна Калинина Reply:

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

    [Ответить]

  2. 2 disputant:

    Пятый – это много :) У меня малой во втором классе решил задачку – можно ли накрыть доминошками (по 2 клетки) шахматную доску с вырезанными a1 и h8 – а ведь по сути тоже инвариант: разность непокрытых черных и белых клеток…

    [Ответить]

  3. 3 Елизавета Александровна Калинина:

    Он у вас молодец! :) На самом деле у меня большинство студентов об инварианте в школе точно не слышали, да и задач таких никогда не видели. К сожалению…

    [Ответить]

  4. 4 disputant:

    Ну, я об инварианте не рассказывал :)

    А задачка из старого-престарого “Кванта”…

    [Ответить]

  5. 5 MZ:

    Здравствуйте, Елизавета!
    Спасибо за сайт, у Вас много всякого интересного.

    Мне кажется, что во второй задаче (про Васю) неточность: инвариантом будет остаток от деления на 9, а не на 10.

    [Ответить]

  6. 6 Елизавета Александровна Калинина:

    2MZ: Спасибо, конечно же! Там при разрывании каждый раз прибавляется 9 кусков.

    [Ответить]

  7. 7 Аноним:

    >Пятый – это много :) У меня малой во втором классе решил задачку – можно ли накрыть доминошками (по 2 клетки) шахматную доску с вырезанными a1 и h8 – а ведь по сути тоже инвариант: разность непокрытых черных и белых клеток…

    Существуют ли случаи, когда нельзя покрыть шахматную доску доминошками, в которой вырезаны 2 белых и 2 чёрных поля? Воспользуйтесь инвариантом ;)

    Елизавета, правильно ли я понимаю, что существуют такие задачи, у которых есть инвариант, но нет решения?

    [Ответить]

  8. 8 Елизавета Александровна Калинина:

    Что значит, что есть инвариант, но нет решения? То, что найденный инвариант не помогает решить задачу? Конечно,так бывает, и Ваш пример с доминошками об этом говорит. Но почему бы не существовать другому инварианту, который не так очевиден, и с помощью которого решение может быть все-таки получено? :)

    [Ответить]

  9. 9 Аноним:

    >Что значит, что есть инвариант, но нет решения? То, что найденный инвариант не помогает решить задачу?

    Есть преобразование 1 ->2, по неким правилам, есть инвариант I для 1 и 2.
    Если, I1=I2, всегда ли возможно преобразование? (судя по шахматной доске, не всегда)
    Если I1 != I2, всегда ли преобразование невозможно?

    >Но почему бы не существовать другому инварианту, который не так очевиден, и с помощью которого решение может быть все-таки получено?

    И как доказать, что данный вид инварианта приводит/не приводит к решению?

    [Ответить]

  10. 10 disputant:

    Инвариант – это для опровержения :)

    Если есть инвариант, сохраняющийся при некотором преобразовании, и инвариант в начальном и конечном состоянии не совпадает – значит, переход невозможен. Но если он сохраняется – это совершенно не значит, что переход возможен!

    Очень отдаленная аналогия: все кошки хвостаты. Отсюда следует, что если бесхвостое – это не кошка, но если хвостатое – это еще не значит, что это кошка… :)

    [Ответить]

  11. 11 Аноним:

    >Очень отдаленная аналогия: все кошки хвостаты. Отсюда следует, что если бесхвостое – это не кошка, но если хвостатое – это еще не значит, что это кошка…

    А почему в этой аналогии не может быть неисследованных бесхвостых кошек? Ведь если суслика не видно, это не значит, что его нет. Не может ли с инвариантом, к примеру, случится то же самое, как с 8 членом забавной интересной последовательности?

    [Ответить]

  12. 12 disputant:

    Потому что тогда неверна сама посылка “все кошки хвостаты”.

    Не может, если инвариант сформулирован правильно. Вы же не думаете, что достаточно сказать “вот это …. – инвариант”?

    [Ответить]

  13. 13 Аноним:

    >Потому что тогда неверна сама посылка “все кошки хвостаты”.

    Дык, в логике средствами логики и нельзя доказать верность посылки. Только контрпримером.

    >Вы же не думаете, что достаточно сказать “вот это …. – инвариант”?

    В задачах выше так и говорится. :)

    [Ответить]

  14. 14 disputant:

    Для простоты доказательство инвариантности опущено.

    С шахматной доской оно практически очевидно – на шахматной доске любые две соседние клетки (не по диагонали) разного цвета, так что покрытие доминошкой захватывает одну черную и одну белую, а значит, разность числа непокрытых черных и непокрытых белых при накрытии доминошкой двух клеток не изменяется.

    Теперь это не просто слова?

    [Ответить]

  15. 15 Аноним:

    >С шахматной доской оно практически очевидно

    Я не догадался, правда доску в уме представлял. Но дело в другом: решение оставляет ощущение какой-то неполноты, так как оно частное и является результатом случайной догадки, а не следствием общего метода решения такого рода задач. И опять-таки, с шахматной доской может и очевидно, но как доказать, что в других задачах у инварианта не может быть “излом”, то есть изменение только при некоторых преобразованиях?

    [Ответить]

  16. 16 disputant:

    Да панацеи ведь и не существует :)

    Иначе б математиков давно заменили компьютером :)

    [Ответить]

  17. 17 Аноним:

    А при чём тут панацея? Просто метод-инструмент, без его получения, годящийся для решения специальным образом отобранных задач – это как-то несерьёзно. :) Как и угадывание частных случаев.

    [Ответить]

  18. 18 disputant:

    Ну, тогда ограничьтесь умножением в столбик – там все строго.

    Я со своей стороны дискуссию заканчиваю.

    [Ответить]

  19. 19 Полуинвариант | Математика, которая мне нравится:

    [...] с задачами на инвариант, на олимпиадах довольно часто встречаются и задачи на [...]

Оставьте свой отзыв

Добавить изображение

Подписаться, не комментируя