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

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

4. Инварианты и полуинварианты
63. а) Ответ: нельзя.
Если стакан переворачивается четное число раз, то он оказыва- ется в начальном положении. Поэтому чтобы поставить все стака- ны дном вниз, нужно каждый стакан перевернуть нечетное число раз. Общее количество переворачиваний также будет нечетным
(сумма семи нечетных слагаемых). Но по условию за один раз пе- реворачивается 2 стакана, значит, общее количество переворачива- ний – четное. б) Ответ: нельзя. Решение аналогично задаче со стаканами. в) Ответ: можно.
Первый раз переворачиваем все пятаки кроме первого, второй раз – кроме второго, ... , восьмой раз – все кроме восьмого. Таким образом, каждый пятак будет перевернут 7 раз, поэтому окажется в положении «гербом вниз», что и требовалось.
64. Ответ: нельзя.
Если количество яблок в соседних корзинах отличается на 1, то числа, выражающие это количество, будут поочередно четными и

72 нечетными. Таким образом, получим 8 четных чисел и 8 нечетных чисел. Количество яблок во всех корзинах должно быть четным (8 четных и 8 нечетных слагаемых). Значит, 55 яблок разложить в корзины требуемым образом не удастся.
65. Ответ: 9.
Найдем инвариант, т.е. характеристику, которая сохраняется при переходе от числа к сумме его цифр. Таким инвариантом явля- ется делимость на 3 и 9: число и сумма его цифр либо одновре- менно делятся на 3 (на 9), либо не делятся. Очевидно, что данное в условии число делится и на 3, и на 9. Значит, полученное одно- значное число тоже должно делиться и на 3, и на 9. Такое одно- значное число одно: 9.
66. Ответ: можно.
Из условия задачи ясно, что количество бананов либо не изме- няется (если срываются два ананаса или банан и ананас), либо уменьшается на 2 (если сорвать два банана), т.е. четность количе- ства бананов сохраняется. Значит, если сначала количество бананов было нечетным, то оставшийся плод – банан, если количество ба- нанов было четным – остался ананас.
67. Ответ: нет.
Рассмотрим разность количеств букв «ы» и «у» в одном слове.
Ни одна из описанных операций не изменяет этой величины. Так как в словах «уыу» и «ыуы» эта разность различна, то эти слова не могут обозначать одно и то же.
68. Ответ: нет.
Рассмотрим общее количество таких разноцветных пар (не только соседних), в которых красная фишка расположена левее си- ней. Заметим, что четность этого показателя не изменяется при указанных операциях. В исходной ситуации этот показатель равен
1, а в желаемой ситуации – 0. Поэтому перейти от исходного поло- жения фишек к желаемому – невозможно.
69. Легко проверить, что длина границы всего заросшего бурь- яном участка (или нескольких участков) при указанных условиях не возрастает. В начальный момент она не превосходит
36 4
9


, поэтому в конечный момент она не может быть равной 40 (пери- метр всего поля).

73 70. Заменим в таблице знак «+» на число 1, а знак «–» на число
1

. При смене знаков у всех чисел одного столбца или одной стро- ки произведение всех чисел в таблице не изменяется, так как одно- временно меняются знаки у четырех чисел. В начальном положе- нии это произведение равно 1

, а в таблице из одних плюсов оно равно 1, поэтому нам не удастся получить таблицу из одних плю- сов, что и требовалось доказать.
71. а) Ответ: нет.
Пронумеруем деревья по кругу с 1 по 44. Сумма номеров дере- вьев, на которых сидят чижи, при каждом перелете либо не изменя- ется, либо изменяется (уменьшается или увеличивается) на 44. Тем самым, сохраняется остаток от деления этой суммы номеров на 44.
Изначально этот остаток равен 22 (сумма равна 990), а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому на одном дереве чижи собраться не смогут. б) Для числа деревьев и чижей n задача решается, если n де- лится на 44, и не решается в противном случае.
72. Рассмотрим и преобразуем выражение:


