И. О. Соловьева. Практикум по решению олимпиадных задач по матем. Практикум по решению олимпиадных задач по математике

• Название: Практикум по решению олимпиадных задач по математике
• Дата: 17.04.2022
• Размер: 1.1 Mb.
• Имя файла: И. О. Соловьева. Практикум по решению олимпиадных задач по матем.pdf
• Тип: Практикум; #480212
• страница: 7 из 9

2. Принцип Дирихле
20. Так как в 30 классах более чем
990 30 33


учащихся, то хотя бы в одном классе более 33 учеников.
21. а) Указание:
12

n
,
1

k
б) Ответ: нет.
22. Количество ошибок для 29 учеников (не считая Вовы) – 13, от 0 до 12, при этом
2 13 29


, следовательно, хотя бы три ученика сделали одинаковое количество ошибок.
23. Ответ: нет.
Указание: посчитайте сумму всех полученных в условии сумм, а также определите последнюю цифру этой суммы при условии, что все суммы оканчиваются на разные цифры.
24. Предположим, что все ребята собрали разное количество орехов. Определим, какое наименьшее количество орехов могло быть собрано в этом случае. Для этого нужно найти сумму пятна- дцати слагаемых:
105 14 2
1 0





. Полученное число более
100. Следовательно, предположение о том, что все ребята собрали разное количество орехов, неверно.
25. Указание. Разность чисел делится на 11, если они имеют одинаковые остатки от деления на 11. «Кролики» – числа, «клетки»
– остатки от деления на 11 (0, 1, 2, ..., 10;
11

n
).
26. Указание: разбить все натуральные числа на n классов в соответствии с тем, какой остаток получается при делении на n
(см. задачу 25).
27. Ответ: 26.
Выберем пять студентов, по одному с каждого курса, и под- считаем наименьшее количество задач, придуманных ими. По- скольку количество задач, придуманных ими, различно, то всего придумано не менее, чем
15 5
4 3
2 1





задач. Тогда осталь- ные 25 студентов придумали не более чем
25 15 40


задач (т.е.

63 каждый из них придумал по одной задаче). Следовательно, всего по одной задаче придумали 26 человек.
28. Ответ: верно.
Выясним сначала, сколько существует различных наборов оценок, которые может получить школьник за три контрольных работы. За первую работу – любую из четырех оценок, за вторую – тоже любую из четырех, и т.д., всего
64 4
4 4



варианта наборов оценок. Поэтому, если бы все школьники получили разные наборы оценок, то общее число школьников было бы не больше 64, а по условию их 65.
29. Разобьем данный квадрат со стороной 1 м на квадратики со стороной 0,2 м (рис. 19). Таких квад- ратиков будет 25. Поскольку точек в большом квад- рате
2 25 51


, то по принципу Дирихле в каком- нибудь из маленьких квадратиков буде не менее трех точек.
30. Указание: см. решение предыдущей задачи, вокруг маленьких квадратиков описать окружности, найти их ра- диусы.
31. Указание: Если салфетки лежат «в один слой», то всего на столе не более 49 салфеток, «в два слоя» – не более 98 салфеток.
32. Рассмотрим прямые, параллельные данным, проходящие через одну точку. При пересечении этих прямых образовалось 14 углов, причем углы между этими прямыми равны углам между данными в условии задачи прямыми. Предположим, что каждый угол между двумя соседними прямыми не менее
0 26
, тогда их сумма будет составлять не менее
0 364 . Однако в сумме эти углы образуют два развернутых, т.е.
0 360
. Следовательно, хотя бы один из образовавшихся углов менее
0 26 .
33. Указание: решение аналогично решению задачи 30.
34. Чтобы координата середины отрезка была целочисленной, соответствующие координаты концов отрезка должны быть одной четности. Четность каждой координаты может иметь два значения
(чет и нечет), точка на плоскости имеет две координаты, следова- тельно, для координат каждой точки возможны следующие вариан- ты: (чет, чет), (чет, нечет), (нечет, чет), (нечет, нечет). Поскольку
Рис. 19

