Инварианты и их применение при решении задач

введён английским математиком Джеймсом Джозефом Сильвестром ( 03/11/1814 – 15/3/1897) в 1851 году.

Инвариантом некоторого преобразования называется величина или свойство, не изменяющееся при этом преобразовании.
Виды инвариантов:
четность (нечетность);
остаток от деления;
перестановки;
раскладки;
раскраски;
чередование и т. п

произведения нескольких целых чисел совпадает с четностью количества нечетных множителей;

знак произведения нескольких (отличных от нуля) чисел определяется четностью количества отрицательных сомножителей.

+

–

+

+

+

–

–

–

+

на

=

на

на

=

=

перекрашиваниях.

1чёрная и 3 белые

1чёрная и 3 белые

3 чёрные и 1 белая

3 чёрные и 1 белая

№ 1 В таблице 3*3 угловая клетка закрашена чёрным цветом, все остальные – белым. Докажите, что с помощью перекрашивания строк и столбцов нельзя добиться того, чтобы все клетки стали белыми. Под перекрашиванием строки или столбца понимается изменение цвета всех клеток в строке или столбце.

Ответ: невозможно

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

среди заштрихованных чисел всегда будет оставаться –1

Ответ: нельзя

САВ и ВСА (слева направо) правильными, а ВАС, АСВ и СВА – неправильными.

№3. Три кузнечика играют на прямой в чехарду. Каждый раз один из них прыгает через другого (но не через двух сразу!). Могут ли они после 1991 прыжка оказаться на прежних местах?

При любом прыжке тип расстановки меняется.

если исходная расстановка была правильная, то после 1991 прыжка расстановка будет неправильная, так как 1991 – число нечётное, и кузнечики не смогут оказаться на прежних местах.

Ответ: нет.

местами любые два рядом стоящих числа. Докажите, что если проделать нечётное число таких операций, то наверняка получится отличное от первоначального расположение чисел 1, 2, 3,…,п.

что два числа образуют в этой перестановке инверсию, если большее из этих чисел предшествует меньшему.

Ответ: нет.

время в одном направлении стартовали 25 автомобилей. По правилам гонки автомобили могут обгонять друг друга, но при этом запрещён двойной обгон. Автомобили финишировали одновременно в тех же пунктах, что и стартовали. Докажите, что во время гонки было чётное число обгонов.

Присвоим автомобилям номера 1, 2, 3,……,24, 25 в том порядке, в каком они располагаются на старте

Ответ: чётное число обгонов.

ходов вернулся на него. Докажите, что он сделал чётное число ходов.

Например, чтобы попасть с чёрного поля снова на чёрное, надо сделать как минимум два хода. Так что для того, чтобы вернуться на исходное поле, надо сделать чётное число ходов.

Шахматный конь ходит с чёрного поля на белое и наоборот.

чтобы свободными остались только клетки а1 и h8?

Решение:
Каждая костяшка домино покрывает два поля: чёрное и белое. Чёрных и белых полей поровну, так что покрывать так, чтобы остались свободными два чёрных поля, нельзя.

Ответ: нельзя.

красят клетки в чёрный цвет. Первый имеет право закрашивать по одной клетке, а второй - «уголок» из трёх клеток. Каждую клетку можно закрашивать один раз. Проигрывает тот, кто не может сделать хода. Кто выигрывает при правильной игре?

Выигрышная стратегия для второго игрока: мысленно разбив квадрат 2008 × 2008 на квадратики 2 х 2, второй игрок, после того как первый закрасит одну клетку в одном из квадратов 2 х 2, «докрашивает» его.

В силу того, что произведение 2008 × 2008 делится на 4 = 2×2, то очевидно, что тогда последний ход всегда останется за вторым игроком.

закрашивать квадрат 2 х 2?

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

сумму цифр числа А, А2=Σ (А1), А3=Σ(А2). Найдите А4=Σ(А3).

Решение:
Число А составлено из одних девяток, следовательно, оно делится на 9. При суммировании цифр числа это свойство сохраняется, т. е. является инвариантом преобразования Σ(х).
А = 999999999……..9

31998
А1=Σ(А) = 9+9+9+…+9 = 9 х 31998 = 9 х 9999 = 91000 < 101000.
Число 101000 записано при помощи 1001 цифры, т.о., полученное число А1 записано с помощью менее, чем 1000 цифр.
Число А2 = Σ(А1) делится на 9, а значит,
А2 = Σ(А1) < 9*1000 = 9000 = 9*103 < 10*103 = 104, так что А2 записано не более, чем четырьмя цифрами.

А3=Σ(А2) < 9 *4 = 36 и делится на 9, т.е. А3 может принимать только значения 9, 18, 27. Во всех этих случаях Σ(А3) = 9.
Ответ: 9.

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

Решение
Снова заменим плюсы и минусы на +1 и –1.
Инвариантом будет произведение чисел, стоящих в чёрных клетках. И раз оно равно числу –1, то нельзя получить таблицу, не содержащую ни одного минуса.
Ответ: нельзя.