2 2
2 2
2 2
4 5
2 2
b
a
b
a
a
b
b
a









 






 
, то есть сумма квадратов всех данных чисел увеличилась. При каж- дом следующем выполнении указанной в условии операции сумма квадратов чисел либо увеличивается, либо не изменяется (если хо- тя бы одно из чисел, к которым применяется операция, равно ну- лю). Значит, мы уже не сможем получить исходный набор чисел, что и требовалось доказать.
73. Если открытая монета лежит так же, как и сначала, то она перевернута четное число раз, если же она лежит иначе, то нечет- ное. Петя знает, сколько раз переворачивались монеты (по количе- ству сказанных «Хоп!»). Знает он также четное или нечетное коли- чество раз переворачивались незакрытые монеты (если монета пе- реворачивалась четное число раз, то она лежит так же, как перво- начально; если монета переворачивалась нечетное число раз, то ее положение изменилось на противоположное). Таким образом, он может определить, четное или нечетное количество раз перевора- чивалась закрытая монета, а значит, сможет сказать, как она лежит.

74 74. Ответ: нельзя.
Занумеруем лампы, начиная с горящей, по кругу числами от 1 до 12. Рассмотрим лампы с номерами 1, 2, 4, 5, 7, 8, 10, 11. Изменяя состояние любых трех ламп, мы изменим состояние ровно двух ламп из рассматриваемых. Среди них изначально горит одна лампа.
Поскольку меняем каждый раз состояние ровно двух ламп из ука- занных, количество горящих ламп среди них всегда будет оста- ваться нечетным.
75. Ответ: нельзя.
Предположим, что можно собрать все шашки в одном секторе.
Занумеруем сектора числами от 0 до 5, начиная с того, в котором собрали шашки. Тогда шашки, которые стояли в секторах с четны- ми номерами, передвинуты четное число раз (независимо от того, в каком направлении их двигали, сколько раз меняли направление и т.д.), а шашки, стоявшие в секторах с нечетными номерами – не- четное число раз. Общее количество «передвижений» шашек полу- чается нечетным, а так как за один раз передвигается 2 шашки, то это количество должно быть четным. Полученное противоречие опровергает наше предположение.
76. Ответ: 2.
Произведение чисел на доске не меняется. Действительно,
ab
b
a
b
a




/
1
/
1 2
2
. Поэтому искомое произведение равно
2 2
1


77. а) Ответ: можно.
Сначала перекрасим на противоположный цвет все клетки не- четных строк, разбив их на пары (по горизонтали). Тогда получит- ся, что чередуются белые и черные столбцы. Теперь можно пере- красить клетки белых столбцов, разбив их на пары по вертикали. б) Ответ: нельзя, если угловые клетки белого цвета; можно, если угловые клетки – черные.
Рассмотрим случай с белыми угловыми клетками. На доске размером
9 9

всего 81 клетка, из которых 41 белая, 40 черных.
Чтобы получить доску черного цвета, каждую черную клетку нуж- но перекрасить четное число раз (возможно, 0), каждую белую – нечетное количество раз, всего получается нечетное число пере-

75 крашиваний. Но каждый раз перекрашивается две клетки, поэтому общее число перекрашиваний – четное.
Покажем, как перекрасить доску размером
9 9