64 точек 5, по принципу Дирихле найдутся две точки с координатами одинаковой четности, середина отрезка с концами в этих точках – искомая.
35. В таблице шесть строк, шесть столбцов, две диагонали, следовательно, получится 14 сумм. Поскольку складываются шесть целых чисел от 1

до 1, то суммы могут принимать целые значе- ния от 6

до 6 (всего 13 возможных сумм). По принципу Дирихле хотя бы две из четырнадцати сумм будут одинаковыми.
36. Рассмотрим двух учеников класса, которые не дружат друг с другом. (Если таких нет, то все ученики дружат между собой, значит, у каждого ученика имеется 24 друга, и задача решена.)
Обозначим этих двух учеников А и Б. Тогда из оставшихся 23 уче- ников каждый дружил либо с А, либо с Б. Действительно, если ка- кой-либо ученик не дружит ни с А, ни с Б, то мы имели бы трех учеников, среди которых не было бы друзей. Теперь если предпо- ложить, что и А, и Б имеют не более 11 друзей, то всего в классе
(кроме этих двоих) было бы не более 22 учеников. Полученное противоречие показывает, что один из школьников имеет не менее
12 друзей.
37. Выберем одну из данных точек. Если через нее проходит более 10 красных прямых, то задача решена. Пусть через выбран- ную точку проходит не более 10 красных прямых, на этих прямых лежит 100 отмеченных точек (не считая выбранной). Согласно принципу Дирихле, найдется красная прямая, на которой не менее
10 точек, вместе с выбранной – 11 точек. Рассмотрим любую точку, не лежащую на данной прямой, она соединена красными прямыми со всеми отмеченными точками. Значит, через нее проходит 11 прямых, проведенных через найденные 11 точек.
38. Отразим океан симметрично относительно центра Земли.
Поскольку сумма площадей океана и его образа превышает пло- щадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмём эту точку вместе с противоположной.
3. Процессы и операции
42. Разложим числа на простые множители:
3 2
12 2


,
3 3
2 54


. Сумма показателей степеней двойки и тройки в разло-

65 жении числа 12 равна трем. После каждой операции эта сумма из- меняется (увеличивается или уменьшается) на единицу, значит, после каждой нечетной операции получается четная сумма показа- телей, а после каждой четной операции – нечетная сумма. Чтобы получить число 54, надо выполнить нечетное число операций, т.к. сумма показателей степеней в этом числе равна четырем. А ровно через час будет совершено 60 операций, т.е. сумма показателей бу- дет нечетной, и не может равняться четырем.
43. Ответ: 8.
Выпишем уже найденные числа и найдем еще несколько: 7, 14,
17, 20, 5, 8, 11, 5 ... Поскольку число 5 повторилось, возникает
«цикл» (числа будут повторяться): 5, 8, 11.


668 3
:
4 2010


(остаток 2), следовательно, на 2010-м месте стоит второе число цикла: 8.
44. Выберем произвольную улицу. Эта улица разбивает город на две части и вместе с одной из получившихся частей кольцевой дороги образует новое кольцо с односторонним движением, а внутри этого кольца образуется новый город, подобный Зурбагану, но меньших размеров. Так как такая операция уменьшает количе- ство улиц, то повторив ее нужное количество раз, мы получим го- род, состоящий из одного квартала, то есть микрорайон, который можно объехать по правилам.
45. Ответ: по A литров в каждом.
Рассмотрим ситуацию, возникающую после первых двух пере- ливаний:
Номер переливания
I сосуд
II сосуд
0
А
А
1 0,5 А
1,5 А
2
А
А
Докажем, что такая же ситуация будет возникать после любых двух последовательных переливаний с нечетным и четным номе- рами. При переливании с нечетным номером n во втором сосуде станет
A
n
n
n
A
A




1
(л), а при следующем переливании в нем останется


A
n
n
A
n
A
n
n
A
n
n












1 1
1 1
1 1
(л). Значит,

