Інваріанти

Блок 1

Инвариант от латинского invarians, в родительном падеже invariantis – неизменяющийся. Был введён английским математиком Джеймсом Джозефом Сильвестром (03/11/1814 – 15/3/1897) в 1851 году.

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

Сформулируем наиболее важные утверждения, на которых основано применение этой идеи:

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

1. На доске записано 15 чисел: 8 нулей и 7 единиц. Вам предлагается 14 раз подряд выполнить такую операцию: зачеркнуть любые два числа и если они одинаковые, то допишите к оставшимся числам нуль, а если разные, то единицу. Какое число останется на доске?

РЕШЕНИЕ:

Сумма 15 исходных чисел равна 7. 7 – число – нечетное. Рассмотрим, какая сумма чисел будет получаться после выполнения операции. Если вычеркнем 2 нуля, то после дописывания нуля на доске будет 7 нулей и 7 единиц. Сумма этих 14 чисел будет нечетная. Если вычеркнем 2 единицы, то на доске останется после дописывания нуля 9 нулей и 5 единиц. Сумма данных 14 чисел будет нечетной. Наконец, вычеркивая нуль и единицу и приписывая единицу, мы получим на доске 7 нулей и 7 единиц, сумма которых снова является нечетным числом.

Что является инвариантом в данном случае?

Таким образом, мы замечаем, что после выполнения данной операции получается на 1 число на доске меньше, причём сумма оставшихся чисел всё время остаётся нечётной. Так как 1 – нечётное число, а 0 – чётное, то на доске после выполнения 14 раз указанной операции получается нечётное число 1.

2. На плоскости расположено 13 шестеренок, соединенных по цепочке. Могут ли все шестеренки вращаться одновременно? А если шестеренок 14?

РЕШЕНИЕ: Пусть первая шестеренка вращается по часовой стрелке, тогда вторая – против часовой стрелки, третья – по часовой стрелке и т. д. Получим, что двенадцатая будет вращаться против часовой стрелки, а тринадцатая – по часовой стрелке.

Что является инвариантом в данном случае?

Значит, первая должна вращаться против часовой, что противоречит тому, что она вращается по часовой стрелке. Поэтому, все 13 шестеренок вращаться одновременно не могут. А вот 14 уже могут.

ВЫВОД: Часто при решении подобного рода задач важно найти чередующиеся объекты.

1. Все костяшки домино выложены в цепь. На одном конце цепи оказалось 3 очка. Сколько на другом конце?

РЕШЕНИЕ: рассмотрим костяшки домино их 28:

Заметим, что “0” – 8 штук, “1” – 8 штук и т.д., то есть чётное число, а значит, каждому числу соответствует парное ему число.

Что является инвариантом в данном случае? (парность)

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

P.S:

Всего костяшек с тройкой на конце 7:

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

Костяшка 3-3 имеет “тройку” на обоих концах. Без нее остается 6 костяшек. Так как при игре в домино в цепи они должны располагаться парами, то на другом конце цепи будет 3 очка.

ВЫВОД. При решении аналогичных задач полезно иногда объекты разбивать на пары.

4. Можно ли разменять купюру достоинством 50 рублей с помощью 15 монет достоинством 1 и 5 рублей?

РЕШЕНИЕ.

Заметим, что:

15 – нечётное число,

50 – чётное,

1 и 5 – нечётные слагаемые

Так как сумма 15 нечетных чисел является числом нечетным, а 50 – число четное, то разменять 50 рублей на 15 монет по 1 и 5 рублей нельзя.

1. Квадрат 5×5 заполнен числами так, что произведение чисел в
   каждой строке отрицательно. Доказать, что найдется столбец, в котором произведение чисел отрицательно.

РЕШЕНИЕ: найдём произведение всех чисел в квадрате:

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

ВЫВОД: В задаче использовалась идея – нахождение произведения чисел.

Для самостоятельной работы

1. Можно ли доску размером 5×5 заполнить доминошками размером 1×2?

РЕШЕНИЕ. Нет, так как общее число клеток – 25 не делится на 2.

2. 16 корзин расположили по кругу. Можно ли в них расположить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?

РЕШЕНИЕ. Если число арбузов в соседних корзинах отличается на 1, то характер четности числа арбузов в этих корзинах будет разным.

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

