Сборник задач

Составил

СБОРНИК ЗАДАЧ

Первые пять задач – это задачи Международной Олимпиады «Эрудит», физико-математической олимпиады «Физтех 2014», заданий заочной физико-технической школы МФТИ для 8 класса.. Даже мой небольшой опыт при решении задач на инвариант помог мне справиться с ними. Далее я привел несколько интересных, на мой взгляд, задач, которые я решал в процессе знакомства с Инвариантами (из книг [1],[2],[3]). Думаю, что Вам эти задачи тоже помогут научиться применять метод Инвариант!

Задача 1. Может ли всадник обойти куб 1979*1979*1979, разбитый на единичные кубики, посещая каждый из них ровно по одному разу, если в начальный момент он находится в центральном кубике (равноудаленном от граней куба)? Одним ходом всадник может перейти из кубика в один из 6 соседних, имеющих общую грань.

Решение: Для того, чтобы найти инвариант, сначала рассмотрим эту же задачу, но на небольшом участке, содержащим все существенные параметры (должен быть центральный кубик, т. е. единичных кубиков должно быть нечетное количество). Начнем с куба, состоящего из единичных кубиков размерностью три - 3*3*3. Раскрасим все его единичные кубики в шахматном порядке. Для наглядности представим куб в виде трех слоев, каждый из которых состоит из 9-ти единичных кубиков. (рис.1,2,3). На рис. 2 изображен «центральный» слой. Заметим, что в нем центральный кубик – белый. Всего же у нас – 14 черных и 13 белых кубиков. Мы начинаем ходить с центрального белого кубика. Из условия задачи следует, что мы не можем ходить «наискосок», следовательно следующий кубик – черный, затем белый и т. д. , т. е. при каждом ходе мы меняем цвет кубика. Поскольку начали мы ходить с белого и дважды нельзя пройти по одному и тому же, а единичных кубиков нечетное число (27), то последний кубик обязательно должен быть белым, а это не так! (белых меньше, чем черных). Следовательно кубик 3*3*3 пройти нельзя!

