Инварианты в олимпиадных задачах по математике

Кружок олимпиадной математике в 6-7 классе

Тема: Инварианты

Занятие 1.

Учитель: Гранкина Наталья Юрьевна

Школа: ГАОУ ТО “ФМШ”, г. Тюмень

Инвариант - это некоторая характеристика объекта/процесса, которая остается неизменной в результате изменений.

С помощью инварианта можно показать невозможность достижения некоторого состояния объекта.

Задача 1

На доске написаны шесть чисел:

1, 2, 3, 4, 5, 6.

За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными?

Задача 1

На доске написаны шесть чисел:

1, 2, 3, 4, 5, 6.

За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными?

Подсказка

Рассмотрите сумму чисел на доске, какая она сначала? как изменяется? Какая должна получиться в конце?

Задача 1

На доске написаны шесть чисел:

1, 2, 3, 4, 5, 6.

За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными?

Решение

Сумма написанных чисел нечётна (она равна 21). За каждый ход эта сумма увеличивается на 2, т.е. всегда остаётся нечётной.

А сумма шести равных чисел всегда чётна. Это значит, что сделать числа равными невозможно.

Задача 1

На доске написаны шесть чисел:

1, 2, 3, 4, 5, 6.

За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными?

Что являлось инвариантом?

Нечетность суммы написанных на доске чисел

Задача 2

100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну фишку. Можно ли с помощью таких операций переставить все фишки в обратном порядке?

Задача 2

100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну фишку. Можно ли с помощью таких операций переставить все фишки в обратном порядке?

Подсказка

Какие фишки могут меняться местами? С какими номерами? Используйте раскраску, если нужно

Задача 2

100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну фишку. Можно ли с помощью таких операций переставить все фишки в обратном порядке?

Решение

Занумеруем места, на которых стоят фишки, числами от 1 до 100. Заметим, что после выполнения данной в условии операции номер каждой фишки либо не изменился, либо изменился (увеличился или уменьшился) на 2.

Таким образом, фишка, стоящая вначале на месте с четным номером, в любой момент остается стоять на месте с четным номером.

Следовательно, фишка, стоящая на месте номером 100 никогда не сможет попасть на клетку с номером 1.

Задача 2

100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну фишку. Можно ли с помощью таких операций переставить все фишки в обратном порядке?

Что являлось инвариантом?

Четность номера конкретной фишки.

Задача 3

Лягушка прыгает вдоль прямой. Сначала она прыгнула на 1 см, затем на 3 см в том же или в противоположном направлении, затем на 5 см в том же или в другом направлении и т. д. Могло ли случиться так, что она оказалась в исходной точке после 57-го своего прыжка?

Задача 3

Лягушка прыгает вдоль прямой. Сначала она прыгнула на 1 см, затем на 3 см в том же или в противоположном направлении, затем на 5 см в том же или в другом направлении и т. д. Могло ли случиться так, что она оказалась в исходной точке после 57-го своего прыжка?

Подсказка

Как изменяется расстояние от лягушки до исходной точки?

Задача 3

Лягушка прыгает вдоль прямой. Сначала она прыгнула на 1 см, затем на 3 см в том же или в противоположном направлении, затем на 5 см в том же или в другом направлении и т. д. Могло ли случиться так, что она оказалась в исходной точке после 57-го своего прыжка?

Решение

После каждого прыжка четность расстояния (в сантиметрах) между исходной точкой и той, где находится лягушка, меняется. Значит, после 57-го прыжка лягушка будет на нечетном расстоянии от исходной точки и не сможет в ней оказаться.

Задача 3

Лягушка прыгает вдоль прямой. Сначала она прыгнула на 1 см, затем на 3 см в том же или в противоположном направлении, затем на 5 см в том же или в другом направлении и т. д. Могло ли случиться так, что она оказалась в исходной точке после 57-го своего прыжка?

Что являлось инвариантом?

Чередование четности расстояния от лягушки до исходной точки.

Задача 4

Миша написал на доске в некотором порядке 2016 плюса и 2017 минусов. Время от времени Юра подходит к доске, стирает любые два знака и пишет вместо них один, причем если он стер одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой?

Задача 4

Миша написал на доске в некотором порядке 2016 плюса и 2017 минусов. Время от времени Юра подходит к доске, стирает любые два знака и пишет вместо них один, причем если он стер одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой?

Подсказка

Как изменяется количество минусов на доске?

Задача 4

Миша написал на доске в некотором порядке 2016 плюса и 2017 минусов. Время от времени Юра подходит к доске, стирает любые два знака и пишет вместо них один, причем если он стер одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой?

Решение

Заметим, что после каждого действия Юры четность количества минусов не меняется, поэтому количество минусов не может сравняться с нулем. Значит, последним знаком мог оказаться только минус.

Задача 4

Миша написал на доске в некотором порядке 2016 плюса и 2017 минусов. Время от времени Юра подходит к доске, стирает любые два знака и пишет вместо них один, причем если он стер одинаковые знаки, то вместо них он пишет плюс, а если разные, то минус. После нескольких таких действий на доске остался только один знак. Какой?

Что являлось инвариантом?

Нечетность количества минусов

Задача 5

Дядька Черномор написал на листке бумаги число 20. Тридцать три богатыря передают листок друг другу, и каждый или прибавляет к числу или отнимает от него единицу. Может ли в результате получиться число 10?

Задача 5

Дядька Черномор написал на листке бумаги число 20. Тридцать три богатыря передают листок друг другу, и каждый или прибавляет к числу или отнимает от него единицу. Может ли в результате получиться число 10?

Подсказка

Как изменяется четность написанного числа?

Задача 5

Дядька Черномор написал на листке бумаги число 20. Тридцать три богатыря передают листок друг другу, и каждый или прибавляет к числу или отнимает от него единицу. Может ли в результате получиться число 10?

Решение

Нет, не может. После того, как листок побывает в руках у богатыря, число, на нем написанное, будет менять свою четность, т.е. станет четным, если было нечетное, и наоборот. Это значит, что после 33-х изменений число станет нечетным, т.е. никак не сможет равняться 10.

Задача 5

Дядька Черномор написал на листке бумаги число 20. Тридцать три богатыря передают листок друг другу, и каждый или прибавляет к числу или отнимает от него единицу. Может ли в результате получиться число 10?

Что являлось инвариантом?

Чередование четности полученного числа.