Задача 051. 8 грибников собрали 37 грибов. Известно, что никакие двое не собрали грибов поровну и каждый нашел хотя бы один гриб. Докажите, что какие-то двое из них собрали больше, чем какие-то пятеро.
Решение:
Пронумеруем грибников так, чтобы первый набрал больше всех грибов, второй больше среди оставшихся и т. д. Ясно, что первый не мог набрать меньше 9 грибов, т. к. тогда бы все вместе набрали максимум:
1 + … + 8 = 36 < 37 грибов.
Также второй не мог набрать меньше 7 грибов. Значит, первый и второй вместе набрали хотя бы 7 + 9 = 16 грибов. Учитывая то, что третий набрал хотя бы 6 грибов, то 4-й, 5-й, …, 8-й набрали вместе максимум:
37 – 16 – 6 = 15 < 16 грибов.
Задача 052. Какое наибольшее число прямоугольников 1х5 можно вырезать из квадрата 8х8?
Решение:
Поскольку в квадрате 8х8 всего 64 клетки, а в прямоугольниках, которые требуется вырезать, — 5 клеток, то нельзя вырезать больше 12 квадратов (12·5=60<64, а13·5=65>64).
Осталось показать, как вырезать 12 прямоугольников. Это сделать просто. Оставляем квадрат 2х2 в центре квадрата 8х8, а остальные 60 клеток разбиваем на четыре прямоугольника 3х5, каждый из которых разрезается на 3 прямоугольника 1х5.
Ответ: 12.
Задача 053. В гости пришло 10 человек, и каждый оставил в коридоре пару калош. Все пары калош имеют разные размеры. Гости начали расходиться по одному, надевая любую пару калош, в которые они могли влезть, т. е. каждый гость мог надеть пару калош, не меньшую, чем его собственные. В какой-то момент обнаружилось, что ни один из оставшихся гостей не может найти себе пару калош, чтобы уйти. Какое максимальное число гостей могло остаться?
Решение:
Сначала привести пример, потом сделать оценку. Следует разделить все калоши на маленькие и большие.
Расположим все калоши по возрастанию размеров и назовем первые 5 пар маленькими, остальные 5 пар — большими калошами.
Если гости с маленькими размерами ног наденут большие калоши, то останутся гости с большими размерами ног, которые не смогут надеть маленькие калоши. Это пример, когда 5 гостей не смогут найти себе пару калош, чтобы уйти.
Покажем, что не может остаться 6 гостей. Если осталось 6 пар калош, то среди них есть большие. А среди оставшихся шести гостей точно есть гость с маленьким размером ноги, и он может надеть большие калоши и уйти. Следовательно, максимальное число гостей, которые могли остаться, — это 5.
Ответ: 5.
Задача 054. На шахматной доске расставлены ладьи так, что каждую ладью бьют не более трех других. Найти наибольшее количество ладей.
Решение:
Заметим, что если ладья стоит в углу шахматной доски, то ее бьют не более двух ладей, а если с краю, но не в угловой клетке, то — не более трех. Расставим максимальное число ладей на крайние клетки, получим 28 ладей, каждую из которых бьют не более трех других ладей:
Покажем, что более 28 ладей разместить нельзя. Рассмотрим расстановку ладей, удовлетворяющую условию задачи. Пусть есть ладья, не стоящая с краю. Рассмотрим 4 направления (относительно этой ладьи): вверх, вниз, вправо и влево. Так как эту выбранную ладью бьют не более трех других, то не может быть такого, что по всем 4 направлениям находятся другие ладьи.
Следовательно, эту ладью можно переместить на край доски по направлению, где нет другой ладьи. При этом новая расстановка будет также удовлетворять условию задачи. Проделав эту процедуру несколько раз, мы можем переместить всех ладей на крайние клетки. Так как крайних клеток всего 28 штук, то ладей не может быть более 28.
Ответ: 28.
Задача 055. В квадрате со стороной 10 отметили 201 точку. Докажите, что какие-то три из отмеченных точек можно накрыть квадратом со стороной 1.
Решение:
Разобьем данный квадрат на 100 квадратов со стороной 1 — это будут клетки. По принципу Дирихле в какой-то из них попадет не менее трех точек.
Задача 056. Можно ли занумеровать вершины куба числами от 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. Значит, по принципу Дирихле одна из сумм обязательно повторится на двух ребрах.
Ответ: нельзя.
Задача 057. Задача Монти Холла стала широко известна благодаря телевизионному шоу «Сделай ставку» — игра, которую ведет Монти Холл. Ее правила в упрощенном варианте таковы. Перед игроком три двери. Он знает, что за одной из них — очень ценный приз, например, модный автомобиль. За каждой из двух других — что-то скверное и вовсе нежелательное (например, козел). Игрок не знает, что прячется за каждой дверью (а вот ведущий Монти Холл знает!) и наугад выбирает ту, за которой находится предназначенный ему приз. Но ведущий дразнит игрока, подначивает его сменить свой выбор и всячески старается сбить его с толку.
Задача, получившая известность под названием «Задача Монти Холла», звучит так: Игрок выбирает дверь. Для простоты мы будем считать, что он выбирает дверь номер 3. Прежде чем отворить эту дверь и продемонстрировать, что за ней скрыто, Монти Холл объявляет: «А сейчас я покажу, что прячется за одной из двух оставшихся дверей». Одну дверь открывают — за ней козел. Затем Монти Холл спрашивает: «Не хотите ли изменить свой выбор?» Тут-то и начинается самое интересное: стоит игроку изменить выбор или следует придерживаться первоначального?
Понятно, что игрок не станет выбирать уже отворенную дверь, — за ней рожки да ножки, это никому не интересно. Так что вопрос в том, стоит ли игроку менять свой выбор и указать на оставшуюся дверь (ее не выбрал ни игрок, ни Монти Холл). Простодушный человек может предположить, что козел с равной вероятностью может оказаться и за оставшейся дверью, и за той, на которую первоначально указал игрок. В конце концов, затворены только две двери, за одной прячется козел, за другой — автомобиль; какой смысл в такой ситуации менять свой выбор? Однако простодушный человек не учитывает тот факт, что козлов в задаче два и они отличаются друг от друга.
Решение:
Для решения задачи мы проведем более тщательный анализ, что приведет к поразительному ответу. Решим задачу Монти Холла, рассмотрев все мыслимые случаи.
Обозначим козлов буквами K1 и K2, а автомобиль — буквой A. Для простоты мы будем считать, что первоначально игрок всегда выбирает третью дверь. Однако мы не можем предположить, что Монти Холл всегда отворяет первую дверь, ведь за ней необязательно спрятан козел. Нам следует рассмотреть такие случаи:
В общем случае существует n! различных способов расположить n объектов. Значит, возможно 6 = 3! перестановок трех объектов. Именно поэтому в таблице шесть строк.
В ней перечислены все способы, которыми можно расположить за тремя дверями автомобиль и двух козлов.
1. В первом случае Монти Холл отворит первую или вторую дверь. Игроку нет смысла менять свой выбор, ведь сейчас за выбранной дверью находится автомобиль, так что в этом случае ответ на вопрос задачи — «Нет».
2. Второй случай похож на первый, здесь тоже нет смысла менять выбор; мы опять отвечаем «Нет».
3. В третьем случае Монти Холл отворит первую дверь, за которой прячется козел, так что игроку выгодно изменить свой выбор. В этом случае ответ «Да».
4. Четвертый случай похож на третий, ответ «Да».
5. В пятом случае Монти Холл отворит вторую дверь. Игроку выгоднее изменить выбор, ответ — «Да».
6. Шестой случай похож на пятый, и мы в последний раз даем ответ «Да».
Заметим, что в результате подробного анализа всех случаев мы четырежды получили «Да» и дважды — «Нет». Это означает, что со счетом два к одному выигрывает предложение сменить выбор двери после того, как Монти Холл отворит дверь и явит миру козла. Иначе говоря, с вероятностью 23 игрок улучшит свои шансы на выигрыш, сменив выбор двери.
Задача 058. Мама испекла печенье на полдник для Светы. В первый день Света съела половину всего испеченного печенья. На второй день она съела половину от того, что осталось. На третий день — одну четверть остатка, а на четвертый — одну треть. На пятый день она довольствовалась половиной того, что осталось, а на шестой день доела одно последнее печенье. Какое количество печенья испекла мама Светы?
Решение:
Начнем с конца задачи и пойдем в обратном порядке:
В 6 день Света съела одно последнее печенье, значит было 1 печенье;
В 5 день она съела 1/2, значит было 2 печенья;
В 4 день она съела 1/3, значит было 3 печенья;
В 3 день она съела 1/4, значит было 4 печенья;
В 2 день она съела 1/2, значит было 8 печений;
В 1 день она съела 1/2, значит было 16 печений.
Таким образом, вначале у Светы было 16 печений. Обратите внимание на то, что при вычислениях от обратного необходимо изменять используемые операции на «обратные». Вместо деления пополам мы должны удваивать, вместо сложения — вычитать и т.д. Это довольно легкий процесс.
Задача 059. Путешественник собирается пересечь пустыню пешком. На это требуется шесть дней, но он может взять продовольствия и воды только на четыре дня. К счастью, местная деревня готова снабжать его носильщиками (каждый из которых обладает такой же грузоподъемностью и потребляет такое же количество провизии, что и сам путешественник). Какое наименьшее количество носильщиков нужно путешественнику, чтобы пересечь пустыню? (Оставлять носильщиков на верную смерть в пустыне без еды и воды нельзя.)
Решение:
Путешественнику потребуется только 2 носильщика. Первого из них надо отпустить домой на второй день, а второго — на третий день путешествия:
1. Путешественник и два носильщика выходят из деревни, неся в совокупности запаса провианта на 12 дней.
2. В течение первого дня они тратят трехдневный запас, и однодневный запас остается первому носильщику, который сразу же отправляется домой. Таким образом, к началу второго дня у путешественника и второго носильщика остается провизии на 8 дней.
3. В течение второго дня они тратят двухдневный запас провианта, и двухдневный запас остается второму носильщику, который сразу же отправляется домой. Таким образом, к началу третьего дня путешественник остается в одиночестве, но оставшегося запаса провизии ему хватит как раз на четырехдневный переход через пустыню.
Задача 060. На листке написаны все неотрицательные целые числа, не превосходящие 100. За один ход можно стереть любые два числа 𝑏 и 𝑏 и записать число 𝑏𝑏. В конце осталось одно число. Чему оно может быть равно?
Решение 1:
На доске написаны числа 0, 1, …, 100 (не забываем про 0!). Заметим, что при такой операции произведение всех чисел – инвариантно, поэтому в конце осталось число равное произведению чисел, то есть 0.
Решение 2:
Заметим, что на доске всегда останется ноль (это и есть инвариант). Действительно, если мы не делаем операцию с нулем, то он остается на доске, а если мы используем в нашей операции ноль, то результат произведения будет равен нулю, то есть мы запишем ноль на доску. Так как в конце осталось одно число, а ноль всегда присутствует, то оставшееся число равно нулю.