с черными уг- ловыми клетками. Занумеруем строки числами от 1 до 9, а столбцы буквами: a, b, c, d, e, f, g, h, i. Перекрасим сначала клетки в столб- цах a и b, h и i с четными номерами, клетки в столбцах c и d, f и g с нечетными номерами, получим столбцы a, d, f, i черного цвета, столбцы b, с, g, h – белого, в столбце e цвет клеток чередуется. За- тем перекрасим клетки в четных строках в столбцах e и f, затем в столбце f перекрасим клетки 12, 13 и 16, 17. Останется перекрасить клетки 13, 14 и 17, 18 в столбце f, а также столбцы b, с, g, h – цели- ком, разбив клетки на пары. В результате получим черную доску.
78. Назовем характеристикой колоды количество имеющихся в ней карт той масти, которой в колоде осталось больше всего. При каждом ходе характеристика либо не меняется, либо уменьшается на 1 (полуинвариант). В последнем случае, очевидно, берется карта загаданной масти. Осталось заметить, что в начале игры характери- стика колоды равнялась 13, а в конце – 0, так что по ходу игры она уменьшалась 13 раз.
79. Сумма всех попарных расстояний между домами есть ве- личина постоянная (инвариант). Предположим, что в результате обмена расстояния между новыми домами для каких-то пар жите- лей стали больше, чем между старыми домами (уменьшиться ни одно из них не могло по условию), тогда сумма попарных расстоя- ний между домами должна также увеличиться, что невозможно.
Полученное противоречие показывает, что в результате обмена расстояние между домами любых двух жителей города не измени- лось, что и требовалось доказать.
80. Ответ: нельзя.
Пусть на доске написано число abcd . Тогда рассматриваемые операции не изменяют число M , где
)
(
)
(
c
a
d
b
M




, так как они увеличивают (или уменьшают) на единицу одно число из пер- вой скобки и одно число из второй. Для числа 1234 число M равно двум:
2
)
3 1
(
)
4 2
(
1234





M
, для числа 2010 число M равно
3

:
3
)
1 2
(
)
0 0
(
2010






M
. Поэтому требуемое невозможно.

76
5. Раскраска
83. Ответ: нельзя.
Предположим, что можно сложить. Тогда если раскрасить по- лученный прямоугольник в шахматном порядке, то должно быть 10 белых и 10 черных клеток. С другой стороны, если раскрасить дан- ные фигуры в шахматном порядке, каждая из фигур, кроме одной, будет содержать 2 белых и 2 черных клетки. Т-образная фигура будет содержать 3 клетки одного цвета и 1 клетку другого цвета.
Таким образом, не удастся получить равное количество белых и черных клеток.
84. Раскрасим комнаты в шахматном порядке (рис. 20). Получится 18 комнат черного цвета и 16 комнат (не считая бассейна) белого цвета. Проходя через дверь в стене, переходим из комнаты од- ного цвета в комнату другого цвета. По- лучается, что в последовательности ком- нат происходит чередование цветов, зна- чит, в цепочке ч, б, ч, б, … количество черных и белых комнат будет либо оди- наковым (если начало и конец цепочки разные по цвету), либо отличаться на 1
(если начало и конец совпадают по цве- ту). Поэтому пройти 18 комнат черного цвета и 16 комнат белого цвета не удаст- ся.
85. Ответ: 31 зал.
Раскрасим залы в два цвета в шахматном порядке (рис. 21). За- лов белого цвета будет 15, черного – 21. Поскольку цвета залов в цепочке чередуются (см. решение задачи 84), то всего в ней не бо- лее
31 16 15


зала. Чтобы осмотреть 31 зал можно начать обход с углового зала, идти вдоль стены, не заходя в последний зал, перей- ти в следующий ряд залов и т.д.:
31 1
2 4
6 8
10






86. Ответ:
1 2


k
k
Раскрасим треугольнички в шахматном порядке (рис. 21). Тре-
Рис. 20
Б
Рис. 21

77 угольников одного цвета будет
2
)
1
(
)
1
(
2 1






k
k
k
, другого
2
)
1
(
2 1
k
k
k





. Поскольку цвета треугольничков в цепочке чередуются, то всего в ней не более
1 1
2
)
1
(
2
)
1
(
2







k
k
k
k
k
k
треугольников.
87. Ответ: нет.
Раскрасим кубики в два цвета в шахматном порядке, тогда без учета центрального кубика получится 14 кубиков одного цвета и 12 кубиков другого цвета. Так как любые два соседних кубика, име- ющих общую грань, будут иметь разные цвета, то хотя бы один кубик останется несъеденным.
88. Раскрасим доску в два цвета в шахматном порядке, чтобы получилось 13 черных и 12 белых клеток. Поскольку соседние клетки имеют разные цвета, жуки с черных клеток перелетели на белые, а с белых – на черные. Значит, на 13 черных клеток перелетели 12 жуков, и хотя бы одна черная клетка освободилась.
89. Ответ: Можно (см. рис. 22).
90. Раскрасим клетки игровой доски в чер- ный и белый цвета в шахматном порядке. То- гда при каждом ходе цвет клетки, в которой находится пустое поле, меняется. Изначально пустое поле находится в правой нижней клет- ке, которая, допустим, окрашена в белый цвет.
Значит, после каждого нечетного хода пустое поле находится на черной клетке, а после чет- ного – на белой. В результате оно оказалось на белой клетке, значит, всего было сделано чет- ное число ходов.
91. Ответ: нельзя.
Раскрасим фигуру в шахматном порядке в три цвета (см. рис. 23). Если предположить, что удастся фигуру замостить двадцатью прямыми тримино, то каждая тримино (независимо от ее расположения в фигуре) должна содер- жать клетки всех трех цветов. Таким образом, в фигуре должно
Рис. 22
Рис. 23

78 быть по 20 клеток каждого цвета. Легко посчитать, что в фигуре 20 клеток одного цвета, 19 другого и 21 – третьего. Полученное про- тиворечие доказывает, что нельзя выполнить требуемое.
92. Ответ: нельзя.
Начав с поля 1
a , конь должен сделать в соответствии с услови- ем задачи всего 63 хода. При каждом ходе коня цвет поля меняется на противоположный, после 63 ходов цвет поля должен быть про- тивоположным цвету поля 1
a , а поле 8
h имеет тот же цвет.
93. Указание: используйте раскраску в три цвета, сравните ко- личество клеток одного цвета в первоначальном варианте и после замены одной фигурки.
94. Ответ: нет.
Выполним шахматную раскраску прямоугольника. Черных и белых клеток по 66. Если предположить, что можно разрезать пря- моугольник на Т-тетрамино, то получатся тетра- мино двух видов (см. рис. 24). Предположим, что тетрамино первого вида – m , второго вида – n .
Тогда черных клеток в прямоугольнике будет
)
1
(
66 3


n
m
, а белых –
)
2
(
66 3


n
m
. Сложив равенства (1) и (2) и разделив полученное равенство на 4, получим
33


n
m
. Если же вычесть из (1) равенство (2) и преобразовать полученное равенство, то получим
n
m

. Но тогда сумма m и n должна быть четной, и не может быть равна 33.
95. Ответ: нет.
Указание: для доказательства используйте раскраску доски в 4 цвета (см. решение задачи 82).
96. Ответ: можно.
Поскольку при каждом ходе «слоненка» меняется номер ряда, в котором он находится, можно нечетные горизонтальные ряды покрасить одним цветом, а четные – другим.
97. Предположим, что в разных строках клеток одного цвета разное количество. Посчитаем наименьшее возможное количество клеток одного цвета во всей таблице:
105 14 2
1 0





. По- скольку в таблице находятся клетки трех цветов, то всего в таблице не менее
315 3
105


клеток. На самом деле клеток
225 15 15


98. Рассмотрим на прямой две произвольные точки
X и Y , окрашенные в один цвет. Рассмотрим также три следующие точки:
Рис. 24

79 точку
1
X – образ точки
X относительно Y ,
1
Y – образ точки Y относительно X и точку O – середину отрезка XY . Если хотя бы одна из этих трех точек окрашена в тот же цвет, что и точки X и
Y , то она вместе с ними образует искомую тройку. Если все эти три точки окрашены в другой цвет, то они будут искомой тройкой.
6. Наибольшее, наименьшее
101. а) Ответ: 8.
Пример размещения восьми ладей в соответствии с условием задачи представлен на рис. 25. Покажем теперь, что невозможно поставить более восьми ладей. В каждом горизонтальном ряду можно поставить не более одной ладьи, иначе они будут бить друг друга, всего рядов 8, поэтому всего может быть не более 8 ладей. б) Ответ: 14.
Пример расположения 14 слонов на доске в соответствии с условием задачи приведен на рис. 26. Покажем теперь, что невоз- можно поставить более 14 слонов. Посчитаем количество диагона- лей на доске (в одном направлении). Их 15. В каждой диагонали может находиться не более одного слона. Кроме того, две крайние диагонали состоят каждая из одной точки, причем слоны, стоящие в них, бьют друг друга. Поэтому на 15 диагоналях могут стоять не более 14 слонов. в) Ответ: 32.
Конь, стоящий на белой клетке, бьет только черные клетки, по- этому коней можно поставить на все клетки одного цвета, они не буду бить друг друга. Покажем, что более 32 коней поставить на доску нельзя. Разобьем шахматную доску на 8 прямоугольников
Рис. 25
Рис. 27
Рис. 28
Рис. 26

