Задача 1: В 100-этажном доме лифт имеет кнопки « + 6» и « – 4» (первая поднимает лифт на 6 этажей, вторая опускает на 4). Доказать, что им нельзя пользоваться.

Задача 2: a) Хулиган Вася порвал стенгазету, причем каждый попадающийся ему кусок он рвал на четыре части. Могло ли получиться 1989 кусков?

b) А если каждый кусок рвался на 4 или 10 частей?

Задача 3: В клетках таблицы 3 × 3 стоят нули. Можно прибавлять по 1 к клеткам любого квадрата 2 × 2. Можно ли получить таблицу?

?

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

a) делились на 2

b) делились на 3.

Задача 5: В углу квадрата a) 4 × 4 b) 3 × 3 стоит минус, в остальных – плюсы. Можно ли заменять все знаки в любом столбце или строке на противоположные. Можно ли получить таблицу из одних плюсов?

Задача 6: Круг разделили на 6 секторов, в каждом лежит селедка. За ход можно одну селедку передвинуть в соседний сектор. Можно ли собрать все селедки в одном секторе ровно за 20 ходов?

Задача 7: В ряд выписаны числа 1, 2, 3,…,100. Можно менять местами любые два числа, между которыми стоит ровно одно. Можно ли получить ряд 100, 99, 98,…, 2, 1?

Задача 8: К числу можно прибавлять сумму его цифр. Можно ли за несколько шагов получить из единицы число 123456?

Задача 9: На доске выписаны числа от 1 до 21. Можно любые два числа заменять на модуль их разности. Может ли в конце (после 20 операций) остаться 0?

Задача 10: На столе стоят 50 стаканов, из них 25 – вверх дном. Можно ли, переворачивая по 4 стакана, получить все стаканы стоящими правильно?

Задача 11: a) Можно ли операциями «прибавить 4» и «умножить на 3» получить из единицы число 1990?

b) Какие числа можно получить?

Задача 12: На доске написано 100 плюсов и 100 минусов. Можно заменять любые 2 минуса на плюс, плюс и минус на минус, два плюса на плюс. Доказать, что знак, который останется в конце, не зависит от порядка операций.

Задача 13: Круг разделен на 6 секторов, в которых по часовой стрелке стоят числа a) 1,0,0,0,0,0 b) 1,0,1,0,0,0. Можно прибавлять по единице к любым двум соседним секторам. Можно ли сделать все числа равными?

Задача 14: На доске написаны числа от 1 до 20. Можно любую пару чисел x, y заменять на x + y + 5xy. Может ли в конце получиться 19901989?

Задача 15: Фигура ходит по диагонали прямоугольника 1 × n (например, для коня это 1 × 2). При каком n она может попасть с любой клетки на любую на бесконечной доске?

Задача 16: На доске написаны числа от 1 до 20.

a) Можно пару чисел (x, y) заменить на x + y. Какое число останется после 19 таких операций?

b) Можно (x, y) заменить на 3x + 5y. Может ли в конце остаться 45239?

c) (x,y) можно заменить на 4(x + y). Может ли в конце остаться 4000?

Задача 17: Квадрат a) 2 × 2 b) 3 × 3 заполнен плюсами. Можно в любой строке или в любом столбце менять все плюсы на минусы. Сколько различных расстановок плюсов и минусов можно получить такими операциями?

Задача 18: На доске написаны числа от 1 до 20. Можно пару чисел (x,y) заменить на x + y + xy. Какое число останется после 19 операций?

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

a)6, 0, 0, 0, 0, 0. b) 5, 1, 0, 0, 0, 0.

Задача 20: В квадрате 10 × 10 стоят 100 ненулевых чисел. Можно менять знак у чисел в любом столбце или строке.

a) Всегда ли можно сделать все числа положительными?

b) Всегда ли можно сумму в любом столбце или в любой строке сделать неотрицательной?

Задача 21: По окружности стоят 3 числа. На каждом шагу между каждыми двумя пишут модуль их разности, а старые числа стирают. Могут ли через 100 шагов получиться числа a) 60, 70, 150. b) 60, 70, 130.

Задача 22: На доске написаны числа 2, 2, 2. Числа a,b,c можно заменять на a,b,a + b – 1.