66 такое же количество воды будет и в первом сосуде.
46. Разобьем парламент произвольным способом на две пала- ты и организуем процесс «пересаживания»: выбираем парламента- рия, имеющего в своей палате не менее двух врагов, и пересажива- ем его в другую палату, где у него не может быть более одного вра- га. В этом случае общее количество пар врагов, сидящих в одной палате, уменьшится, значит, такой процесс не может продолжаться бесконечно (общее количество пар врагов конечно). В тот момент, когда процесс останавливается, и будет достигнуто нужное разбие- ние.
47. Ответ: 31.
Первый способ. Пусть поток студентов, сдававших зачет, насчитывал x человек. Составим таблицу:
Дни
Пришло (чел.) Сдало (чел.)
Осталось (чел.)
1
x
3 1

x
3 1
2

x
2 3
1 2

x
9 2
2

x
9 5
4

x
3 9
5 4

x
27 4
4

x
27 19 8

x
4 27 19 8

x
81 8
8

x
81 65 16

x
5 81 65 16

x
243 16 16

x
243 211 32

x
Для того чтобы искомое количество студентов было наимень- шим, должно быть наименьшим значение x , причем все числа, за- писанные в таблице, должны быть натуральными.


5 4
3 1
2 243 16 16




x
x
, значит,
5 3
1


x
, то есть
1 3
5


x
Тогда
31 243 211 32


x
Второй способ. Предположим, что вместе со студентами каж- дый день приходил еще один школьник, тогда можно считать, что в каждый из пяти дней ровно треть пришедших получали зачет, а две

67 трети должны были придти на следующий день. Так как зачет при- нимался пять раз, то количество пришедших на зачет должно быть кратно числу
5 3 , то есть в первый раз на зачет пришли
242 1
243


студента. В этом случае непосредственным подсче- том выясняем, что после пятого раза не сдавших зачет останется 32 человека, из которых один – школьник.
48. Ответ: можно.
49. Ответ: можно.
Наберем воды в 16-литровое ведро, перельем в 15-литровое, в
16-литровом останется 1 л, перельем в 15-литровое ведро. Затем опять наберем воды в 16-литровое ведро, перельем 14 л в 15- литровое ведро, в 16-литровом останется 2 л. Продолжаем эти опе- рации, в 16-литровом каждый раз количество воды будет увеличи- ваться на 1 л. Таким образом можно набрать 8 л воды.
50.
51.
52.
11
)
7 11
(
15



. Поэтому сначала запустим часы одновре- менно, через 7 минут начнем варить кашу. Когда истечет 11 минут
(каша к этому моменту варится 4 минуты), перевернем 11- минутные часы и варим кашу до конца.
53. а) Ответ: 3 взвешивания.
Покажем, как нужно взвешивать монеты. Первое взвешивание: на чаши весов положим по 7 монет (7 монет отложено). Если весы находятся в равновесии, то фальшивая монета среди отложенных.
Если весы находятся не в равновесии, то фальшивая монета нахо- дится на той чаше весов, которая перевесила. Таким образом, после первого взвешивания удалось определить 7 монет, среди которых находится фальшивая. Второе взвешивание: на чаши весов поло-
Ведро, 4 л
0 4
0 4
0 1
1 4
Ведро, 9 л
9 5
5 1
1 0
9
6
Ведро, 8 л
8 3
3 6
6 1
1
Бидон, 5 л
0 5
2 2
0 5
4
Банка, 3 л
0 0
3 0
2 2
3 7 ведер
6 3
3 7
5
5
6 ведер
4 4
6 2
2
5
3 ведра
0 3
1 1
3 0

68 жим по 3 монеты (одна монета отложена). Если весы в равновесии, то фальшивая монета – отложенная. В этом случае поиск фальши- вой монеты завершен. Если весы не в равновесии, то фальшивая монета на перевесившей чаше. Третьим взвешиванием (по одной монете на чаши весов, одну отложить) мы определим фальшивую монету. б) Ответ: 5 взвешиваний.
Кратко опишем взвешивания. Первое: взвешиваем 67 и 67 (66 отложено). Второе: взвешиваем 22 и 22 (23 или 22 отложено). Тре- тье: взвешиваем 8 и 8 (6 или 7 отложено). Четвертое: взвешиваем 3 и 3 (отложено 2 или 1 или ни одной монеты). Пятое взвешивание
(если потребуется): 1 и 1 (возможно, одна монета отложена). в) Ответ: k взвешиваний, где
k
k
n
3 3
1