80 размером
4 2

(рис. 27). В таком прямоугольнике можно разме- стить не более 4 коней, покажем это. Раскрасим клетки прямо- угольника в 4 цвета (рис. 28), на клетки одного цвета нельзя одно- временно поставить коней, т.к. они будут бить друг друга. Итак, в прямоугольнике не более 4 коней, прямоугольников 8, поэтому всего не более 32 коней.
102. Ответ: 3 хода.
Покажем, что за 3 хода можно перевернуть все карточки. За- нумеруем карточки числами от 1 до 7. Первым ходом перевернем карточки с первой по пятую, вторым – со второй по шестую. В ре- зультате перевернутыми окажутся первая и шестая карточки. Тре- тьим ходом перевернем оставшиеся пять.
Теперь докажем, что меньшим числом ходов не обойтись. Оче- видно, что за один ход не перевернуть все карточки. Остается дока- зать, что двух ходов тоже не достаточно. Первым ходом перевора- чиваются любые пять карточек, после чего неперевернутыми оста- нутся две. Значит, делая второй ход, мы вынуждены перевернуть не менее трех карточек, перевернутых за первый ход, и они ока- жутся в первоначальном положении. Значит, за два хода не удастся добиться требуемого результата.
103. Ответ: 10.
Приведем пример, содержащий 10 дробей с целыми значения- ми:
3 6
,
4 12
,
2 14
,
5 15
,
8 16
,
13 17
,
9 18
,
1 19
,
10 20
,
7 21
,
11 22
. Покажем, что все 11 дробей не могут иметь целые значения. Среди данных чисел три числа (13, 17, 19) могут образовывать дробь, принимающую целое значение, только с единицей. Поскольку карточку с числом 1 мож- но использовать только один раз, не менее одной дроби будет принимать нецелое значение.
104. Ответ: 11.
Пример размещения 11 прямоугольников пред- ставлен на рис. 29. Если предположить, что можно расположить 12 уголков, то всего будет 36 клеток, а в прямоугольнике размером
7 5