Так как четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых, то общее число арбузов в 8 корзинах с четным числом арбузов и в 8 корзинах с нечетным числом арбузов будет четным. По условию же всего арбузов – 55, а это нечетное число. Значит, разложить нельзя.

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

3. Сумма 2002 натуральных чисел – число нечетное. Каким числом: четным или нечетным является произведение этих чисел?

РЕШЕНИЕ:

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

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

4. Учитель написал на листке бумаги число 10. 25 учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу – как хочет. Может ли в результате получиться число 0?

РЕШЕНИЕ. От прибавления или вычитания единицы меняется характер четности числа.

Поэтому, если 25 раз (нечётное число) менять характер четности числа 10, то в результате получится нечетное число. Следовательно, число 0 получиться не может.

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

5. В вершинах куба записаны числа 2, 0, 0, 3, 1, 9, 5, 7. За один ход разрешается прибавить к числам, стоящим на концах одного ребра, одно и то же целое число. Можно ли за несколько ходов получить нули во всех вершинах?

РЕШЕНИЕ. Так как сумма данных чисел: число 27 – нечетное, а при прибавлении двух одинаковых целых чисел четность суммы не меняется.

Т.о. получить все нули во всех вершинах не получится (сумма восьми нулей – число четное).

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

III. Для домашней работы.

1. Квадратная доска 6×6 заполнена костяшками домино 1×2. Докажите, что можно провести вертикальный и горизонтальный разрез этой доски, не пересекающий ни одной из костяшек домино.
2. На доске написано несколько нулей, единиц и двоек. Разрешается стереть две неравные цифры и вместо них написать одну цифру, отличную от двух стертых (2 вместо 0 и 1, 1 вместо 0 и 2, 0 вместо 1 и 2. Докажите, что если в результате таких операций на доске останется одна – единственная цифра, то она не зависит от порядка, в котором производились стирания.
3. Числа 0, 1, 2,…,9 записаны по кругу. За один ход разрешается прибавить к двум соседним числам одно и то же целое число. Можно ли за несколько ходов получить десять нулей?

Блок 2

Повторение ранее изученного:

Инвариантом некоторого преобразования называется величина или свойство, не изменяющееся при этом преобразовании.

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

Сформулируем наиболее важные утверждения, на которых основано применение этой идеи:

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

Задачи для работы в классе

Выделение части объекта.

Основная идея такова: выделить в каждом объекте какую-то часть, в которой изменения, вызываемые разрешенными операциями, выглядят особенно просто.

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

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

1) 2)

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

3) 4)

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

Характер чётности числа чёрных клеток среди четырёх угловых не меняется при перекрашиваниях.

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

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

2. В таблице 4*4 знаки “+” и “-” расставлены так, как показано на рисунке.

Разрешается изменить знак на противоположный одновременно во всех клетках, расположенных в одной строке, в одном столбце или вдоль прямой, параллельной какой-нибудь из диагоналей

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

Решение.

Заменим плюсы и минусы числами 1 и –1. В качестве инварианта можно взять произведение чисел, находящихся в клетках, которые заштрихованы на рисунке, поскольку оно в результате разрешенной операции все время сохраняет первоначальное значение равное –1.

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

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

Перестановки

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

Решение:

Обозначим кузнечиков А, В и С.

Назовём расстановки кузнечиков АВС, САВ и ВСА (слева направо) правильными, а ВАС, АСВ и СВА – неправильными.

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

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

Ответ: нет.

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

Доказательство:

Пусть а_1, а₂, а₃,……,а_п – произвольная перестановка из чисел 1, 2, 3,….,п. Будем говорить, что два числа образуют в этой перестановке инверсию, если большее из этих чисел предшествует меньшему.

Поменяв местами два соседних числа в перестановке, мы увеличим или уменьшим число инверсий на 1. Проделав же нечётное число таких операций, мы изменим, характер чётности числа инверсий, а значит, изменим и перестановку.

Ответ: нет.

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

Доказательство:

Присвоим автомобилям номера 1, 2, 3,……,24, 25 в том порядке, в каком они располагаются на старте. В центре автодрома установим световое табло, на котором после каждого обгона будем указывать номера автомобилей в том порядке, в каком они следуют. Тогда обгон, приводит к тому, что на световом табло меняются местами два соседних числа. И теперь наша задача становится похожей на предыдущую.