Будем рассуждать по индукции (по числу взвешиваний).
Найдем наибольшее количество монет, из которых мы сможем вы- делить фальшивую за одно взвешивание. Если на одной чаше весов при взвешивании находятся 2 монеты, то по результату взвешива- ния мы не сможем сказать, какая из них фальшивая, а какая насто- ящая. Поэтому взвесить можем не более двух монет. Если отложе- но не менее двух монет, то мы также не сможем выделить из них фальшивую. Значит, отложить можно также не более одной моне- ты. Таким образом, за одно взвешивание мы можем определить фальшивую монету из трех монет (не более). За два взвешивания можно определить фальшивую из девяти монет: по три монеты взвешиваем, три отложено (тогда за одно взвешивание определяет- ся группа из трех монет, в которой находится фальшивая, а вторым взвешиванием – из выделенных трех монет определяется фальши- вая). Аналогично рассуждая, получим, что за три взвешивания можно выделить фальшивую из 27 монет (
3 3
), за четыре взвешива- ния – из 81 монеты (
4 3
), ..., за k взвешиваний – из
k
3
монет. Та- ким образом, чтобы выяснить, сколько взвешиваний потребуется для определения фальшивой из n монет, нужно найти такое число
k , которое удовлетворяет двойному неравенству
k
k
n
3 3
1



. По- требуется k взвешиваний. Для определения фальшивой монеты нужно каждый раз монеты делить на три равные (или примерно равные) группы, две взвешивать, а одну откладывать.

69 54. Первый способ. Первое взвешивание: три монеты кладем на одну чашу весов, три другие – на вторую чашу (одна монета от- ложена). Если весы находятся в равновесии, значит, на обеих ча- шах находится по одной фальшивой монете. В этом случае второе взвешивание: взять две монеты с одной чаши и сравнить друг с другом. Если весы в равновесии, то эти две монеты и отложенная в первом взвешивании – искомые. Если весы при втором взвешива- нии не находятся в равновесии, то настоящими будут монеты: бо- лее тяжелая при втором взвешивании, третья монета с чаши и от- ложенная в первом взвешивании. Теперь рассмотрим случай, когда при первом взвешивании весы не находятся в равновесии. В этом случае на перевесившей чаше не может быть фальшивых монет.
Действительно, если бы на ней была хоть одна фальшивая монета, то на той чаше, которая легче, должно быть по крайне мере две фальшивых монеты. Поскольку всего фальшивых монет по усло- вию задачи две, то это невозможно. Следовательно, три монеты, лежащие на перевесившей чаше, являются искомыми.
Второй способ. Первое взвешивание: на каждую чашу поло- жим по две монеты (три монеты отложены). Если весы находятся в равновесии, то возможны два варианта расположения фальшивых монет: либо по одной на каждой чаше, либо обе – в отложенных монетах. Чтобы это выяснить, при втором взвешивании поместим на весы монеты с одной чаши. Если весы в равновесии, то в первом взвешивании все 4 монеты на весах – настоящие. Если весы не в равновесии, то настоящими являются 3 отложенные в первом взвешивании монеты. Теперь рассмотрим случай, когда при первом взвешивании весы не находятся в равновесии. В этом случае на пе- ревесившей чаше обе монеты настоящие (см. объяснение в первом способе). Вторым взвешиванием сравним друг с другом монеты с более легкой чаши. Если весы в равновесии, то обе монеты – фальшивые, все остальные – настоящие. Если весы не в равнове- сии, то более тяжелая монета вместе с двумя монетами с более тя- желой чаши – искомые.
55. Будем обозначать веса монет
6 2
1
...,
,
,
a
a
a
. Первым взвеши- ванием сравним
1
a и
2
a . Случай 1.
2 1
a
a