всего 35 клеток.
105. Ответ: 9.
Рис. 29
Рис. 30
Рис. 31

81
Пример покраски представлен на рис. 30. Для оценки разобьем доску на квадраты размером
2 2

(рис. 31). В каждом таком квад- рате может быть не более одной покрашенной клетки, т.к. все клет- ки одного квадрата имеют общую точку. Поскольку всего квадра- тов 9, то и клеток не может быть более девяти.
106. Ответ: 24.
Покажем, что 24 выстрелов хватит. Произведем выстрелы по полям, отмеченным на рис. 32а. Любое положение корабля
4 1

накрывает одно отмеченное поле. Поэтому 24 выстрелов хватит.
Покажем, что меньшего числа вы- стрелов не хватит.
Разместим на доске
24 корабля
4 1

(рис. 32б). В каждый из них должен по- пасть выстрел. Зна- чит, нужно сделать не менее 24 выстре- лов.
107. Ответ: 6.
Легко проверить, что монеты достоинством в 1, 3, 5, 7, 9 и 10 рублей удовлетворяют условию задачи. Покажем, что пяти типов монет не хватит. В самом деле, имея пять типов монет, мы сможем с соблюдением условий задачи уплатить не более 20 денежных сумм: 5, беря по одной монете; 5, беря по две одинаковые монеты; и еще не более 10, беря по две различные монеты. Поскольку тре- буется, чтобы мы могли уплатить ровно 20 различных сумм, все перечисленные выше суммы должны быть различными. Кроме то- го, поскольку все суммы, которые требуется уплатить, равны цело- му числу рублей, каждая из монет должна быть достоинством в целое число рублей (она тоже составляет одну из искомых сумм).
Поэтому обязательно должна быть монета достоинством в 1 рубль.
Тогда двухрублевой монеты нет (иначе сумму в 2 рубля можно бы- ло бы уплатить двумя способами), а трехрублевая обязательно есть, четырехрублевой нет (
1 3
4


), а пятирублевая есть. Но тогда по- лучается, что сумму в 6 рублей можно составить двумя способами:
3 3
1 5
6