Запишем наши рассуждения в виде таблицы:

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

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

Раскраска

Обычно поиск нужной раскраски нацелен на доказательство отрицательного ответа.

6. Шахматный конь вышел с поля а1 и через несколько ходов вернулся на него. Докажите, что он сделал чётное число ходов.

Доказательство:

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

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

7. Можно ли покрыть шахматную доску костяшками домино 1*2 так, чтобы свободными остались только клетки а1 и н8?

Решение:

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

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

8. На доске 2008 х 2008 двое игроков по очереди красят клетки в чёрный цвет. Первый имеет право закрашивать по одной клетке, а второй – “уголок” из трёх клеток. Каждую клетку можно закрашивать один раз. Проигрывает тот, кто не может сделать хода. Кто выигрывает при правильной игре?

Решение

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

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

Ответ: выигрывает второй игрок.

9.Продолжение предыдущей задачи. Изменится ли ответ, если первый имеет право закрашивать квадрат 2 х 2?

Решение:

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

Ответ: не изменится, выигрывает второй игрок.

10. Пусть А – число, записанное с помощью 3¹⁹⁹⁸. Обозначим А₁₌ (А) сумму цифр числа А, А₂= (А₁), А₃= (А₂). Найдите А₄= (А₃).

Решение:

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

А =

А₁= (А) = 9+9+9+…+9 = 9 х 3¹⁹⁹⁸ = 9 х 9⁹⁹⁹ = 9¹⁰⁰⁰ < 10¹⁰⁰⁰.

Число 10¹⁰⁰⁰ записано при помощи 1001 цифры, т.о., полученное число А₁ записано с помощью менее, чем 1000 цифр.

Число А₂ = (А₁) делится на 9, а значит,

А₂ = (А₁) < 9*1000 = 9000 = 9*10³ < 10*10³ = 10⁴, так что А₂ записано не более, чем четырьмя цифрами.

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

Ответ: 9.

МАЛАЯ ОЛИМПИАДА

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

Решение

Снова заменим плюсы и минусы на +1 и –1.

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

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

2.Докажите, что шахматную доску 8 х 8 нельзя замостить 15 прямоугольными фигурками 1 х 4 и одной фигурой, указанной на рисунке. (Квадраты шахматной доски и фигурки одинаковы).

Доказательство

Используем раскраску доски чёрными и белыми, чередующимися по цвету строками. Чёрных и белых квадратов оказывается поровну – 32.

Как бы мы ни располагали данную на рисунке фигуру, она будет накрывать три квадрата одного цвета один другого. Прямоугольники 1 х 4 либо накрывают одинаковое количество чёрных и белых квадратов, либо – 4 квадрата только одного цвета. Так что всякий раз, накрывая ими из 32 – ух по два, то по четыре квадрата, никак не останется 1 или 3 свободных для указанной фигурки.

ЗАДАЧИ ДЛЯ ДОМАШНЕЙ РАБОТЫ

1.Может ли шахматный конь пройти с поля а1 на поле н8, побывав по дороге на каждом из остальных полей ровно один раз?

Решение

Поля а1 и н8 оба чёрные, а чёрных и белых полей на шахматной доске поровну – 32. При проходе цвета полей будут чередоваться, так что закончить обход на поле того же цвета нельзя.

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

2.На доске написано число 8^п. У него вычисляется сумма цифр, у полученного числа вновь вычисляется сумма цифр, и так далее, до тех пор, пока не получится однозначное число. Что это за число, если п =1989?

Решение

Вспомним доказательства признака делимости на 9 и заметим, что число и сумма его цифр дают одинаковый остаток при делении на 9. Какие же остатки при делении на 9 дают степени восьмёрки? Число 8¹ при делении на 9 даёт в остатке 8; 8² – 1; 8³ – 8, 8⁴ – 1; 8⁵ – 8 и т. д. Степени с чётным показателем дают в остатке 1, а степени с нечётным показателем дают в остатке 8. Значит, 8¹⁹⁸⁹ при делении на 9 даёт в остатке 8. Вернёмся к условию задачи. Описанные в условии последовательные вычисления всё время будут давать числа, которые при делении на 9 дают в остатке 8. Так что, когда получится однозначное число, то это и будет само число 8.

Ответ: 8.

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

Решение