Теперь рассмотрим кубик 5*5*5. Поделим его тоже на слои из единичных кубиков. В нем будут 3 слоя (центральный (3-й) и крайние (1-й и 5-й), как на рис.5 и два слоя (4-й и 2-й), как на рис.4. Ситуация поменялась – кубиков, имеющих цвет центрального кубика, стало больше, чем кубиков, имеющих другой цвет! (65 и 60). Более того, его пройти, выполнив условия задачи, можно! Доказательство приведено на рис. 6-10! Мы выходим из точки А на рис. 8 (3-й, центральный слой), идем по кругу, как показано стрелками и доходим до кубика В, затем, оставив кубик О непройденным, идем на следующий слой, обходим его, начиная с кубика В как показано на рис. 7, (О – не пройден), доходим до кубика А, переходим на следующий слой и обходим все кубики слоя по кругу, как на рис. 8, заметим, что мы через кубики О

Рис.1. Рис.2. Рис.3

Рис.4. Рис.5.

		А
			В	О

		А
			В	О

Рис.6. Рис.7.

		А
				О

		А
				О

Рис.8. Рис.9.

		А
				О

Рис.10.

спускаемся на слой под центральным слоем (кубики О всех трех слоев при этом пройдены!). Теперь мы обходим этот слой как показано на рис. 9, доходим до точки А, спускаемся на последний слой и проходим его, как показано на рис.10. (обратите внимание, мы закончили на кубике цветом совпадающим с центральным!)

Обратим внимание на то, что если мы добавим еще по одному слою (кубик 7*7*7), то мы не сможем воспользоваться приведенным методом обхода, нам не хватит еще одного слоя, чтобы вернуться, пройдя все кубики! (мы или оставим непройденным центральный (А), либо не попадем в точку возврата О). А кубиков, имеющих цвет центрального – меньше, чем других!

(Имеем: если центральные кубики на крайних гранях куба имеют цвет центрального кубика всего куба – то кубиков такого цвета больше, чем кубиков другого цвета!)

Легко проверить, что для кубика 9*9*9 (аналог прохода кубика 5*5*5) мы тоже выполним условия задачи и т. д.

Заметим, что, если размерность кубика равна 3, 7, 11,… - пройти нельзя, а для 5, 9, 13, … - пройти можно, т. е., когда над центральным (и под центральным) слоев, число слоев кратно 2-м, пройти можно.

Инвариант, когда можно обойти все единичные кубики это –

N-1 должно быть кратно 4-м, где N – размерность кубика (число единичных кубиков вдоль грани). Или иначе: инвариант - остаток от деления на 4 числа единичных кубиков. Он должен быть равен 1.

А теперь посмотрим, что мы имеем в нашем случае:

1979-1=1978 не кратно 4-м, (или – остаток от деления 1979 на 4 равен 3) следовательно – нельзя выполнить условия задачи - всадник не сможет обойти по одному разу все единичные кубики куба 1979*1979*1979.

Примечание. А если бы размерность была 1981, то всадник смог бы обойти все единичные кубики предложенным мною способом!

Задача 2. Четно или нечетно произведение (7a+b-2c+1)(3a-5b+4c+10), где а и b – целые числа.

Решение. Рассмотрим исходное выражение и немного по другому

запишем его:

(7a + b – 2c +1)(3a – 5 b +4c +10)= ((7a +b) – (2c-1))((3a -5b) + (4c+10))

Рассмотрим выражения (7a + b) и (3a - 5b). Нетрудно заметить, что они имеют одинаковую четность (так как 7а и 3а имеют одинаковая четность; также b и 5b имеют одинаковая четность).

Теперь рассмотрим ((7a +b) – (2c-1)) и ((3a -5b) + (4c+10)) . Эти выражения имеют разную четность, так как (2с – 1) всегда нечетное (разность четного и нечетного) и, следовательно меняет четность (7a+b), а (4с+ 10) всегда четное (сумма двух четных) и четность (3a-5b) не меняет. В результате мы всегда имеем произведение четного и нечетного чисел, а это, как известно всегда четное число.

Задача 3. Поэт Цветик купил для своих новых стихов тетрадь с 2000 листами и пронумеровал их от 1 до 2000, а потом перевернул и пронумеровал с конца тетради обратную сторону листов снова от 1 до 2000. Затем он долго сочинял новую поэму, а когда понял, что ничего у него не получается, то рассердился и вырвал из тетради 25 листов, идущих подряд. Может ли сумма цифр на обеих страницах вырванных листов быть равной 2000?

Решение. Цветик вырвал 25 листов, это 50 страниц с числами подряд, то есть на каждом листе стоят 2 подряд числа одно из них, следовательно четное, а второе - нечетное, а сумма 2-х чисел четного и нечетного всегда нечетное число. Сумма двух нечетных чисел - четное число, а нечетных – нечетное, а у нас 25 таких сумм, следовательно общая сумма 25 нечетных чисел будет нечетным числом. Число 2000 – четное, следовательно такую сумму Цветик получить не мог!

Задача 4. Последовательность.

На доску выписаны числа a 1  a_1 , a 2  a_2 , …, a 1001  a_{1001} . Известно, что a 1 =4  a_1 = 4 , a 2 =10  a_2 = 10 . Найдите a 1001  a_{1001} , если для любого натурального n  n справедливо равенство a n+2 =a n+1 –a n a_{n + 2} = a_{n + 1} – a_{n} .

Решение. Хочу отметить, что эта задача интересна тем, что инвариант уже задан, это a n+2 =a n+1 –a n . Зная, что инвариант, это нечто неизменное, характеризующее объект, я понял, что нужно восстановить элементы последовательности и определить через сколько элементов и как начнется повторение. Вот, что получилось:

4; 10; 6; -4; -10; -6; 4; 10; 6; -4; -10; -6; …

Получается, что через 6 элементов идет повторение. Значит еще один инвариант это остаток от деления по модулю 6 номера элемента. Далее получаем остаток от деления номера искомого элемента на 6. Это 5.

Следовательно, 5-й элемент последовательности и есть наше число.

a 1001 = -10.

Следующая задача по физике:

Задача 5. Электрическая цепь состоит из очень большого числа одинаковых звеньев, содержащих три сопротивления r = 1 Ом (см. рис. 11, на котором таких звеньев два). Определите сопротивление R¥ цепи между точками A и B, если количество звеньев очень велико, т. е. цепочка бесконечная.

Рис.11

Решение

Исходя из правил расчета последовательных и параллельных соединений, получаем:

RAB = r+r+RЭКВ

1 = 1 + 1

RЭКВ r r+r+ RЭКВ1

Известно, если цепочка бесконечная, то удаление или присоединение одного звена не изменяет сопротивления бесконечной цепочки, т. е. RЭКВ = RЭКВ1. RЭКВ не меняется! Инвариант - RЭКВ. получаем:

1 = 1 + 1

RЭКВ r r+r+ RЭКВ

Решением этого уравнения является RЭКВ = 0.73(ом).

RAB = 1+1+0.73=2.73(ом)

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

Решение: Конечно же, сначала нужно попробовать попереворачивать стаканы. Однако довольно быстро становится понятно, что так просто эта задача не решается. Тогда возникает желание доказать, что добиться требуемой расстановки стаканов невозможно. Как это сделать? Давайте сравним количества стаканов, стоящих на дне и вверх дном. Сначала мы имеем 7 стаканов, которые стоят вверх дном и 0 стаканов, стоящих на дне. Мы можем перевернуть любые два стакана. Какие бы стаканы мы ни выбрали, у нас будет 5 стаканов вверх дном и 2 стакана, стоящих правильно. В следующий раз мы можем перевернуть стаканы различными способами. Так, мы можем поставить на дно два стакана, стоящих вверх дном. Тогда у нас останется 3 стакана, стоящих вверх дном, а 4 стакана будут стоять правильно. Мы можем перевернуть один стакан, стоящий вверх дном, и один стакан, стоящий правильно. Тогда ничего не изменится, и у нас останется 5 стаканов, стоящих вверх дном, и 2 стакана, стоящих на дне. И последний вариант: мы можем перевернуть два стакана, которые стоят на дне. Тогда получим исходную ситуацию, а именно 7 стаканов вверх дном и 0 стаканов, стоящих правильно.

Что же общее во всех этих ситуациях? Найдем разность числа стаканов, стоящих вверх дном, и числа стаканов, стоящих на дне. В исходном варианте эта разность равна семи. После первого переворачивания она становится равна трем. А дальше, в зависимости от выбранного варианта переворачивания стаканов, она станет равной -1, 3 или 7. Мы видим, что эта разность может измениться только на 4. И в данном случае неважно, что исходно мы рассматривали 7 стаканов, которые были перевернуты вверх дном. Если мы рассмотрите случай, когда a стаканов стоят на дне, а b стаканов — вверх дном, мы придем к тому же самому выводу. Предположим, что нам удалось, переворачивая стаканы, добиться их правильного расположения. Тогда в конечной ситуации разность между числом стаканов, стоящих вверх дном, и числом стаканов, стоящих правильно, равна-7. И мы видим, что число -7 отличается от 7 на 14 — это число не кратно 4. Следовательно, действуя описанным в условии задачи способом, добиться того, что все 7стаканов будут стоять на дне, невозможно.

В рассмотренной задаче инвариантом был остаток от деления на 4 разности числа стаканов, стоящих вверх дном, и числа стаканов, стоящих на дне. Он должен всегда оставаться равным 3.

Задача 7. В файле хранятся 2003 единицы и 232 нуля. Программа читает из файла два произвольных числа, стирает, и записывает на их место 0, если они были равны, и 1, если нет. Программа запускается многократно. В конце в файле остается только одно число. Чему оно равно, 0 или 1?

Решение: Несмотря на то, что вариантов действия программы очень много, мы можем установить ответ однозначно. Что может прочитать программа за каждый отдельный запуск? Либо 0 и 0 (и записать 0), либо 0 и 1 (и записать 1), либо 1 и 1 (и записать 0). В первых двух случаях сумма всех чисел в файле не меняется, в последнем - уменьшается на 2. В любом случае, четность этой суммы остается прежней, четность – инвариант!. Исходно сумма была 2003*1+232*0=2003 - нечетная, значит, и в конце будет нечетная. Но в конце остается только одно число - оно и равно сумме всех - поэтому оно нечетное. А так как в файле бывают только нули и единицы, то это 1.

Задача 8. А какое число останется в файле, если программа за один запуск стирает два числа и записывает вместо них их сумму?

Решение: Если в прошлой задаче инвариантом была четность суммы всех чисел в файле, то теперь это будет сама сумма. Ясно, что при замене двух любых чисел на их сумму сумма всех не меняется. Поэтому последнее число - оно же сумма чисел в конце - равно сумме чисел в начале, т. е. 2003.

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

Решение. Рассмотрим число разноцветных пар (не только соседних), где левая фишка красная, и заметим, что чётность этого показателя не меняется. Но в исходной ситуации наш показатель равен 1, а в желаемой ситуации – нулю. Поэтому перейти к желаемой ситуации невозможно.

Задача 10. На вешалке висят 20 платков. 17 девочек по очереди подходят к вешалке и либо снимают, либо вешают платок. Может ли после ухода девочек остаться ровно 10 платков?

Решение. После подхода первой девочки количество оставшихся платков либо 19, либо 21 (нечетное количество); после подхода второй девочки – либо 18, либо 20, либо 22 (четное количество); после подхода третьей девочки – либо 17, либо 21, либо 23, либо 19 (нечетное количество). После подхода 17 девочки остается нечетное количество платков. Получается противоречие. Значит, 10 платков остаться не может. В задаче инвариантом является четность суммы чисел

Задача 11. Имеются три числа, которые можно заменять по следующим правилам: числа a, b и c стираются и вместо них записываются (a+b)/2, (b+c)/2 и (a+c)/2.Можно ли из чисел 101, 73, 125 получить 77, 79 и 83?

Решение: А давайте так, "на всякий случай", посмотрим, как меняется сумма чисел. Было a+b+c, а стало... вместо них записываются (a+b)/2+(b+c)/2+(a+c)/2 = (2a+2b+2c)/2 = a+b+c - не изменилась. То есть, как ни крути, а сумма трех чисел не меняется. Но 101+73+125=299, а 77+79+83=239 - суммы исходной и конечной тройки разные. Поэтому из одной нельзя получить другую.
(А те, кто захочет взять в качестве инварианта четность суммы или ее остаток по какому-то модулю, скорее всего, ошибутся, так как начальная и конечная суммы различаются на 60, а делителей у 60 много).

Задача 12. Опять имеются три числа, которые можно заменять уже по другим правилам: a, b и c - на ab/c, ac/b и bc/a. Можно ли из 5, 17/6 и 3/5 получить 16/5, 9/4 и 7/6?

Решение: Ну, о том, куда тут переходит сумма чисел, даже думать не хочется. Что еще бывает, кроме суммы? Произведение, например. Перед операцией произведение чисел - abc, а после: (ab/c)*(ac/b)*(bc/a) = a2b2c2/abc = abc - не изменилось! Значит, произведение трех чисел остается постоянным при всех операцих. Но в начале оно было равно 5*(17/6)*(3/5)=8,5, а в конце (16/5)*(9/4)*(7/6)=8,4 - не равны. Поэтому ответ "нельзя".

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

4

 

Рис. 12. Рис.13. Рис.14

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

Например, для рис. 14 имеем S = 2+2+4+4+5+6=23.

Очевидно, что при сдвиге фишки в соседний сектор соответствующее ей слагаемое в сумме S меняет четность. Значит, если сдвигаются одновременно две фишки, то четность суммы S не меняется, а значит она – инвариант задачи!

Но для расстановки на рис.1 S=21. Если же все фишки находятся в одном секторе с номером N (1<N<6), то S = 6N - четное число ( а 21 – число нечетное). Следовательно, из исходной расстановки нельзя получить расстановку, в которой все 6 фишек находятся в одном секторе.

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

Задача 14. Фигура "крокодил" ходит по клетчатой доске на 4 клетки в одном направлении и одну в перпендикулярном (почти как шахматный конь, только конь ходит не на 4, а на 3 клетки). Докажите, что нельзя пройти крокодилом с какого-то поля на соседнее (по стороне) с данным.

Решение: Раскрасим доску в шахматном порядке. Тогда (нетрудно убедиться) крокодил при своем ходе не меняет цвет клетки, на которой стоит. А соседняя клетка, увы, другого цвета, ч. т.д.

						Ж
			Ж	Ж	Ж	Ж

Рис. 15

Задача 15. В каждой клетке доски 5×5 клеток сидит жук. В некоторый момент все жуки переползают на соседние (по горизонтали или вертикали) клетки. Докажите, что осталась хотя бы одна пустая клетка?

Решение: Раскрасим доску в 2 цвета. Черных клеток – 13, а белых – 12.

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

Задача 16. Деревянный куб размером 3 хЗ условно разделен на 27 маленьких кубиков. Жук начинает прогрызать один из крайних угловых кубиков, двигаясь только параллельно ребрам куба. Может ли жук прогрызть все кубики, побывав в каждом только один раз и закончив путь в центральном кубике?

Решение: Раскрасим кубики в шахматном порядке. То есть так, чтобы любые два соседних кубика имели разный цвет: один - белый, другой - черный. Тогда, двигаясь по условию задачи, жук непременно должен проходить из кубика одного цвета в кубик другого цвета. Чередование цвета при переходе из одного кубика в другой - инвариант данной задачи. Пусть жук начинает движение из кубика черного цвета (рис. 16).

Рис. 16

Составим таблицу смены цветов кубиков при движении жука.

№ кубика	1	2	3	4	…	26	27
цвет	ч	б	ч	б		б	ч

То есть последний - 27-й кубик -должен быть черным, но по рисунку совершенно очевидно, что он - белый. Это противоречие говорит о том, что жук не сможет проделать путь, описанный в задании.

Задача 17. Выпуклый n-угольник разбит на треугольники непересекающимися диагоналями, причем в каждой его вершине сходится нечетное число треугольников. Докажите, что n делится на 3.

Решение: Если многоугольник разбит на части несколькими диагоналями, то эти части можно окрасить в два цвета так, чтобы части, имеющие общую сторону, были разного цвета. Это можно сделать следующим образом. Будем последовательно проводить диагонали. Каждая диагональ разбивает многоугольник на две части. В одной из них сохраняем раскраску, а  другую перекрашиваем, заменяя везде белый цвет на черный, а черный - на белый. Проделав эту операцию для всех нужных диагоналей, получим требуемую раскраску. Так как в нашем случае в каждой вершине сходится нечетное число треугольников, то при такой раскраске все стороны многоугольника будут принадлежать треугольникам одного цвета, например черного (рис. 17). Обозначим число сторон белых треугольников через m. Ясно, что m делится на 3. Так как каждая сторона белого треугольника является также и стороной черного треугольника, а все стороны многоугольника являются сторонами черных треугольников, то число сторон черных треугольников равно n + m. Поэтому n + m делится на 3, а поскольку m делится на 3, то и n делится на 3.

Рис.17

Задача 18. Плоскость раскрашена в три цвета. Докажите, что найдутся две точки одного цвета, расстояние между которыми равно 1.

Решение. Предположим, что любые две точки, лежащие на расстоянии 1, окрашены в разные цвета. Рассмотрим правильный треугольник ABC со стороной 1; все его вершины разного цвета. Пусть точка A1 симметрична A относительно прямой BC. Так как A1B = A1C = 1, то цвет точки A1 отличен от цветов точек B и C, т. е. она окрашена в тот же цвет, что и точка A. Эти рассуждения показывают, что если AA1 = √3, то точки A и A1 одного цвета. Поэтому все точки окружности радиуса √3 с центром A одного цвета. Ясно, что на этой окружности найдутся две точки, расстояние между которыми равно 1. Получено противоречие.

ЛИТЕРАТУРА

1. , , Фомин математические кружки. - Киров.: Издательство «АСА», 1994. - 271 с.

2. Спивак кружок. 6-7 классы, - М.: МЦНМО, 2012.- 128 с.

3. Фарков к олимпиадам по математике: учеб-метод. Пособие, - М.: Издательство «Экзамен», 2010. – 158 с.