a) Можно ли такими операциями получить набор 19,1971,1989.

b) Какие наборы можно получить?

Задача 23: a) Набор из трех чисел a,b,c каждую секунду заменяется на набор a + b – c,a + c – b,b + c – a. В начале имеется набор из чисел 1989, 1990, 1991. Может ли через некоторое время получиться набор 1987, 1990, 1991?

b) Тот же вопрос, если числа a,b,c заменяются на , , .

Задача 24: Квадрат 4 × 4 раскрашен в 2 цвета. Можно менять цвет у всех клеток любого столбца или строки. Характеристикой раскраски называется наименьшее число черных клеток, которого можно достичь такими операциями.

a) Доказать, что бывают раскраски с характеристиками 0, 1, 2, 3, 4.

b) Какие характеристики бывают?

Задача 25: На доске написаны числа от 1 до 1990. Можно любую пару чисел a, b заменить на число a² – b². Можно ли добиться, чтобы в конце (после 1989 операций) остался ноль?

Задача 26: a) В квадрате 4 × 4 клетка, соседняя с угловой, – черная, а остальные – белые. Можно перекрашивать все клетки любого столбца, строки или диагонали (не обязательно главной). Доказать, что такими операциями нельзя получить целиком белый квадрат.

b) То же для квадрата 8 × 8, у которого закрашена любая не угловая клетка.

Задача 27: В квадрате 8 × 8 стоят целые числа. Можно прибавлять по единице ко всем числам любого квадрата 3 × 3 или 4 × 4. Всегда ли можно добиться, чтобы все числа в таблице делились на 3?

Задача 28: a) В ряд стоят несколько фишек. Можно менять местами любые две соседние. После нескольких таких операций обнаружили, что все фишки оказались на своих исходных местах. Доказать, что было сделано четное число перестановок.

b) То же, если менять местами можно любые две (не обязательно соседние) фишки.

Задача 29: На доске написаны три числа. можно брать любые два из них – a и b и заменять их на , . В начале написаны числа 1990, 1995, 1996. Можно ли получить набор 1991, 1994, 1997?

Задача 30: В ряд выписаны числа от 1 до 1991. Разрешается брать любые 4 числа и переставлять их в обратном порядке. Можно ли такими операциями получить ряд 1991, 1990, …, 2, 1?

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

Задача 32: Автомат работает с карточками, на которых написаны пары чисел. Из карточки (a,b) он может сделать (a/2, b/2), если a и b четны, или (a + 1,b + 1). Из карточки (a,b) и (b,c) он может сделать карточку (a,c). Исходные карточки он возвращает. Вначале есть карточка (5,10).

a) Можно ли получить (1,100)?

b) Можно ли получить (1,50)?

c) Для каких x можно получить карточку (1,x)?

Задача 33: Три кузнечика сидят на плоскости в точках с координатами (0,0), (0,1), (1,0). Каждую секунду один из них прыгает в точку симметричную относительно какого-то другого.

a) Могут ли они попасть в точки (0,1), (1,0), (1,1)?

b) В точки (x,y), (x + 1,y + 1), (x + z,y)?

c) Могут ли они попасть в точки (x,y), (x + 3,y), (x,y + 3)?

Задача 34: 4 кузнечика играют в чехарду на плоскости, как в предыдущей задаче. Вначале они находятся в точках (0,0), (0,1), (1,1). Могут ли они попасть в точки (x,y), (x + 1,y + 1), (x + 3,y), (x + 2,y – 1)?

Задача 35: В алфавите имеются только две буквы – А и Я. Комбинации букв АЯ и ЯЯЯ, ЯА и ААЯ, ЯЯ и ААА в любом слове можно заменять друг на друга. Можно ли из слова АЯЯ получить слово ЯАА?

Задача 36: Написаны 4 числа: a,b,c,d. Каждую секунду они заменяются на числа a + b,b + c,c + d,d + a. Через некоторое время опять получились исходные числа. Доказать, что все числа равны нулю.

Задача 37: 239 машин целый день ездили по круговой дороге в одном направлении. Вечером все они оказались на тех же местах, откуда начинали. Доказать, что они совершили четное число обгонов.