Заменяя все плюсы нулями, а минусы – единицами, заметим, что сумма двух стираемых чисел имеет тот же характер чётности, что и число, записываемое вместо них. Так как сумма всех чисел была нечётной (13), то и последнее оставшееся число будет нечётным, т. е. единицей, и, значит, на доске останется минус.

4. Дно прямоугольной коробки было вымощено прямоугольными плитками 1 х 4 и 2 х 2. Плитки высыпали из коробки, и одна плитка 2 х 2 потерялась. Её заменили на плитку 1 х 4. Докажите, что теперь дно коробки вымостить не удастся.

Доказательство

Рассмотрим раскраску в четыре цвета, указанную на рисунке:

Тогда каждая плитка 2 х 2 содержит ровно одну клетку цвета1, а каждая плитка 1 х 4 – или ни одной или две клетки цвета 1. Следовательно, характер чётности числа плиток 2 х 2 должен совпадать с характером чётности числа клеток цвета 1. Но после замены плиток характер чётности числа плиток 2 х 2 изменится. Это и доказывает то, что замостить дно коробки не удастся.

Блок 3

(ОБОБЩАЮЩЕЕ ЗАНЯТИЕ ПО ТЕМЕ “ИНВАРИАНТЫ”)

Повторение ранее изученного

Инвариантом некоторого преобразования называется величина или свойство, не изменяющееся при этом преобразовании.

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

Сформулируем наиболее важные утверждения, на которых основано применение этой идеи:

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

Задачи для работы в классе

Чётность

№ 1 Разность двух целых чисел умножили на их произведение. Могло ли получиться число 45 045?

РЕШЕНИЕ:

Пусть 45 045 = (х – у)*х*у. Рассмотрим случаи:

1. х – чётное, у – чётное

(х – у) – чётное и ху – чётное, а произведение двух чётных чисел чётно, поскольку 45 045 число нечётное, то этот вариант невозможен.

1. х – нечётное, у – чётное или у – нечётное, х – чётное

(х – у) – нечётное и ху – чётное, а произведение нечётного и чётного чисел чётно, поскольку 45 045 число нечётное, то этот вариант невозможен.

1. х – нечётное, у – нечётное

(х – у) – чётное и ху – нечётное, а произведение нечётного и чётного чисел чётно, поскольку 45 045 число нечётное, то этот вариант невозможен.

ОТВЕТ: нет.

№ 2 В вершинах куба записаны числа 0, 0, 0, 0, 1, 0, 0, 0. За один ход разрешается прибавить к числам, стоящим на концах одного ребра, одно и то же целое число. Можно ли за несколько ходов получить нули во всех вершинах?

РЕШЕНИЕ. Так как сумма данных чисел: число 1 – нечетное, а при прибавлении двух одинаковых целых чисел четность суммы не меняется.

Т.о. получить все нули во всех вершинах не получится

(сумма восьми нулей – число четное).

ОТВЕТ: нет.

№ 3. Вдоль дороги растут 2002 ели. Утром на каждой из них сидело по одной вороне. В полдень каждая ворона взлетела и перелетела на дерево, растущее через одно от того, с которого она взлетела. Могло ли так получиться, чтобы на каждой ели вновь сидело по одной вороне?

РЕШЕНИЕ:

С чего начать? А если так: Занумеруем ели по порядку с 1 по 2002. Заметим, что вороны, сидевшие на елях с нечетными номерами, перелетают на ели с нечетными номерами. Соответственно вороны, сидевшие на елях с четными номерами, перелетят на ели с четными номерами. Рассмотрим ели с нечетными номерами: покрасим их в два цвета:Белый цвет: 1,5,9…2001. Таких елей 501. Черный цвет: 3,7,11…1999. Таких елей 500. Ели вдоль дороги: 1, 2, 3, 4, 5, 6, 7, …………………………….,2002. Заметим, что ворона с “белой” ели, перелетит на “черную”, и наоборот. Однако черных елей 500, а белых – 501. Значит, по крайней мере, на одну из белых елей не сядет ни одной вороны.

ОТВЕТ: не могло.

№ 4. На доске написано в строку 2003 числа. Доказать, что среди них можно стереть одно число так, что сумма оставшихся чисел будет четной. Верно ли это для 2002 чисел?

