Задача 1:

В алфавите языка племени УЫУ всего две буквы: У и Ы, причем этот язык обладает такими свойствами: если из слова выкинуть стоящие рядом буквы УЫ, то смысл слова не изменится. Точно так же смысл слова не изменится при добавлении в любое место слова буквосочетания ЫУ или УУЫЫ. Можно ли утверждать, что слова УЫЫ и ЫУУ имеют одинаковый смысл?

Решение:

Обратите внимание, что при любой разрешенной нам операции добавления или выкидывания куска слова количества букв У и Ы в этом куске равны. Это означает, что разность между числом букв У и букв Ы в слове не изменяется. Проследите это на примере

Ы  →  ЫЫУ  →  ЫУУЫЫЫУ  →  ЫУЫЫУ

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

Задача 2:

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

Решение:

Занумеруем сектора по кругу числами от 1 до 6 и для любой расстановки фишек рассмотрим следующую величину S – сумму номеров секторов, в которых стоят данные нам 6 фишек (с учетом кратности).

Очевидно, что при сдвиге фишки в соседний сектор соответствующее ей слагаемое в сумме S меняет четность. Значит, если сдвигаются одновременно две фишки, то четность величины S не меняется – она инвариантна. Для начальной расстановки S = 21. Если же все фишки находятся в одном секторе с номером A, то S = 6A – это четное число (а 21 – число нечетное). Следовательно, из исходной расстановки нельзя получить расстановку, в которой все 6 фишек находятся в одном секторе.

Задача 3:

На доске написаны числа 1, 2, 3, …, 19, 20. Разрешается стереть любые два числа a и b и вместо них написать число a + b – 1. Какое число может остаться на доске после 19 таких операций?

Решение:

Для любого набора из n чисел на доске рассмотрим следующую величину X: сумму всех чисел, уменьшенную на n. Допустим, что с набором произведено описанное в условии преобразование. Как же изменится эта величина? Если сумма всех чисел набора, кроме a и b, равна S, то до преобразования величина X равнялась S + a + b – n, а после преобразования X = S + (a + b – 1) – (n – 1) = S + a + b – n. Итак, значение величины X не изменилось, она – инвариант. Исходно (для набора из условия задачи) X = (1 + 2 +  …  + 19 + 20) – 20 = 190. Значит, и после 19 операций, когда на доске останется одно число p, X также будет равно 190. Но по своему определению, в этот момент X будет равно p – 1. Значит, p = 191. Следовательно, число, оставшееся на доске обязательно будет равно 191.

Задача 4:

На доске выписаны числа 1, 2, …, 20. Разрешается стереть любые два числа a и b и заменить их на число ab + a + b. Какое число может остаться на доске после 19 таких операций?

Подсказка: В качестве инварианта рассмотрите следующую величину: произведение всех чисел на доске, предварительно увеличенных на 1.

Задача 5:

На шести елках сидят шесть чижей, на каждой елке – по чижу. Елки растут в ряд с интервалами в 10 метров. Если какой-то чиж перелетает с одной елки на другую, то какой-то другой чиж обязательно перелетает на столько же метров, но в обратном направлении. Могут ли все чижи собраться на одной елке? А если чижей и елок – семь?

Решение:

В качестве инварианта рассмотрите следующую величину: пусть каждый чиж получает номер, равный номеру елки, на которой он сидит (считая слева). Тогда сумма номеров чижей S – инвариант.

Задача 6:

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

Задача 7:

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

Решение:

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

Задача 8:

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

Решение:

Докажите, что четность числа черных клеток в квадрате из клеток a1, a2, b1, b2 не меняется при перекрашиваниях.

Задача 9:

На доске написаны числа 1, 2, 3, …, 1989. Разрешается стереть любые два числа и написать вместо них разность этих чисел. Можно ли добиться того, чтобы все числа на доске были нулями?

Решение:

Проверьте, что четность суммы чисел на доске неизменна.

Задача 10:

В стране Серобуромалин живет 13 серых, 15 бурых и 17 малиновых хамелеонов. Когда встречаются два хамелеона разного цвета, они одновременно приобретают окраску третьего цвета (например, серый и бурый становятся малиновыми). Может ли через некоторое время оказаться, что все хамелеоны имеют один цвет?

Решение:

В чем состоит описанная операция? В том, что «пропадают» два хамелеона двух разных цветов и «появляются» два хамелеона третьего цвета. Если догадаться о том, что величину-инвариант нужно определять по набору чисел (a, b, c), где a, b и c – количества серых, бурых и малиновых хамелеонов соответственно, то дальше решение получается почти сразу же. В самом деле, операция, описанная в условии, означает то, что из набора (a, b, c) получается набор (a – 1, b – 1, c + 2) или набор (a – 1, b + 2, c – 1) или набор (a + 2, b – 1, c – 1) – все зависит от того, в какой цвет перекрашивается хамелеоны. Очевидно, что разности между числами набора либо не меняются, либо изменяются на 3, а значит, остатки этих разностей при делении на 3 не меняются – они инвариантны. Но в начале a – b = 13 – 15 =  – 2, а в случае, если все хамелеоны малиновые, a – b = 0 – 0 = 0.Числа 0 и  – 2 имеют разные остатки при делении на 3, что и доказывает невозможность такого положения дел в стране. Аналогично разбираются и случаи, когда все хамелеоны стали серыми, или все стали бурыми.

Задача 11:

В вершинах правильного 12-угольника расставлены числа  + 1 и  – 1 так, что во всех вершинах, кроме одной, стоят  + 1. Разрешается изменять знак в любых k подряд идущих вершинах. Можно ли такими операциями добиться того, чтобы единственное число  – 1 сдвинулось в соседнюю с исходной вершину, если а) k = 3; б) k = 4; в) k = 6?

Решение:

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

В качестве инварианта рассмотрим произведение всех чисел в отмеченных вершинах. В начале оно равно  – 1, а в случае, когда число  – 1 сместилось в соседнюю слева (неотмеченную) вершину, равно 1. Инвариантность же введенной величины следует из описанного выше свойства множества отмеченных вершин.