МАТЕМАТИЧЕСКИЕ ЗАДАЧИ С РЕШЕНИЕМ. Часть 4
Математические задачи с решениями: расчетные, головоломные и на стратегии математических игр. Источники разнообразные, только решения таких задач не является объектом авторского права.
Запах от цветущего кустика ландышей распространяется в радиусе 20 м вокруг него. Какое минимальное количество цветущих кустиков ландышей необходимо посадить вдоль прямолинейной 400-метровой аллеи, чтобы в каждой ее точке пахло ландышем?
Решение:
Один ландыш распространяет запах на 20 м в одну сторону аллеи и на 20 м — в другую. Следует поделить аллею на 40-метровые участки.
Так как каждый ландыш распространяет запах на 40 метров аллеи, то надо посадить 400:40=10 ландышей, первый — на расстоянии 20 метров от начала аллеи, второй — на расстоянии 40 от первого, третий — на расстоянии 40 метров от второго и т. д. Последний десятый ландыш будет находиться на расстоянии 20 метров от конца аллеи.
Ответ: 10.
В булке оказался запечен изюм двух сортов. Доказать, что внутри булки (булка содержит внутри себя шар радиуса 1 см) найдутся две такие точки, удаленные на 1 см, что они либо не принадлежат никаким из изюмин, либо принадлежат изюминам одного сорта.
Решение:
Рассмотрим правильный тетраэдр с ребром 1 см, расположенный целиком внутри булки. Для каждой из его вершин есть одна из трех возможностей — либо находиться внутри изюмины одного из двух сортов, либо не принадлежать никакой изюмине. Вершин — 4, а возможностей — 3.
Бесконечный лист бумаги разлинован в клетку. Каждая клетка окрашена в один из шести цветов. Докажите, что всегда найдутся четыре клетки одного цвета, центры которых являются вершинами прямоугольника со сторонами, параллельными прямым линиям на бумаге.
Решение:
Возьмем горизонтальную полосу шириной 7 клеток. Так как число способов окраски конечно, то найдутся два одинаково окрашенных вертикальных столбика. В каждом из них 7 клеток, окрашенных в 6 цветов, поэтому по принципу Дирихле в каждом столбике найдутся 2 одинаково окрашенные клетки, находящиеся на одной диагонали.
Может ли крестьянин перевезти через реку волка, козу и капусту, если в лодку вместе с ним помещается только кто-то один из них? (Нельзя оставить без присмотра ни волка с козой, ни козу с капустой.)
Решение:
Это классическая задача на переправы. При имеющихся ограничениях ее решение довольно просто (козу придется покатать больше других, перевозя ее обратно, раз ее нельзя ни с кем оставить):
1) Сначала крестьянин перевозит козу на другой берег.
2) Затем возвращается один и забирает, например, волка и перевозит его на другой берег.
3) Высадив волка, крестьянин забирает козу и перевозит ее обратно.
4) Высадив козу, крестьянин забирает капусту и перевозит ее на другой берег.
5) Затем крестьянин возвращается за козой и перевозит ее.
За все время коза ни с кем не оставалась — ни с волком, ни с капустой без присмотра крестьянина.
Ответ:Да.
Имеется шесть гирь, выглядящих внешне совершенно одинаково и даже выкрашенных в один и тот же цвет: три гири одного и три гири другого (чуть большего) веса. Как с помощью трех взвешиваний на равноплечих весах определить, к какой из двух категорий — к тяжелым или к легким — относится каждая из этих 6 гирь?
Решение:
Обозначим гири буквами А, Б, В, Г, Д и Е.
Сравниваем между собой гири А и Б.
Если весы в равновесии, то это означает, что среди оставшихся 4 гирь 3 — одного веса. Сравниваем гири Б и В.
1. Если Б = В, то это означает, что гири А, Б и В, а также Г, Д и Е — одного веса. Заключительным взвешиванием сравниваем между собой гири А и Г.
2. Если Б < В, то это означает, что гири А и Б — легкие, В — тяжелая, а среди оставшихся гирь Г, Д и Е есть одна легкая и две тяжелые. Сравниваем между собой гири Г и Д.
Если Г = Д, то А, Б и Е — легкие, а В, Г и Д — тяжелые.
Если Г < Д, то А, Б и Г — легкие, а В, Д и Е — тяжелые.
Если Г > Д, то А, Б и Д — легкие, а В, Г и Е — тяжелые.
3. Б > В. Аналогично предыдущему случаю.
Если одна гиря оказалась легче другой (пусть для определенности А < Б), то это означает, что среди оставшихся 4-х гирь 2 легкие и 2 тяжелые. Сравниваем гири В и Г.
1. Если В = Г, то это означает, что гири В и Г, а также Д и Е — одного веса. Заключительным взвешиванием сравниваем между собой гири В и Д.
2. Если В < Г, то это означает, что среди гирь Д и Е — одна легкая и одна тяжелая. Заключительным взвешиванием просто сравниваем их между собой.
3. В > Г. Аналогично предыдущему случаю.
Веб-сайт просит пользователя создать восьмизначный пароль, содержащий только строчные буквы латинского алфавита, где каждая буква используется только один раз. Определите: сколько существует различных возможных паролей?
Решение:
Для создания такого пароля разрешается применять только строчные буквы латинского алфавита – 26 символов. Каждая буква должна использоваться только один раз. Значит, для определения количества паролей необходимо использовать формулу размещения без повторений.
Тогда, количество размещений из 8 строчных букв латинского алфавита, выбранных из 26, составляет 62990928000 паролей.
Ответ: 62990928000 паролей, содержащих только строчные буквы латинского алфавита, где каждая буква используется только один раз.
Можно ли в квадрате 7×7 закрасить некоторые клетки так, чтобы в любом квадрате 2×2 была ровно одна закрашенная клетка?
Решение:
Возьмем квадрат 8×8 и закрасим в нем клетки, стоящие на пересечении столбца и строки с четным номером. Ясно, что у этого квадрата в любом квадрате 2×2 будет ровно одна закрашенная клетка. Теперь выкинем правый столбец и верхнюю строку. Получим квадрат 7×7, удовлетворяющий условию.
Ответ: да, можно.
Автомобиль едет по шоссе с постоянной скоростью 55 км/ч. Водитель замечает другой автомобиль на расстоянии 0,5 км позади. Второй автомобиль обгоняет первый 1 минуту спустя. С какой скоростью двигался второй автомобиль, если считать, что она была постоянной?
Решение:
Предположим, что первый автомобиль движется чрезвычайно медленно, т.е. со скоростью 0 км/ч. В этом случае второй автомобиль проедет за одну минуту и догонит первый автомобиль. Таким образом, второй автомобиль должен двигаться со скоростью 30 км/ч. Первый автомобиль движется со скоростью 0 км/ч, а второй автомобиль — на 30 км/ч быстрее, чем первый. Если первый автомобиль будет иметь скорость 55 км/ч, то второй — 85 км/ч.
В стране есть несколько городов. Сумасшедший путешественник едет из города A в самый далекий от него город B. Затем едет в самый далекий от B город C и т.д. Докажите, что если город C не совпадает с городом А, то путешественник никогда не вернется обратно в город A.
Решение:
Предположим, что на втором шаге путешественник не возвратился в A, т. е. город C отличен от города A. Тогда маршрут от A до B короче маршрута из B в C (поскольку C — наиболее удаленный от B город). В дальнейшем каждый следующий маршрут будет не короче предыдущего, так как каждый раз мы в качестве следующего пункта назначения выбираем наиболее удаленный город. Пусть на некотором шаге путешественник все же вернулся в город A, выйдя из некоторого города X. По доказанному, маршрут от X до A длиннее маршрута от A до B, а это противоречит тому, что B — наиболее удаленный от A город.
В кинотеатре 7 рядов по 10 мест каждый. Группа из 50 детей сходила на утренний сеанс, а потом на вечерний. Докажите, что найдутся двое детей, которые на утреннем сеансе сидели в одном ряду и на вечернем тоже сидели в одном ряду.
Решение:
Рассмотрим самый заполненный ряд и применим принцип Дирихле. На самом заполненном ряду сидели как минимум 8 детей.
На утреннем сеансе 50 детей разместились на 7 рядах. По принципу Дирихле хотя бы в одном из рядов сидели как минимум 8 детей. Так как рядов всего 7, то как минимум двое из этих восьми детей окажутся в одном ряду на вечернем сеансе.
Дано 12 различных двузначных чисел. Докажите, что из них можно выбрать два числа, разность которых — двузначное число, записываемое двумя одинаковыми цифрами.
Решение:
Сначала заметим, что любое двузначное число, записываемое двумя одинаковыми цифрами, обязательно делится на 11 и, наоборот, если двузначное число делится на 11, то оно записывается двумя одинаковыми цифрами.
Теперь понятно, что клетками будут остатки от деления числа на 11 — различных остатков равно 11, а кроликами будут данные числа — их 12. Тогда, по принципу Дирихле, найдутся два числа, остаток от деления которых на 11 одинаковый. Эти два числа и являются искомыми.
Некоторые из клеток таблицы 5×5 окрашены в красный цвет, остальные в синий. Докажите, что можно найти четыре клетки, окрашенные одним цветом, которые находятся на пересечении двух строк и двух столбцов.
Решение:
Согласно принципу Дирихле, в каждой строке есть не менее трех клеток, окрашенных в один цвет. Так как строк пять, то, опять же по принципу Дирихле, найдутся три, в каждой из которых не менее трех клеток одного цвета.
Пусть для определенности это будут клетки красного цвета. Рассмотрим две из этих трех строк. Если в них нет двух столбцов красного цвета, то найдется один столбец красного цвета, а в остальных четырех столбцах по одной клетке красного и синего цвета. Тогда, добавляя третью строчку, мы обязательно получим требуемое в задаче.
В одной комнате имеется три выключателя, а в другой — присоединенные к ним лампочки, при этом какой выключатель соответствует той или иной лампочке, неизвестно. Разрешается, производя какие-то манипуляции с выключателями, зайти затем в соседнюю комнату. Можно ли при этом установить, какой выключатель соответствует той или иной лампочке?
Решение:
Включаем один выключатель и некоторое время держим его включенным. Затем выключаем, включаем другой и быстро идем в соседнюю комнату. Одна лампочка горит (соответствует второму выключателю), одна лампочка не горит, но зато теплая (соответствует первому выключателю), а третья — ни то, ни другое (соответствует последнему выключателю).
Гриб называется плохим, если в нем не менее 10 червей. В лукошке 90 плохих и 10 хороших грибов. Могут ли все грибы стать хорошими после того, как некоторые черви переползают из плохих грибов в хорошие?
Решение:
Пусть в каждом плохом грибе ровно 10 червей, а в хорошем червей нет. Далее, пусть из каждого плохого гриба по одному червю переползут в хорошие, по 9 в каждый. В результате в каждом грибе окажется по 9 червей, и все грибы будут хорошими.
Ответ: могут.
Даны три кучки камней, по n камней в каждой. За один ход можно выбрать две кучки, убрать из них по одному камню, при этом добавив один камень в третью кучку. При каких n можно через несколько ходов оставить только один камень
Решение:
Давайте возьмем число n = 7 и посмотрим, что мы вообще можем получить.
7 7 7
6 6 8
7 5 7
8 4 6
7 5 5
8 4 4
7 3 5
Заметим, что три числа всегда одной четности. Докажем это.
Пусть у нас были числа Ч Ч Ч, так как все числа изменяются на 1, станет Н Н Н. Аналогично, если было Н Н Н, так как все числа изменяются на 1, станет Ч Ч Ч. Таким образом, 0 0 1 мы получить не сможем.
По кругу записано 100 чисел, каждое из которых равно среднему арифметическому своих соседей. Докажите, что все 100 чисел равны.
Решение:
Рассмотрим наибольшее из записанных чисел. Если таких чисел окажется несколько, то возьмем любое из них. Поскольку это число не меньше своих соседей и является средним арифметическим этих соседей, оба соседа равняются данному числу.
Проводя аналогичные рассуждения для соседей данного числа, для их соседей и т. д., получаем, что все числа равны между собой. Что и требовалось доказать. (В этой задаче крайним было наибольшее из всех чисел.)
Электронные часы показывают цифры часов и минут (например, 18:40). Какая наибольшая сумма цифр может быть на таких часах?
Решение:
Следует оценить сумму цифр в записи числа часов и в записи числа минут. Заметим, что максимальное число часов на часах — 23, максимальное число минут на часах — 59.
Наибольшее значение первой цифры — 2, второй — 9, значит, сумма первых двух цифр не может быть больше 11. Сумма равна 11 только при первой цифре 2 и второй цифре 9, но число часов не может быть равным 29. Следовательно, сумма первых двух цифр меньше 11. Сумма, равная 10, достигается на 19 часах.
Наибольшее значение третьей цифры — 5, четвертой — 9, значит, сумма первых двух цифр не может быть больше 14. Сумма, равная 14, достигается на 59 минутах. В итоге наибольшая сумма цифр — это 10+14=24.
Ответ: 24.
Несколько команд участвуют в однокруговом футбольном турнире. Докажите, что независимо от расписания игр в любой момент найдутся хотя бы две команды, сыгравшие к этому моменту одинаковое количество матчей.
Решение:
Обозначим количество команд через n. Рассмотрим произвольный момент турнира. К этому моменту каждая команда могла сыграть от 0 до n − 1 матчей: различных вариантов ровно n, то есть столько же, сколько команд.
Пусть все команды сыграли разное количество матчей. Тогда каждый из n вариантов реализован ровно одной командой. Следовательно, какая-то команда не сыграла ни одного матча, а другая команда сыграла n – 1 матчей, то есть играла со всеми остальными командами. Но тогда она играла и с той командой, которая не сыграла ни одного матча, — противоречие.
Плоскость окрашена в два цвета — белый и черный, причем имеются точки и белого, и черного цвета. Докажите, что всегда найдутся две точки одного цвета на расстоянии 1 друг от друга.
Решение:
Рассмотрим равносторонний треугольник со стороной 1, произвольно расположенный на этой плоскости. Поскольку вершин у треугольника три («кролики»), а цветов только два («клетки»), согласно принципу Дирихле, найдутся две вершины одного цвета (любые две вершины этого треугольника расположены на расстоянии 1 друг от друга).
Могут ли три рыцаря, каждый со своим оруженосцем, переправиться через реку на двухместной лодке, если оруженосцы отказываются оставаться с незнакомыми рыцарями без своих хозяев?
Решение:
Здесь следует перебирать последовательно все возможные варианты переправы, отсекая заведомо неподходящие. А для того чтобы оруженосцы не оставались с незнакомыми рыцарями, рыцари не должны оставаться в меньшинстве.
Для того чтобы проиллюстрировать задачу, обозначим рыцарей и их оруженосцев через Р1, Р2, Р3 и О1, О2, О3 соответственно, а реку обозначим знаком тире. Изначально все находились по одну сторону от реки, т. е.
Р1 Р2 Р3 О1 О2 О3 −,
в итоге мы хотим получить расположение
− Р1 Р2 Р3 О1 О2 О3.
1. Если в первую переправу поедет один из рыцарей со своим оруженосцем, то оруженосцы не останутся с незнакомыми рыцарями ни на первом берегу, ни на втором. Вернуть лодку на первый берег оруженосец не может, так как в этом случае на первом берегу оруженосец окажется без своего рыцаря, что нас не устраивает. Значит, после первой переправы лодку назад должен возвращать рыцарь. В результате первая переправа (туда-обратно) будет выглядеть так:
Р1 Р2 Р3 О1 О2 О3 − ⇒ Р1 Р2 О1 О2 − Р3 О3 ⇒ Р1 Р2 Р3 О1 О2 − О3.
2. После этого на первом берегу окажется 3 рыцаря и 2 оруженосца, а на втором берегу — 1 оруженосец. Определим того, кто на этот раз может переправиться на другой берег. Двух рыцарей отправлять нельзя, так как в этом случае на первом берегу рыцари останутся в меньшинстве. Рыцаря и оруженосца нельзя, так как в этом случае на втором берегу рыцари будут в меньшинстве. Следовательно, отправить придется двух оруженосцев. Пригнать лодку обратно придется оруженосцу, поскольку на втором берегу будут только оруженосцы. В результате вторая переправа (туда-обратно) будет выглядеть так:
Р1 Р2 Р3 О1 О2 − О3 ⇒ Р1 Р2 Р3 − О1 О2 О3 ⇒ Р1 Р2 Р3 О1 − О2 О3.
3. Теперь на первом берегу будут 3 рыцаря и 1 оруженосец, а на втором — 2 оруженосца. Переправить на другой берег рыцаря с оруженосцем мы не можем, так как тогда там рыцари будут в меньшинстве, значит, отправляем двух рыцарей. В этом случае на первом берегу останутся рыцарь с оруженосцем, а на втором будет 2 рыцаря и 2 оруженосца. Теперь отправить возвращать лодку кого-то одного уже на получится, так как либо на первом, либо на втором берегу рыцари окажутся в меньшинстве. Получается, что отправить обратно можно только рыцаря с оруженосцем. В результате третья переправа (туда-обратно) будет выглядеть так:
Р1 Р2 Р3 О1 − О2 О3 ⇒ Р1 О1 − Р2 Р3 О2 О3 ⇒ Р1 Р2 О1 О2 − Р3 О3.
Заметим, что теперь ситуация стала совершенно симметричной. Если до последнего маневра на первом берегу были рыцарь с оруженосцем, а на втором — 2 рыцаря и 2 оруженосца, то после маневра наоборот: на первом берегу 2 рыцаря и 2 оруженосца, а на втором 1 рыцарь и 1 оруженосец. Так как наша исходная задача также была симметричной (все были на первом берегу, а должны оказаться на втором берегу), то нужно выполнить все предыдущие действия в обратном порядке.
4. Сейчас на первом берегу 2 рыцаря и 2 оруженосца, а на втором 1 рыцарь и 1 оруженосец. Отправим на второй берег двух рыцарей, а лодку возвращать поручим оруженосцу:
Р1 Р2 О1 О2 − Р3 О3 ⇒ О1 О2 − Р1 Р2 Р3 О3 ⇒ О1 О2 О3 − Р1 Р2 Р3.
5. Двух оруженосцев отправим на второй берег, а лодку возвращать поручим рыцарю:
О1 О2 О3 − Р1 Р2 Р3 ⇒ О3 − Р1 Р2 Р3 О1 О2 ⇒ О3 Р3 − Р1 Р2 О1 О2.
6. Последней поездкой отправим оставшихся рыцаря с оруженосцем:
О3 Р3 − Р1 Р2 О1 О2 ⇒ − Р1 Р2 Р3 О1 О2 О3.
В результате наших действий все оказались на другом берегу реки.
Ответ: Да.