РЕШЕНИЕ: Очевидно, надо использовать следующее утверждение: четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых. Например: 1+2+3=6
1+2+3+5=11
Для числа 2003 (нечет.) рассмотрим три случая:

1случай:

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

2случай:

пусть все 2003 числа нечетные. Стираем любое из них.
3случай:

пусть 2003 числа четное. Стираем любое из них.
Для числа 2002.
Если они все нечетные, то после стирания одного из них сумма останется нечетной. Остальные случаи рассматривать нет смысла. Поэтому для 2002 целых числе это неверно. Ч.Т.Д.

Раскраска

Обычно поиск нужной раскраски нацелен на доказательство отрицательного ответа.

№ 5 Можно ли разрезать квадратный лист клетчатой бумаги (10х10 клеток) на четырёхклеточные фигуры вида (см. рис. 1)?

рис. 1

РЕШЕНИЕ: нельзя, так как если раскрасить клетки в шахматном порядке, то закрашенных клеток будет 50 и их нельзя распределить по фигурам заданного вида, поскольку таких фигур должно быть 25, а закрашенных клеток, каждая из них может содержать лишь нечётное количество.

ОТВЕТ: нельзя.

Чередование

Часто при решении подобного рода задач важно найти чередующиеся объекты.

№ 6 Можно ли обойти доску (рис. 2), начав с отмеченной клетки, побывав на каждой клетке только 1 раз. Переходить с клетки на клетку можно только через сторону клетки, а не через угол. Возвращаться на исходную клетку не обязательно.

Рис.2

РЕШЕНИЕ: Нетрудно подсчитать, что синих полей на доске меньше, чем белых. Если мы начнём обход с синего поля, то получим чередование полей с – б – с – б – … . В такой цепочке синих полей не меньше, чем белых, поэтому обойти все синие поля таким образом нельзя.

ОТВЕТ: нельзя.

№ 7. На плоскости лежат три шайбы. Хоккеист бьет по одной из них, так, чтобы она прошла между двумя другими и остановилась в некоторой точке. Можно ли все шайбы вернуть на свои места после 2003 ударов?

РЕШЕНИЕ: Вернуть шайбы на свои места – это значит сохранить направление движения, например, от А до В. Пусть первоначальное положение шайб А-В-С.

Попробуем выполнить рисунки:

Заметим, что после чётного числа ударов ориентация “против часовой стрелки” не меняется, а после нечётного числа ударов ориентация “по часовой стрелки” меняется.
Инвариантом является сохранение четного числа ударов, так как при этом сохраняется исходное положение шайб. Значит, после 2003 ударов шайбы не удается вернуть на свои места.
ОТВЕТ: нет, нельзя.

Остатки от деления

Разделить с остатком целое число а на натуральное число b – значит найти такое целое число q (НЕПОЛНОЕ ЧАСТНОЕ) и такое неотрицательное число r (ОСТАТОК), что а = b х q + r и r < b.

Например: 179 = 12х14 + 11 означает, что 179 при делении на 12 даёт неполное частное 14 и остаток 11.

В общем виде: 4n – формула чисел, кратных 4. Вычитая из них по 1, получим числа вида 4n – 1 , при делении на 4, дающие в остатке 3. Поскольку 4n – 1 = 4(n – 1) + 3. Те же самые числа, при делении на 4, дающие в остатке 3, можно задать формулой 4n + 3, т.к. 4n + 1 = 4(n + 1) – 3.

№ 8 У старшего дракона с планеты Хемтам 19 голов. Отважный рыцарь придумал аппарат с помощью которого можно одним ударом отрубить ровно 12, 14, 21 или 340 голов, но после этого у дракона отрастают взамен соответственно 33, 1998, 0 или 4 головы. Если все головы отрублены, новые не вырастают. Сможет ли рыцарь победить дракона?

РЕШЕНИЕ: Победить дракона значит оставить его без голов.

Попробуем использовать в качестве инварианта остаток от деления. Пусть у дракона n-голов.

Рассмотрим числа 21, 1974, 336. Они делятся без остатка на 3. Значит, остаток от деления на 3 числа голов останется постоянным и будет зависеть от числа n. Остаток от деления числа 19 на 3 равен 1, то число голов у дракона не может стать равным 0.
ОТВЕТ: не сможет.

МАЛАЯ ОЛИМПИАДА

