МАТЕМАТИЧЕСКИЕ ЗАДАЧИ С РЕШЕНИЕМ. Часть 3
Математические задачи с решениями: расчетные, головоломные и на стратегии математических игр. Источники разнообразные, только решения таких задач не является объектом авторского права.
В квадрате со стороной 10 отметили 201 точку. Докажите, что какие-то три из отмеченных точек можно накрыть квадратом со стороной 1.
Решение:
Разобьем данный квадрат на 100 квадратов со стороной 1 — это будут клетки. По принципу Дирихле в какой-то из них попадет не менее трех точек.
Можно ли занумеровать вершины куба числами от 1 до 8 так, чтобы суммы чисел на концах каждого ребра куба были различными?
Решение:
Посчитаем количество возможных сумм (они и будут клетками). Суммы чисел на концах ребер могут принимать значения от 1+2=3 до 7+8=15 — всего 13 различных значений, а ребер у куба 12, т. е. реальных сумм на ребрах только 12 (они будут кроликами).
На первый взгляд получается, что ответ на вопрос задачи положительный. Но при внимательном рассмотрении оказывается, что суммы 3, 4, 5 и 6 все четыре на ребрах куба получиться не могут.
Для доказательства этого факта рассмотрим вершину, в которой записано число 1. Тогда, чтобы получить на ребрах суммы 3, 4 и 5, в трех соседних с единицей вершинах должны стоять числа 2, 3 и 4. Но тогда невозможно получить сумму 6 (6=1+5=2+4), поскольку рядом с единицей уже нет свободных ребер, а цифры 2 и 4 уже находятся на разных ребрах. Значит, клеток уже не 13, а 12.
Аналогично можно доказать, что из сумм 12, 13, 14 и 15 одна получиться не может. Следовательно, клеток не больше 11, а кроликов 12. Значит, по принципу Дирихле одна из сумм обязательно повторится на двух ребрах.
Ответ: нельзя.
Мама испекла печенье на полдник для Светы. В первый день Света съела половину всего испеченного печенья. На второй день она съела половину от того, что осталось. На третий день — одну четверть остатка, а на четвертый — одну треть. На пятый день она довольствовалась половиной того, что осталось, а на шестой день доела одно последнее печенье. Какое количество печенья испекла мама Светы?
Решение:
Начнем с конца задачи и пойдем в обратном порядке:
В 6 день Света съела одно последнее печенье, значит было 1 печенье;
В 5 день она съела 1/2, значит было 2 печенья;
В 4 день она съела 1/3, значит было 3 печенья;
В 3 день она съела 1/4, значит было 4 печенья;
В 2 день она съела 1/2, значит было 8 печений;
В 1 день она съела 1/2, значит было 16 печений.
Таким образом, вначале у Светы было 16 печений. Обратите внимание на то, что при вычислениях от обратного необходимо изменять используемые операции на «обратные». Вместо деления пополам мы должны удваивать, вместо сложения — вычитать и т.д. Это довольно легкий процесс.
Путешественник собирается пересечь пустыню пешком. На это требуется шесть дней, но он может взять продовольствия и воды только на четыре дня. К счастью, местная деревня готова снабжать его носильщиками (каждый из которых обладает такой же грузоподъемностью и потребляет такое же количество провизии, что и сам путешественник). Какое наименьшее количество носильщиков нужно путешественнику, чтобы пересечь пустыню? (Оставлять носильщиков на верную смерть в пустыне без еды и воды нельзя.)
Решение:
Путешественнику потребуется только 2 носильщика. Первого из них надо отпустить домой на второй день, а второго — на третий день путешествия:
1. Путешественник и два носильщика выходят из деревни, неся в совокупности запаса провианта на 12 дней.
2. В течение первого дня они тратят трехдневный запас, и однодневный запас остается первому носильщику, который сразу же отправляется домой. Таким образом, к началу второго дня у путешественника и второго носильщика остается провизии на 8 дней.
3. В течение второго дня они тратят двухдневный запас провианта, и двухдневный запас остается второму носильщику, который сразу же отправляется домой. Таким образом, к началу третьего дня путешественник остается в одиночестве, но оставшегося запаса провизии ему хватит как раз на четырехдневный переход через пустыню.
Решение:
Ответ:
На листке написаны все неотрицательные целые числа, не превосходящие 100. За один ход можно стереть любые два числа 𝑏 и 𝑏 и записать число 𝑏𝑏. В конце осталось одно число. Чему оно может быть равно?
Решение 1:
На доске написаны числа 0, 1, …, 100 (не забываем про 0!). Заметим, что при такой операции произведение всех чисел – инвариантно, поэтому в конце осталось число равное произведению чисел, то есть 0.
Решение 2:
Заметим, что на доске всегда останется ноль (это и есть инвариант). Действительно, если мы не делаем операцию с нулем, то он остается на доске, а если мы используем в нашей операции ноль, то результат произведения будет равен нулю, то есть мы запишем ноль на доску. Так как в конце осталось одно число, а ноль всегда присутствует, то оставшееся число равно нулю.
Разменный автомат меняет одну монету на пять других. Можно ли с его помощью разменять одну монету на 100 монет?
Решение 1:
Заметим, что за каждый ход у нас количество монет увеличивается на 4. Выпишем первые числа, которые будем получать: 1, 5, 9, 13, …. Давайте докажем, что все числа, которые мы можем получить, меняя монеты, нечетные.
Действительно, изначально монета одна, число монет нечетное. Каждый раз число монет увеличивается на четное число (на 4), поэтому четность количества монет не поменяется и останется нечетной. Так как 100 – четное, его получить нельзя.
Решение 2:
Заметим, что количество монет дает остаток 1 при делении на 4. Действительно, изначально монета одна, а дальше за одну операцию мы прибавляем 4 монеты к нашему количеству, что не меняет остаток при делении на 4. Но 100 дает остаток ноль при делении на 4, таким образом, это количество получиться не могло.
Дана доска 8 × 8, раскрашенная в шахматном порядке. За одно действие можно выбрать любые две соседние клетки и перекрасить их в противоположные цвета: белые в черный, а черные в белый. Можно ли за несколько действий оставить на доске ровно одну черную клетку?
Решение:
Попробуем решить задачу следующим образом. Берем две соседние клетки, черную и белую, перекрашиваем. Заметим, что было 32 белые и 32 черные клетки, столько же и стало. Ну все, значит, количество не меняется, а так как нам нужно получить одну черную клетку, то это невозможно.
Мы сделали следующую логическую ошибку: мы проверили, что после первого действия ничего не поменялось и утверждаем, что ничего не поменяется всегда, но это неправда!
Конкретно в этой задаче, после первого хода, могут образоваться две соседние белые клетки, поэтому наше рассуждение будет неверным. Приведем правильное решение.
Решение. Давайте рассмотрим несколько вариантов, а именно, как могли перекраситься две соседние клетки.
ББ → ЧЧ
БЧ → ЧБ
ЧЧ → ББ
Заметим, что после перекрашивания четность количества черных клеток не меняется.
В начале черных клеток 32 – четное количество, поэтому получить одну черную клетку не получится.
В системе Зеленой Собаки 2013 планет. На каждой из этих планет сидит астроном и смотрит в телескоп на ближайшую планету. Докажите, что если попарные расстояния между планетами различны, то найдется планета, на которую никто не смотрит.
Решение:
Рассмотрим две планеты A и B, расстояние между которыми наименьшее. Астроном на планете A смотрит на планету B, а астроном на планете B смотрит на планету A.
Если астроном с какой-нибудь другой планеты смотрит на одну из планет A или B, то, поскольку планет и астрономов одинаковое количество, а на одну из планет смотрят два астронома, найдется планета, на которую никто не смотрит.
Предположим, что ни один астроном с других планет не смотрит на планеты A и B. Тогда эти планеты можно исключить из рассмотрения и перейти к системе из 2011 планет.
Проводя аналогичные рассуждения, мы каждый раз будем уменьшать количество планет в системе на две планеты и постепенно придем к системе из трех планет. Выберем две из них, расстояние между которыми наименьшее, и получим, что на третью планету никто не смотрит. (В этой задаче крайним было наименьшее расстояние между планетами.)
Шоколадка имеет углубления в виде двух продольных и трех поперечных канавок, по которым ее можно разламывать. Какое наименьшее число разломов необходимо, чтобы разломать ее на кусочки, не имеющие канавок, если одним разломом можно ломать и несколько кусков, приложив их друг к другу?
Решение:
Так как каждый разлом может удвоить число кусков, а в результате мы должны получить 12 кусочков, то трех разломов недостаточно:
1) после первого разлома станет 2 куска;
2) после второго разлома станет максимум 4 куска;
3) после третьего разлома станет максимум 8 кусков.
Нам нужно получить 12 кусочков, значит, минимально необходимое число разломов — четыре. Осталось привести пример:
1) первым разломом разделить шоколадку на два одинаковых куска размером 2х3 и положить их друг на друга;
2) второй разлом разделит каждый из этих кусков на куски размером 1х3, также положим их все друг на друга;
3) третьим разломом отломим от каждого из них по кусочку размером 1х1;
4) четвертым разломом разломам оставшиеся куски размером 1х2 пополам.
Ответ:четыре.
16 учеников сидят за круглым столом, причем больше половины из них — девушки. Докажите, что какие-то 2 девушки сидят друг напротив друга.
Решение:
Образуем 8 пар, в каждую из которых входят ученики, сидящие друг напротив друга. Тогда роль клеток будут играть пары, а роль кроликов — девушки. Поскольку девушек более половины, т.е. не меньше 9, то по принципу Дирихле найдется пара, в которой окажутся 2 девушки.
Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.
Решение:
Вариантов числа знакомых всего 5: от 0 до 4. Однако, если у кого-то 4 знакомых, то ни у кого не может быть 0 знакомых. Поэтому остается только 4 варианта: либо от 0 до 3, либо от 1 до 4. Возможное количество знакомых — клетки (их 4), а люди — кролики (их 5). Значит, по принципу Дирихле найдутся два человека с одинаковым количеством знакомых.
Из девяти монет одна фальшивая, она легче остальных. Как за два взвешивания на чашечных весах без гирь определить, какая монета фальшивая?
Решение:
Разделим монеты на три кучки по три монеты в каждой. Поскольку фальшивая монета только одна, то она окажется в одной из кучек, а в двух других будут только настоящие монеты. Поэтому кучка с фальшивой монетой будет легче двух других, которые будут весить одинаково. Определим сначала кучу, в которой находится фальшивая монета.
Положим первую кучку на левую чашку весов, а вторую кучку на правую чашку весов. Возможны два случая:
1) Чашки весов уравновешены. Значит, эти кучки весят одинаково и в них нет фальшивой монеты. Следовательно, фальшивая монета находится в третьей кучке.
2) Одна из чашек оказалась выше другой. Значит, фальшивая монета именно в этой чашке и лежит.
Итак, мы за одно взвешивание определили кучку, в которой находится фальшивая монета. Поскольку в кучке три монеты, из которых ровно одна фальшивая, предыдущий алгоритм позволит за одно взвешивание определить ее.
Берем две любые монеты из этой кучки и кладем на разные чашки весов. Опять возможны два случая:
1) Чашки весов уравновешены. Значит, эти монеты весят одинаково и среди них нет фальшивой монеты. Следовательно, фальшивой является третья монета.
2) Одна из чашек оказалась выше другой. Значит, фальшивая монета лежит именно в этой чашке.
Таким образом, за два взвешивания мы определили фальшивую монету. При решении задачи мы последовательно делили монеты, среди которых находится фальшивая монета, на три кучки. Этот подход очень часто применяется при решении задач на взвешивание.
Найдите количество трехзначных чисел, в записи которых есть хотя бы один 0.
Решение:
Воспользуемся правилом вычитания. Сначала найдем количество всех трехзначных чисел — это можно сделать и без всякой комбинаторики - их будет 999-99=900. Теперь найдем, сколько из них не содержат ни одного 0: на первое место можно поставить любую из девяти цифр, на второе - любую из девяти цифр и на третье - любую из девяти цифр (каждый раз исключаем 0). Всего по правилу умножения будет 9•9•9=729 вариантов. А теперь найдем ответ по правилу вычитания: 900 – 729 = 171. Сколько трехзначных чисел содержат хотя бы один 0?
Имеется 100 городов, между некоторыми из них проложены дороги с двусторонним движением. Известно, что из любого города можно попасть в любой другой, причем по единственному маршруту. Сколько имеется дорог?
Решение:
Понятно, что число 100 тут ни при чем. Попытаемся построить такие транспортные магистрали вначале для маленького числа городов (двух-четырех), а уж затем попытаемся угадать общий ответ для произвольного числа городов. Для случая двух городов только одна возможность –– соединить города между собой, для трех –– ответ тоже ясен: два ребра из трех возможных должны быть, а третье –– отсутствует (иначе будет два разных маршрута). Интересное замечание: треугольника не может быть и в общем случае по тем же причинам. Значит, граф, отвечающий нашей магистрали, в своем составе не имеет никаких треугольников (напомним, что с точки зрения теории графов треугольник с кривыми сторонами ничем не отличается от треугольников с прямыми –– лишь бы стороны были).
Теперь случай четырех городов. Как бы поудобнее перебрать возможные ситуации? Пожалуй, лучше всего так. Наверняка есть хоть один город, из которого выходят не менее двух дорог. Итак, допустим, что из города А есть дорога в город Б и есть дорога в город В. Между прочим, тогда Б и В между собой не соединены –– получился бы злополучный треугольник. Остался город Д. Тут возможны три ситуации: Д соединен с А, Б или с В. Случаи Б и В совершенно симметричны, так что можно рассматривать только один из них. А вот случай с А от них коренным образом отличается. Нетрудно видеть, что больше ребер быть не может: получится либо треугольник, либо квадрат (а квадрат тоже не подходит: тогда будет два разных маршрута из одного города в другой).
Анализ маленьких случаев мы уже окончили. Попробуем сделать определенные выводы. Первый –– в нашем графе нет циклов, т. е. замкнутых маршрутов. Мы добрались до важнейшего определения: связный граф без циклов называется деревом. Связный означает, что граф нельзя разбить на два, не разрывая его в какой-нибудь вершине. Происхождение слова «дерево» понятно, если нарисовать несколько больших деревьев: явно видны структуры веток. Вывод второй: судя по результатам малой проверки, число ребер на единицу меньше числа вершин, и это можно доказать.
Итак, мы нашли вершину с одной дорогой из нее. Выбросили и ее, и дорогу –– получили меньший граф, для которого все уже можем считать доказанным, например, по индукции. Там уже вершин на одну больше, чем ребер. Значит, и у нас так. Все. Замечаний к решению –– два. Первое –– в виде вопроса: верна ли лемма для бесконечного дерева? Второе замечание касается нашего способа обращения с числом 100, данным в исходной постановке вопроса, которое мы сразу заменили на произвольное число. Что мы выиграли от этого? Получили возможность индукционного рассуждения, во-первых, и анализа маленьких ситуаций, во-вторых.
Вывод: не решайте задачи с большими конкретными числами. Другое дело, что не всегда вместо конкретного числа можно взять любое, но почти всегда –– бесконечный набор однотипно устроенных чисел. Так, например, если в условиях задачи появилось число 2023, то это –– надежный признак одного из двух: либо надо решать задачу с произвольным k, либо использовать какие-то свойства делимости, т. е. по существу решая задачу для произвольного k, делящегося на что-то. Исключения бывают, но редкие.
На листке написаны целые числа от 1 до 20. Можно стереть любые два числа 𝑏 и 𝑏 и записать число 𝑏 + 𝑏. В конце осталось одно число. Чему оно может быть равно?
Решение:
Заметим, что при такой операции сумма всех чисел – инвариантна, поэтому оставшееся число — это просто сумма всех чисел. Осталось ее посчитать 1 + 2 + · · · + 20 = (20·21):2 = 210. Получили, что на доске осталось число 210.
Можно ли расставить числа 1, 2, 3, 4, 5, 6, 7, 8, 9 и 20 в строку так, чтобы в каждой паре соседних одно из чисел делилось на другое?
Решение:
Заметим, что какие-то числа расставлять проще, а какие-то сложнее, например, на единицу делится что угодно, поэтому надо подумать, какое число «особенное» в этой задаче.
Давайте рассмотрим число 7. На него ничего не делится, а 7 делится только на 1, поэтому 7 точно стоит с краю, а рядом с ним 1. А теперь посмотрим теперь на числа 9 и 5. На девять делится только на 3 и 1, а на 9 не делится ничего, а 5 делится на только 1, а на пять делится только 20. Значит, рядом с 1 стоит либо 5, либо 9.
Пусть стоит 5, значит, следом 20, но тогда 9 стоит точно на другом конце, а рядом 3. Дальше все однозначно определяется и получаем такую расстановку: 7, 1, 5, 20, 4, 8, 2, 6, 3, 9.
На самом деле, если бы мы поставили рядом с 1 число 9, то получили бы тоже подходящую расстановку: 7, 1, 9, 3, 6, 2, 8, 4, 20, 5.
Понятно, что, если в задаче вопрос: «можно ли ...?», и вы нашли пример, то нужно только написать: «да, можно» и привести пример.
За круглым столом сидят 25 человек. Им роздано по две карточки. На каждой из 50 карточек написано одно из чисел 1, 2, 3, ... , 25, причем каждое из чисел встречается дважды. Раз в минуту по сигналу ведущего каждый из сидящих передает своему соседу справа ту из своих карточек, на которой написано меньшее число. Если же у кого-то на руках окажутся две карточки с одинаковыми номерами, то процесс заканчивается. Докажите, что это рано или поздно произойдет.
Решение:
Следует проанализировать процесс оседания на руках игрока карточек с большими числами. Рассмотреть сначала игроков с карточкой с самым большим числом, потом с карточкой со вторым по величине числом и т. д.
Если у кого-то из игроков есть две одинаковые карточки, то процесс игры сразу завершен. Поэтому рассмотрим случай, когда у каждого из игроков карточки с разными числами.
Рассмотрим двух игроков с карточками с числом 25. Так как 25 — самое большое из рассматриваемых чисел, то в течение всей игры эти карточки останутся у этих игроков.
Теперь рассмотрим двух игроков с карточками с числом 24. Если эти два игрока не являются игроками с карточками 25, то карточки с числом 24 не будут передаваться, так как к ним в пару не может прийти карточка с большим числом. Если же у игрока с карточкой 25 находится и карточка с 24, то он передаст ее другому игроку. Заметим, что карточка с 24 может передаваться максимум два раза, а потом она осядет на руках игрока, так как не будет карточек с большим номером, которые не осели.
Если обе карточки с 24 осели у одного игрока, то процесс завершился. Рассмотрим ситуацию, когда все 4 карточки с номерами 25 и 24 находятся у четырех разных игроков. Тогда рассмотрим две карточками с числом 23. Если они у одного игрока, то процесс завершился. Если карточка с 23 находится у игрока с карточкой 25 или 24, то она осядет максимум за 4 хода.
Действуя аналогичным образом, дойдем до карточек с числом 13. Если к этому моменту игра не завершилась, то карточки с числами 25, 24, ..., 14 находятся у 24 различных человек. Заметим, что никто из этих 24 человек выиграть не может, поскольку любая пришедшая к ним карточка будет с меньшим числом и ее придется передать дальше.
Рассмотрим последнего игрока, у которого нет карточки с числами 25, 24, ..., 14, и покажем, что в такой ситуации выиграет именно он. Так как первые 24 игрока будут только передавать дальше пришедшие к ним карточки, то, если последний игрок не выиграет раньше, к нему придет карточка с числом 13. Эта карточка осядет у него, так как будет самой большой из передающихся карточек. После этого уже все 25 игроков будут только передавать пришедшие к ним карточки. В результате к последнему игроку придет вторая карточка с числом 13 и игра завершится.
Какое наименьшее количество типов монет должен выпустить Монетный двор России, чтобы любую сумму от 1 до 20 рублей можно было бы уплатить не более чем двумя монетами (без сдачи)?
Решение:
При решении этой задачи мы изменим порядок действий, т. е. сначала приведем пример, а затем покажем, что меньшим количеством типов обойтись нельзя.
Легко проверить, что монеты достоинством 1, 3, 5, 7, 9 и 10 рублей удовлетворяют условию задачи. Покажем, что монет пяти типов не хватит.
Действительно, имея монеты пяти типов, мы сможем, соблюдая условия задачи, уплатить не более 20 сумм:
- не более десяти, беря по две различные монеты;
- пять, беря по две одинаковые монеты;
- пять, беря по одной монете.
Поскольку требуется уплатить ровно 20 различных сумм (1, 2, 3, ... , 20), то все перечисленные выше суммы должны быть различными.
Далее, так как все суммы, которые требуется уплатить, равны целому числу, то и каждая из наших пяти монет должна быть достоинством в целое число рублей. Поэтому должна быть обязательно монета достоинством в 1 рубль.
Тогда двухрублевой монеты быть не должно, иначе сумму в 2 рубля можно будет уплатить двумя различными способами, что запрещено выше.
Трехрублевая монета должна быть, а четырехрублевой монеты быть не должно (4=3+1), но пятирублевая монета должна быть. Тогда получается, что сумму в 6 рублей можно составить двумя способами: 6=5+1=3+3. Следовательно, сделать все 20 сумм различными не удастся. Поэтому монет пяти типов не хватит.
Ответ:
шесть типов монет (1, 3, 5, 7, 9 и 10 рублей).
В непрозрачном мешке лежат 4 красных и 2 зеленых шара. Какое наименьшее число шаров надо вытащить, чтобы среди них оказался:
а) один красный шар;
б) один зеленый шар;
в) один красный и один зеленый шар;
г) два шара одного цвета?
Решение:
Эта задача из тех, в которых придется при решении использовать слова «в худшем случае».
а) В худшем случае мы можем вытащить первые два шара зеленого цвета, тогда в мешке останутся только шары красного цвета и третий шар обязательно будет красным. Значит, надо вытащить три шара. Конечно, может так случиться, что среди вытащенных трех шаров будут два или даже три красных шара, но в худшем случае будет только один красный шар.
б) Рассуждая аналогично, получаем, что надо вытащить 5 шаров.
в) Поскольку красных шаров больше, то в худшем случае первые четыре шара могут оказаться красными и только пятый — зеленым. Поэтому надо вытащить 5 шаров.
г) При кажущейся похожести вопрос этого пункта отличается от трех предыдущих. Этот вопрос ставит классическую задачу на принцип Дирихле. Здесь клетки — цвета, а кролики — шары. Цветов только два. Значит, по принципу Дирихле достаточно вынуть 3 шара, чтобы среди них оказались два одного цвета.
Ответ:
а) 3; б) 5; в) 5; г) 3.