И. О. Соловьева. Практикум по решению олимпиадных задач по матем. Практикум по решению олимпиадных задач по математике
 Скачать 1.1 Mb.
|
|
Задача 61. На острове Серобуромалин живет 13 серых, 15 бу- рых и 17 малиновых хамелеонов. Если встречаются два хамелеона разного цвета, они одновременно меняют окраску на третий цвет. Может ли случиться, что в некоторый момент все хамелеоны на острове станут одного цвета? Решение. Будем искать инвариант, но сначала надо разобрать- ся, какие операции происходят: два хамелеона двух разных цветов «пропадают» и «появляются» два хамелеона третьего цвета. Обо- значим количество серых, бурых и малиновых хамелеонов соответ- ственно буквами a , b и c . Тогда операция, описанная в условии, означает, что из набора ) , , ( c b a получается набор ) 2 , 1 , 1 ( c b a или набор ) 1 , 2 , 1 ( c b a или набор ) 1 , 1 , 2 ( c b a . Рассмотрев разности между двумя числами набора c b b a , и c a , можно заметить, что они в результате операции либо не меняются, либо изменяются на 3. Значит, остатки от деления разностей на 3 инва- риантны. Первоначально две разности равны –2, а третья –4, все они не делятся на 3. Если же все хамелеоны станут одного цвета, то одна из разностей станет равна 0, будет делиться на 3, что невоз- можно. ■ В некоторых задачах решение основано на использовании по- луинварианта – величины, которая при каждой операции может изменяться только в одном направлении (возрастать или убывать). 22 Задача 62. Вокруг поляны стоят 12 домиков, покрашенные в белый и красный цвета, в которых поселилось 12 гномов. У каждо- го гнома нечетное число друзей. В январе первый гном красит свой дом в тот цвет, в который окрашены дома большинства его друзей. В феврале это же делает второй (по часовой стрелке) и т.д. Дока- жите, что наступит момент, после которого цвет дома у каждого гнома перестанет меняться. Решение. Рассмотрим число пар гномов-друзей, у которых до- ма разного цвета. Каждый месяц это число не увеличивается. Дей- ствительно, если цвет дома сохраняется, то число не меняется, если же цвет дома меняется, то это число уменьшается. Так как это чис- ло неотрицательно, оно не может бесконечно уменьшаться, значит, с того момента, когда оно перестанет меняться, каждый гном будет красить свой дом в один и тот же цвет. ■ Задачи. 63. а) На столе стоят 7 стаканов дном вверх. Разрешено пере- ворачивать одновременно любые два стакана. Можно ли поставить все стаканы дном вниз? б) 9 пятаков лежат гербом вверх. Разреше- но за раз перевернуть любые 8 из них. Можно ли добиться, чтобы все пятаки легли гербом вниз? в) То же для 8 пятаков, переворачи- ваются – 7. 64. 16 корзин расположили по кругу. Можно ли в них разло- жить 55 яблок так, чтобы количество яблок в любых двух соседних корзинах отличалось на 1? 65. У числа 2010! вычислили сумму цифр. У полученного чис- ла опять вычислили сумму цифр, и так до тех пор, пока не получи- лось однозначное число. Какое это было число? 66. На чудо-яблоне растут бананы и ананасы. За один раз раз- решается сорвать с нее два плода. Если сорвать два банана или два ананаса, то вырастет еще один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Можно ли определить, какой это плод, если известно, сколько ба- нанов и ананасов росло вначале? 67. В языке дикарей хотийцев всего два звука: «ы» и «у». Два слова означают одно и то же, если одно получается из другого при помощи некоторого количества следующих операций: пропуска идущих подряд звуков «ыу» или «ууыы» или добавления в любом 23 месте звуков «уы». Означают ли одно и то же слова: «уыу» и «ыуы»? 68. На прямой стоят две фишки: слева – красная, справа – си- няя. Разрешается производить любую из двух операций: вставку двух фишек одного цвета подряд (между фишками или с краю) и удаление пары соседних одноцветных фишек (между которыми нет других фишек). Можно ли с помощью таких операций оставить на прямой ровно две фишки: слева – синюю, а справа – красную? 69. Квадратное поле разбито на 100 одинаковых квадратных участков, девять из которых поросли бурьяном. Известно, что бу- рьян за год распространяется на те и только те участки, у каждого из которых не менее двух соседних участков уже поросли бурья- ном (участки соседние, если они имеют общую сторону). Докажи- те, что это поле никогда не зарастет бурьяном полностью. 70. В одной клетке квадратной таблицы 4 4 стоит знак ми- нус, а в остальных стоят плюсы. Разрешается одновременно менять знак во всех клетках, расположенных в одной строке или в одном столбце. Докажите, что, сколько бы мы ни проводили таких пере- мен знака, нам не удастся получить таблицу из одних плюсов. 71. а) На 44 деревьях, расположенных по кругу, сидит по весе- лому чижу. Время от времени какие-то два чижа перелетают на со- седнее дерево, один – по часовой стрелке, а другой – против. Могут ли все чижи собраться на одном дереве? б) А если чижей и деревьев n ? 72. Дано несколько (не менее двух) ненулевых чисел. Вместо любых двух чисел a и b из этого набора записываются числа 2 b a и 2 a b . Затем эта операция производится с двумя произвольными числами из получившегося набора и т.д. Докажите, что после не- скольких таких операций нельзя вновь получить исходный набор чисел. 73. На столе лежат 22 монеты. Петя закрывает глаза, а Витя переворачивает монеты по одной, говоря при каждом переворачи- вании «Хоп!» (он может переворачивать одну монету несколько раз, не забывая каждый раз сказать «Хоп!»). После этого Витя накрывает одну из монет рукой, а Петя открывает глаза и отгады- 24 вает, как лежит невидимая монета – гербом вверх или вниз. Как Петя это делает? 74. Каждая из расположенных по кругу 12 ламп может нахо- диться в одном из двух состояний: гореть или не гореть. За один ход можно изменить состояние любых трех ламп, расположенных подряд. Вначале горит только одна лампа. Можно ли добиться то- го, чтобы горели все 12 ламп? 75. Круг разбит на 6 секторов. В секторах стоят 6 шашек, по одной в каждом. За один ход разрешается передвинуть две шашки на один сектор каждую (в одинаковых или противоположных направлениях). Можно ли за несколько ходов собрать все шашки в одном секторе? 76. На доске в лаборатории написаны два числа. Каждый день старший научный сотрудник Петя стирает с доски оба числа и пи- шет вместо них их среднее арифметическое и среднее гармониче- ское. Утром первого дня на доске были написаны числа 1 и 2. Найдите произведение чисел, записанных на доске вечером 2010-го дня. (Средним арифметическим двух чисел a и b называется число 2 b a , а средним гармоническим – число b a / 1 / 1 2 ). 77. На шахматной доске разрешается перекрашивать в проти- воположный цвет любые две соседние клетки. Можно ли с помо- щью таких операций перекрасить всю доску в черный цвет? Рас- смотрите случаи размера доски а) 8 8 ; б) 9 9 78. В колоде 52 карты, по 13 каждой масти. Ваня вынимает из колоды по одной карте. Вынутые карты в колоду не возвращаются. Каждый раз перед тем, как вынуть карту, Ваня загадывает какую- нибудь масть. Докажите, что если Ваня каждый раз будет загады- вать масть, карт которой в колоде осталось не меньше, чем карт любой другой масти, то загаданная масть совпадет с мастью выну- той карты не менее 13 раз. 79. Население города состоит из n человек, и каждый живет в отдельном домике. Однажды жители города решили обменяться домами. После обмена выяснилось, что расстояние между новыми домами любых двух жителей не меньше, чем расстояние между их старыми домами. Докажите, что в результате обмена расстояние между домами любых двух жителей не изменилось. 25 80. Написанное на доске четырехзначное число можно заме- нить на другое, прибавив к двум его соседним цифрам по единице, если ни одна из этих цифр не равна 9; либо, вычтя из соседних двух цифр по единице, если ни одна из них не равна 0. Можно ли с по- мощью таких операций из числа 1234 получить число 2010? 5. Раскраска В математических задачах встречаются раскраски фигур. Рас- краска может быть задана условием задачи, в некоторых задачах нужно раскрасить фигуру определенным образом, но чаще встре- чаются задачи, в которых раскрашивание фигуры определенным образом помогает решить задачу. Задача 81. Можно ли разбить на доминошки (каждая – из двух клеток) шахматную доску без противоположных углов а1 и h8? Решение. В этой задаче говорится о шахматной доске, которая уже раскрашена в два цвета. Каждая доминошка, как бы она ни располагалась на доске, состоит из соседних клеточек разного цве- та: черной и белой. Поэтому если бы удалось разбить доску без уг- ловых клеток (всего 62 клетки) на доминошки, то получилось бы поровну (по 31) белых и черных клеток. Клеточки а1 и h8 лежат на одной диагонали и имеют одинаковый цвет, поэтому в оставшейся части шахматной доски клеток одного цвета на две больше, чем другого. Поэтому доску нельзя разбить на доминошки. ■ Чаще всего в задачах на раскраску используется шахматная черно-белая раскраска. Однако может быть использовано и больше цветов. Рассмотрим задачу. Задача 82. Можно ли разрезать шахматную доску без клетки а1 на плитки размером 3 1 ? Решение. Для решения этой задачи выполним «диагональную раскраску» доски в три цвета (рис. 1). При такой раскраске, как бы плитка размером 3 1 не располагалась, она всегда займет по одной клетке каждого из трех цветов. Если бы доску можно было разрезать на такие плитки, то клеток всех цветов было бы поровну, но в нашей рас- Рис. 1 8 7 6 5 4 3 2 1 a b c d e f g h 26 краске клеток одного цвета 22, второго цвета – 21, третьего цвета – 20 клеточек. Следовательно, доску разрезать нельзя. ■ Задачи. 83. Можно ли из пяти фигур, изображенных на рис. 2, сложить прямоугольник размером 5 4 ? 84. Замок состоит из 34 комнат и бассейна (рис. 3), в каждой стене, разделяющей две соседние комнаты, есть дверь. Можно ли, не выходя из замка и не заходя в бассейн, обойти все комнаты, по- бывав в каждой ровно по одному разу? 85. Треугольный замок состоит из 36 одинаковых залов (рис. 4), между любыми двумя залами есть дверь. Какое наиболь- шее число залов сможет осмотреть человек, не желающий нигде побывать более одного раза? 86. Каждая сторона правильного треугольника разбита на k равных частей, через точки деления проведены прямые, параллель- ные сторонам. В результате треугольник разбился на 2 k маленьких треугольничков. Назовем цепочкой последовательность треуголь- ничков, в которой ни один треугольник не появляется дважды и каждый последующий имеет общую сторону с предыдущим. Како- во наибольшее число треугольничков в цепочке? 87. Мышка грызет куб сыра, составленный из 27 единичных кубиков. Когда она съедает кубик, то переходит к соседнему через общую грань с предыдущим. Может ли мышка съесть весь куб кроме центрального кубика? 88. 25 жуков сидели по одному на каждой клетке доски 5 5 . В некоторый момент каждый жук перелетел на одну из соседних кле- ток (соседними считаются клетки, имеющие общую сторону). До- кажите, что хотя бы одна клетка освободилась. Рис. 2 Рис. 3 Б Рис. 4 27 89. Можно ли шахматную доску с вырезанным угловым полем покрыть уголками, изображенными на рис. 5 (уголки можно поворачивать)? 90. Игра «15» представляет собой поле – коробочку размером 4 4 , в ко- торой находятся 15 фишек (квадрати- ков 1 1 ), пронумерованных числами от 1 до 15; при этом одно поле остается пустым (рис. 6). В начале игры пустое поле находилось в правом нижнем углу. Я начал двигать фишки по полю. За один ход я передвигал на пустое поле одну из фишек, находившуюся на соседнем поле. В результате порядок располо- жения фишек изменился, но пустое поле вновь оказалось в правом нижнем углу. Докажите, что я сделал четное число ходов. 91. Можно ли фигуру из 60 клеток (рис. 7) замостить двадца- тью прямыми тримино (рис. 8а; размер клетки тримино совпадает с размером клетки фигуры)? 92. Можно ли обойти шахматную доску ходом коня, побывав на каждом поле по од- ному разу, начав в левом нижнем углу доски (на поле а1) и закончив в правом верхнем (на поле h8)? 93. В прямоугольную коробочку были сложены несколько прямых тримино (рис. 8а) так, что они заполняли ее целиком (коро- бочка такова, что лежащие в ней фигурки не могут налегать друг на друга). Затем одно прямое тримино заменили на тримино- уголок (рис. 8б). Докажите, что образовав- шийся набор не поместится в коробочку. 94. Можно ли прямоугольник 12 11 разрезать на Т-тетрамино (рис. 8в)? 95. Можно ли доску 10 10 разрезать на прямоугольники 1 4 ? 96. Фигура «слоненок» ходит по шахматной доске, как и слон, по диагонали, но только на одно поле. Можно ли перекрасить клет- ки шахматной доски, используя черный и белый цвета, чтобы при каждом ходе «слоненка» цвет поля менялся? Рис. 5 Рис. 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Рис. 7 Рис. 8 а б в 28 97. Клетки таблицы 15 15 окрашены в три цвета. Докажите, что найдутся хотя бы две строки, в которых одинаковое количество клеток какого-то цвета. 98. Прямая раскрашена в два цвета. Докажите, что на ней найдутся три точки A , B и C , окрашенные в один цвет такие, что точка B является серединой отрезка AC . 6. Наибольшее, наименьшее Задачи на нахождение наибольшего или наименьшего значения некоторой величины называют экстремальными. В экстремальных задачах полное решение, как правило, должно содержать: 1) ответ, т.е. наибольшее или наименьшее значение, искомое в задаче, 2) пример, показывающий, что это значение достижимо, 3) оценку, т.е. доказательство того, что это значение действи- тельно является наибольшим или наименьшим. (Важно! Доказа- тельство того, что невозможно достижение большего / меньшего значения, не должно быть связано с построенным примером. Кроме того, оценка не заменяет примера.) Задача 99. Какое наибольшее количество клеток таблицы 8 8 можно покрасить так, чтобы никакие три центра окрашенных кле- ток не лежали на одной прямой? Решение. Можно раскрасить 16 клеток. Пример раскраски, удовлетворяющей условию задачи, приведен на рис. 9. Выполним оценку. Поскольку в каждой строке может находиться не более двух закрашенных клеток, а всего строк 8, то всего можно закрасить не более 16 клеток. ■ Примечание. Доказать, что нельзя раскра- сить большее число клеток, можно и иначе. Предположим противное: можно покрасить не менее 17 клеток. Тогда по принципу Дирихле в какой-то горизон- тали, либо в какой-то вертикали окажется не менее трех окрашен- ных клеток, причем их центры будут лежать на одной прямой, что противоречит условию задачи. Рис. 9 29 Задача 100. Какое минимальное число прямоугольников раз- мером 2 1 клетки нужно закрасить на доске 8 8 клеток, чтобы любой квадрат 2 2 содержал по крайней мере одну закрашенную клетку? Решение. Нужно закрасить 9 прямоугольников, на рис. 10 показан пример. Для доказа- тельства минимальности данно- го ответа рассмотрим вспомога- тельную раскраску доски (рис. 11). Любой из прямо- угольников размера 2 1 пере- секается не более чем с одним из девяти закрашенных квадратов размера 2 2 . Следовательно, нам потребуется закрасить не менее девяти прямоугольников. ■ Задачи. 101. Какое наибольшее количество а) ладей, б) слонов, в) ко- ней, не бьющих друг друга, можно расставить на доске 8 8 ? 102. На столе лежат 7 карточек. За один ход разрешается пере- вернуть любые 5 карточек. Какое наименьшее число ходов необхо- димо совершить, чтобы перевернуть все карточки? 103. На 22 карточках написаны натуральные числа от 1 до 22. Из этих карточек составили 11 дробей. Какое наибольшее число этих дробей могут иметь целые значения? 104. Какое наибольшее количество уголков, состоящих из трех квадратов 1 1 , можно поместить в прямоугольнике 7 5 ? (Уголки нельзя накладывать друг на друга). 105. Какое наибольшее число клеток доски 6 6 можно покра- сить так, чтобы никакие две закрашенные клетки не соприкасались (даже в одной точке)? 106. За какое наименьшее количество выстрелов можно с га- рантией подбить четырёхклеточный корабль в игре «морской бой»? 107. Какое наименьшее количество типов монет должен выпу- стить Монетный Двор России, чтобы любую сумму от 1 до 20 руб- лей можно было бы уплатить не более чем двумя монетами (без сдачи)? Рис. 10 Рис. 11 30 108. В музее города Черноморска имеется коллекция из 96 оди- наковых золотых монет, лежащих в ряд. Однажды был пойман во- ришка Паниковский, у которого обнаружили 19 монет из этой кол- лекции. На следствии он показал, что заменил 19 лежащих подряд монет на фальшивые, которые легче настоящих, но внешне от них неотличимы. За какое наименьшее количество взвешиваний можно отыскать все фальшивые монеты, используя чашечные весы без гирь? 109. Найдите все такие натуральные 3 n , что все целые числа от 1 до n можно расставить по окружности так, чтобы сумма лю- бых двух рядом стоящих чисел делилась на следующее за ними по ходу часовой стрелки число. 110. N цифр – единицы и двойки – расположены по кругу. Изображенным назовем число, образуемое несколькими цифрами, расположенными подряд (по часовой стрелке или против часовой стрелки). При каком наименьшем значении N все четырехзначные числа, запись которых содержит только цифры 1 и 2, могут ока- заться среди изображенных? |