№ 1 Можно ли разбить на “доминошки” (каждая состоит из двух клеток) шахматную доску без противоположных углов а1 и h8?

РЕШЕНИЕ: нельзя, так как каждая “доминошка” покрывает одну белую и одну чёрную клетки. Поэтому среди покрытых “доминошками” клеток белых и чёрных должно быть поровну. На шахматной доске 8х8 с вырезанными левой нижней и правой верхней угловыми клетками это не так: клеток одного цвета на 2 больше, чем другого.

ОТВЕТ: нельзя.

№ 2 В ряд выписаны числа от 1 до 10. Можно ли расставить между числами знаки “+” и “-” так, чтобы значение полученного выражения было равно нулю? (ПОДСКАЗКА: отрицательные числа тоже бывают чётными и нечётными).

РЕШЕНИЕ: нельзя, так как среди указанных чисел находится 5 – чётных и 5 – нечётных чисел. Сумма “Ч” и “Н” – число нечётное, а 0 – число чётное.

ОТВЕТ: нельзя.

№ 3. На доске написано в строку 1993 числа. Доказать, что среди них можно стереть одно число так, что сумма оставшихся чисел будет четной. Верно ли это для 1992 целых чисел?

РЕШЕНИЕ: Очевидно, надо использовать следующее утверждение: четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.
Например: 1+2+3=6, 1+2+3+5=11
Для числа 1993 (нечет.) рассмотрим три случая:

1случай: среди 1993 целых чисел есть четные и нечетные. Если количество нечетных чисел нечетно, то стираем любое из них. Если количество нечетных четно, то из 1993 целых чисел есть хотя бы одно четное. Его и стираем.
2случай: пусть все 1993 числа нечетные. Стираем любое из них.
3случай: пусть 1993 числа четные. Стираем любое из них.
Для числа 1992.
Если они все нечетные, то после стирания одного из них сумма останется нечетной. Остальные случаи рассматривать нет смысла. Поэтому для 1992 целых числе это неверно. Ч.Т.Д

ЗАДАЧИ ДЛЯ ДОМАШНЕЙ РАБОТЫ

№ 1. Докажите, что доску размером 50х50 нельзя разрезать на четырёхклеточные фигуры в форме буквы “Т” (см. рис. 1).

рис. 1

№ 2. По кругу зацеплены 9 шестерёнок: первая со второй, вторая с третьей, …, девятая с первой. Могут ли они вращаться?

РЕШЕНИЕ: Пусть первая шестеренка вращается по часовой стрелке, тогда вторая – против часовой стрелки, третья – по часовой стрелке и т. д. Получим, что девятая будет вращаться по часовой стрелке, как и первая, а значит, вращаться они не могут.

ОТВЕТ: нет

№ 3. В вершинах куба записаны числа 1, 2, 3, 4, 5, 6, 0. За один ход разрешается прибавить к числам, стоящим на концах одного ребра, прибавить по 1. Можно ли за несколько ходов получить во всех вершинах одно и тоже чётное число?

РЕШЕНИЕ. Так как сумма данных чисел: число 21 – нечетное, а при прибавлении двух одинаковых целых чисел, равных 1, четность суммы не меняется: Н + Ч = Н

Т.о. получить все чётные числа во всех вершинах не получится

(сумма восьми чётных чисел – число четное).

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

№ 4 (остатки от деления)
Хулиганы Вася и Петя порвали школьную стенгазету, в которой была заметка об их плохой учебе. Причем Вася рвал каждый кусок на 5 частей, а Петя на 9. Заместитель директора школы, заметив такое безобразие, потребовала собрать обрывки стенгазеты. Ребята нашли 1999 обрывков.
Все ли обрывки были найдены?

РЕШЕНИЕ:

Если речь идет о делении на части, то рассмотрим остатки от деления. Пусть газету рвёт Вася (на 5 кусков) и Петя (на 9 кусков): Вася

1 шаг порвал на 5 кусков:

2 шаг 1 кусок порвал ещё на 5 кусков

получилось 9 кусков.

Теперь Вася будет дальше рвать некоторые куски на 5, а Петя будет рвать газету на 9 кусков, то число кусков получится:

Так как 1999=499х4 + 3, то ученики собрали не все обрывки стенгазеты. ОТВЕТ: нет, не все.