. Тогда монеты 1 и 2 настоящие. Сравним монеты 3 и 4. Если
4 3
a
a

, фальшивые моне- ты – 5 и 6. Если
4 3
a
a

, одна из фальшивых монет – 3, а вторая

70 находится среди 4, 5 и 6 (она выделяется сравнением
4
a и
5
a ).
Случай
4 3
a
a

аналогичен. Случай 2.
2 1
a
a

. Монета 1 – фальши- вая. Вторая фальшивая монета выделяется сравнениями монет 2 и 3 и монет 4 и 5 (если при одном из взвешиваний неравенство – более легкая монета фальшивая, иначе фальшивая монета 6). Случай
2 1
a
a

аналогичен случаю 2.
56. а) Ответ: два взвешивания.
Разобьем монеты на три кучки по 6 монет. Сравниваем вес двух кучек. Если весы в равновесии, то все взвешенные монеты настоящие, а фальшивая монета в отложенной кучке. Тогда вторым взвешиванием сравниваем одну из уже взвешенных кучек с отло- женной кучкой, по результату взвешивания будет ясен ответ на во- прос задачи. Если же при первом взвешивании одна из кучек пере- весила, то в отложенной кучке все монеты настоящие, сравниваем ее вес с весом одной из уже взвешенных кучек. б). Ответ: два взвешивания.
Рассмотрим для n три случая:
k
n
3

,
1 3


k
n
,
2 3


k
n
. В первом случае решение задачи аналогично решению задачи а). Рас- смотрим второй случай. Разобьем монеты на три кучки: k , k и
1

k
монета. Сравним первые две кучки. Если весы в равновесии, то фальшивая монета в третьей кучке, сравниваем ее с одной из уже взвешенных кучек (добавив в нее одну монету из другой взве- шенной кучки). Если же при первом взвешивании весы не в равно- весии, то в кучке с
1

k
монетой все монеты настоящие, отложим из нее одну монету и сравним оставшиеся с одной из кучек, взве- шенной ранее. Случай
2 3


k
n
рассматривается аналогично.
57. Первые два взвешивания: сравниваем 1 и 2, затем 3 и 4 па- кеты. Третьим взвешиванием сравниваем массы двух более легких пакетов, четвертым – двух более тяжелых. Таким образом, за четы- ре взвешивания определили самый легкий и самый тяжелый паке- ты, а пятым сравниваем два средних.
58. Разобьем все монеты на 4 группы по 10 монет, обозначим эти группы A, B, C, D. Первым взвешиванием сравним группы A и
B. Если весы в равновесии, то либо в группах A и B по одной фальшивой, либо все взвешенные монеты – настоящие. При втором взвешивании разобьем монеты группы A по пять. Если весы в рав- новесии, то монеты групп A и B являются настоящими, если не в

71 равновесии, то искомые – монеты групп C и D. Если же при первом взвешивании весы не находятся в равновесии, то на перевесившей чаше все монеты настоящие (см. решение задачи 54, первый спо- соб). При втором взвешивании сравним вес монет групп C и D. Ес- ли весы в равновесии, то в этих группах все монеты настоящие.
Если весы не в равновесии, то искомыми являются монеты групп, перевесивших в обоих взвешиваниях.
59. Первым взвешиванием сравним вес первой и восьмой мо- нет. Поскольку первая легче, значит, она фальшивая, а восьмая – настоящая. При втором взвешивании на одну чашу весов положим первую и восьмую монеты, а на другую – вторую и третью. По- скольку вторая и третья легче, чем первая и восьмая, среди них фальшивых монет больше, значит, они обе фальшивые. Аналогич- но поступим при третьем взвешивании: на одну чашу весов поло- жим первую, вторую, третью и восьмую монеты, четыре оставших- ся – на другую. Все монеты с четвертой по седьмую – фальшивые, так как они легче, чем три фальшивые и одна настоящая.