. Значит, сделать 20 сумм различными не удастся.
Рис. 32 а б

82 108. Ответ: за четыре взвешивания.
Докажем сначала, что трех взвешиваний может не хватить, чтобы наверняка отыскать все фальшивые монеты. Занумеруем монеты по порядку слева направо: 1,2, …, 96. Самая левая фальши- вая монета может иметь номер от 1 до 78 – всего 78 вариантов. По- сле каждого взвешивания может быть три результата: перевесила левая чаша весов, перевесила правая чаша, весы находятся в равно- весии. Значит, после первого взвешивания фальшивая монета с ми- нимальным номером находится (в зависимости от результата) в одном из трех множеств. При этом в одном из них не менее
26 3
:
78

элементов. Если монета оказалась именно в этом множе- стве, то после второго взвешивания указанная монета находится в одном из трех множеств, большее из которых содержит не менее 9 элементов (
8 3
:
26

). Аналогично после третьего взвешивания мо- нета может оказаться в множестве, содержащем не менее
3 3
:
9

элементов, то есть не определяется однозначно. Таким образом, трех взвешиваний недостаточно.
Покажем теперь, как найти все фальшивые монеты за четыре взвешивания. При первом взвешивании положим на левую чашу весов 27 монет с номерами 1, 2, …, 27, а на правую – 27 монет с номерами 70, 71, …, 96. Если весы будут находиться в равновесии, то все эти монеты – настоящие, а фальшивые – какие-то 19 лежа- щих подряд монет из оставшихся 42 монет (для удобства будем считать, что фальшивые монеты – среди 45 монет с 28-й по 72-ю, хотя про монеты 70, 71, 72 уже точно известно, что они настоя- щие). Если при первом взвешивании перевесит, например, правая чаша (случай с левой чашей аналогичен), то на левой чаше была хотя бы одна фальшивая монета, то есть фальшивые монеты – ка- кие-то 19 монет из 45 монет (с 1 по 45). При втором взвешивании положим на левую чашу девять монет с наименьшими номерами
(из 45 подозрительных монет), а на правую – девять монет с наибольшими номерами (из тех же 45 монет). Разбирая возможные исходы этого взвешивания, аналогично предыдущему, получим 9 вариантов для самой левой фальшивой монеты, то есть остаются подозрительными 27 монет (среди них 19 фальшивых). При треть- ем взвешивании положим на левую чашу три монеты с наимень- шими номерами (из 27 подозрительных монет), а на правую – три

83 монеты с наибольшими номерами (из тех же 27 монет). Разбирая возможные исходы этого взвешивания, аналогично предыдущему получим три варианта для самой левой фальшивой монеты, то есть остаются подозрительными 21 монета. Теперь осталось сравнить веса крайних монет (из оставшихся подозрительными 21 монеты).
109. Ответ:
3

n
Пример для
3

n
очевиден (годится любая расстановка).
Предположим, что при некотором
3

n
удалось найти расстанов- ку, удовлетворяющую условию задачи. Тогда после каждого четно- го числа против хода часовой стрелки стоят два числа одинаковой четности (сумма двух чисел разной четности нечетна и не может делиться на четное число). Рассмотрим два случая. 1) Хотя бы для одного четного числа оба его «предшественника» четны. Тогда рассмотрим ближайшее к ним против хода часовой стрелки нечет- ное число. Следующие за ним по ходу часовой стрелки два числа четны, но «нечет» + «чет» не может делиться на «чет». 2) Для каж- дого четного числа оба его «предшественника» нечетны. Тогда между каждыми двумя четными числами стоит, по крайней мере, два нечетных. Если четных чисел на окружности k то нечетных – не меньше k
2 . Но разность между количеством нечетных и коли- чеством четных чисел не больше 1, следовательно
1

k
, тогда
3

n
110. Ответ:
14

N
Заметим, что изображения чисел
1111, 2112 и 2122 не могут иметь об- щих единиц, а изображения чисел 2222,
1221 и 1211 – общих двоек. Следова- тельно, если все эти числа встречаются среди изображенных, то по кругу должны располагаться не менее 14 цифр – 7 единиц и 7 двоек. Пример расположения цифр для
14

N
пока- зан на рис. 33.