МАТЕМАТИЧЕСКИЕ ЗАДАЧИ С РЕШЕНИЕМ. Часть 2
Математические задачи с решениями: расчетные, головоломные и на стратегии математических игр. Источники разнообразные, только решения таких задач не является объектом авторского права.
Барон Мюнхгаузен и его слуга Томас подошли к реке. На берегу они обнаружили лодку, способную перевезти лишь одного человека. Тем не менее они переправились через реку и продолжили путешествие. Могло ли так быть?
Решение:
Здесь следует рассмотреть все возможные варианты расположения барона Мюнхгаузена и его слуги Томаса относительно реки и все возможные варианты их переправы через реку.
Если барон со слугой находятся на одном берегу реки, то на другой берег может переправиться только один из них. Для того чтобы переправился второй, первый должен вернуть лодку, а, следовательно, вернуться сам, и тогда они снова вместе с лодкой окажутся на том же месте.
Если же барон со слугой находятся на разных берегах реки, то сначала тот из них, на чьем берегу обнаружилась лодка, должен переправиться на противоположный берег, а потом на приплывшей лодке второй из них должен перебраться через реку.
Ответ: да, если они подошли к реке с разных берегов.
У входа в пещеру, где хранятся сокровища Али-Бабы, стоит устройство, не позволяющее проникнуть в пещеру непосвященному. Снаружи это устройство похоже на диск, в котором проделаны в виде квадрата четыре отверстия. Внутри каждого отверстия есть невидимый снаружи выключатель. Каждый выключатель имеет два положения: «вверх» и «вниз», причем легко определить на ощупь, в каком положении находится выключатель. Человек имеет право опустить руки в любые два отверстия и придать выключателям желаемое положение. После этого диск начинает быстро вращаться и останавливается в некотором положении. (При этом нельзя установить, как новое положение диска связано с предыдущим.) После этого вновь можно манипулировать любыми двумя выключателями. Дверь в пещеру откроется лишь в том случае, если все четыре выключателя окажутся в одном положении. Указанные манипуляции можно проделать не более шести раз. В противном случае на неудачника обрушится тяжелая плита. Смогли бы вы попасть в пещеру Али-Бабы?
Решение:
Поскольку каждое следующее положение диска никак не связано с предыдущим, то нам, фактически, доступны только две операции:
1. Проверить и переключить какие-то два соседних (расположенных не по диагонали) выключателя, не важно, с какой стороны квадрата.
2. Проверить и переключить какие-то два диагональных выключателя, не важно, на какой диагонали квадрата.
Обозначим положения выключателей через «В» (верх) и «Н» (низ). Алгоритм решения головоломки, следующий:
1. Переключаем 2 соседних выключателя в положение В.
2. Переключаем 2 диагональных выключателя в положение В. Если после этого дверь не открылась, то ясно, что 3 выключателя находятся в положении В, и один — в положении Н.
3. Проверяем два соседних выключателя. Если нам не повезло, и попались оба выключателя в положении В, то переключаем один из них в положение Н. Теперь два выключателя находятся в положении В, и два — в положении Н. Неясно только, как они расположены: ВВНН (в одинаковом положении находятся соседние выключатели) или ВНВН (в одинаковом положении находятся диагональные выключатели).
4. Проверяем 2 диагональных выключателя. Если они в одинаковом положении, то нам повезло (это ситуация ВНВН): переводим их в обратное положение, и дверь открывается. Если они в разном положении, то это ситуация ВВНН. Ничего не делаем и переходим к следующему шагу.
5. Проверяем 2 соседних выключателя. Если нам не повезло, и они находятся в разном положении, то переводим каждый из них в обратное положение. Так мы превратим позицию ВВНН в позицию ВНВН, а с ней мы легко справимся на следующем шаге.
6. Переключаем 2 диагональных выключателя в обратное положение, и дверь открывается.
Задача решена.
На белую бесконечную плоскость брызнули черной краской. Докажите, что найдутся какие-то две точки одного (белого или черного) цвета, расстояние между которыми в точности равно 2023 метрам.
Решение:
Нарисуем на плоскости произвольный равносторонний треугольник с длиной стороны 2023 метра.
У этого треугольника три вершины, каждая из которых окрашена в один из двух цветов (в белый или в черный). Понятно, что какие-то две из этих вершин — одинакового цвета (поскольку цветов всего два, а вершин три). Расстояние между этими двумя вершинами как раз и будет составлять 2023 метра.
Точное указание расстояния между точками — 2023 метра — тут не играет никакой роли. Оно нужно лишь для того, чтобы сбить с толку.
В пионерском лагере каждый мальчик знаком с 10 девочками, а каждая девочка –– с 10 мальчиками. Доказать, что мальчиков и девочек в лагере одинаковое число.
Решение:
Поиск решения состоит только в том, чтобы догадаться нарисовать граф. А задачи про знакомства просто по своей постановке просят графа. Так вот, предположим, что граф уже нарисован. Вершины –– девочки и мальчики, ребра –– знакомства, т. е. соединяем мальчика и девочку ребром тогда и только тогда, когда они знакомы. Граф неориентированный, так как если мальчик знаком с какой-то девочкой, то и, наоборот, девочка знакома с этим мальчиком. Теперь единственный вопрос: сколько получится ребер? У каждого мальчика по 10 знакомых, значит, количество ребер равно количеству мальчиков, умноженному на 10. Точно так же количество ребер равно количеству девочек, умноженному на 10. Но количество ребер всегда одинаково, как ни считай. Получаем, что десятикратное количество мальчиков равно десятикратному количеству девочек, а, следовательно, тех и других поровну.
Имеются чашечные весы без гирь и 9 одинаковых по внешнему виду монет. Одна из монет фальшивая, причем неизвестно, легче она настоящих монет или тяжелее (настоящие монеты одного веса). Сколько надо сделать взвешиваний, чтобы определить фальшивую монету?
Решение:
Поскольку мы не знаем, легче или тяжелее фальшивая монета настоящих, то определение этого будет нам стоить одного лишнего взвешивания.
Вначале разделим монеты на три кучки по три монеты в каждой. Поскольку фальшивая монета только одна, то она окажется в одной из кучек, а в двух других будут только настоящие монеты. Поэтому кучка с фальшивой монетой будет отличаться по весу от двух других, которые будут весить одинаково. Определим сначала кучу, в которой находится фальшивая монета.
Положим первую и вторую кучку на разные чашки весов.
Возможны два случая:
ПЕРВЫЙ СЛУЧАЙ. Чашки весов уравновешены. Значит, эти кучки весят одинаково и в них нет фальшивой монеты. Следовательно, фальшивая монета находится в третьей кучке. Снимаем все монеты с весов — они настоящие — и откладываем их в сторону. Берем две монеты из третьей кучки и кладем их на разные чашки весов. Опять возможны два случая:
а) Чашки весов уравновешены. Значит, на весах настоящие монеты, а фальшивой является третья монета. За два взвешивания мы определили, какая из монет фальшивая, но не определили, легче она или тяжелее настоящих. Если это надо, то третьим взвешиванием мы это легко делаем.
б) Одна из чашек оказалась ниже другой. Значит, фальшивая монета на весах, но неизвестно на какой стороне. Третьим взвешиванием мы можем определить, на какой чашке весов находится фальшивая монета, и даже узнать, легче она или тяжелее настоящей.
Предположим, для определенности, что левая чашка весов оказалась выше, а правая ниже. Снимем с правой чашки монету и положим туда третью (настоящую) монету. Если чаши весов уравновесятся, то снятая монета фальшивая и она тяжелее настоящих. Если же левая чашка так и останется выше правой, то фальшивая монета в левой чашке, и она легче настоящих.
ВТОРОЙ СЛУЧАЙ. Одна из чашек оказалась ниже другой. Значит, фальшивая монета в одной из этих кучек. Вторым взвешиванием мы можем определить, в какой именно кучке находится фальшивая монета, и даже узнать, легче она или тяжелее настоящей. Предположим, для определенности, что левая чашка весов оказалась выше, а правая ниже.
Снимем с правой чашки монеты и положим туда монеты из третьей кучки. Если чаши весов уравновесить, то фальшивая монета в снятой кучке, и она тяжелее настоящих. Если же левая чашка так и останется выше правой, то фальшивая монета в левой чашке, и она легче настоящих. Третьим взвешиванием из трех монет легко, аналогично предыдущей задаче, находим фальшивую.
Таким образом, за три взвешивания мы определили фальшивую монету и даже узнали, легче она или тяжелее настоящих.
Ответ: не более трех.
(Смекалка кузнеца Хечо). Назад тому лет 300 жил в Грузии князь злой и надменный. Была у князя дочь-невеста, Дариджан по имени. Обещал князь свою Дариджан в жены богатому соседу, а она полюбила простого парня, кузнеца Хечо. Попытались было Дариджан и Хечо убежать в горы от неволи, но поймали их слуги князевы.
Рассвирепел князь и решил назавтра казнить обоих, на ночь же приказал их запереть в высокую, мрачную, заброшенную, недостроенную башню, а вместе с ними еще и служанку Дариджан, девочку-подростка, которая помогала им бежать.
Не растерялся в башне Хечо, осмотрелся, поднялся по ступенькам в верхнюю часть башни, в окно выглянул — прыгать невозможно, разобьешься. Тут заметил Хечо около окна забытую строителями веревку, перекинутую через заржавленный блок, укрепленный повыше окна. К концам веревки были привязаны пустые корзины, к каждому концу — по корзине. Хечо вспомнил, что при помощи этих корзин каменщики поднимали вверх кирпич, а вниз спускали щебень, причем, если вес груза в одной корзине превышал вес груза в другой примерно на 5 — 6 кг, то корзина довольно плавно опускалась на землю; другая корзина в это время поднималась к окну.
Хечо на глаз определил, что Дариджан весит около 50 кг, служанка не более чем 40 кг. Свой вес Хечо знал — около 90 кг. Кроме того он нашел в башне цепь весом в 30 кг. Так как в каждой корзине могли поместиться человек и цепь или даже 2 человека, то им всем троим удалось спуститься на землю, причем спускались они так, что ни разу вес опускающейся корзины с человеком не превышал веса поднимающейся корзины более чем на 10 кг.
Как они выбрались из башни?
Решение:
1. Сначала «пленники» положили цепь (30 кг) в корзину и отправили ее вниз.
2. В поднявшуюся наверх пустую корзину села девочка-служанка (40 кг) и опустилась вниз; в то же время корзина с цепью поднялась вверх.
3. Хечо вынул цепь и посадил в корзину Дариджан (50 кг). Дариджан опустилась вниз, поднимая вверх служанку-девочку.
4. Дариджан вышла из корзины на землю, а девочка из поднявшейся корзины — в башню.
5. В освободившуюся наверху корзину Хечо снова положил цепь и вторично опустил ее на землю.
6. На земле в корзину с цепью села Дариджан (50 + 30 = 80 кг), а в поднявшуюся корзину сел Хечо (90 кг).
7. Хечо спустился, вышел из корзины на землю, а Дариджан вышла из поднявшейся корзины в башню. Цепь она оставила в поднявшейся корзине.
8. Цепь в третий раз опустилась на землю.
9. В поднявшуюся корзину снова села девочка (40 кг) и опустилась на землю, поднимая цепь (30 кг).
10. Дариджан вынула цепь, села в корзину (50 кг) и опустилась вниз, поднимая вверх девочку (40 кг). Дариджан вышла на землю, а девочка в башню.
11. Девочка положила в корзину цепь и опять опустила ее на землю, затем сама села в поднявшуюся пустую корзину и опустилась вниз, поднимая цепь наверх.
12. «Приземлившись», девочка присоединилась к ожидающим ее Дариджан и Хечо, а цепь в последний раз упала на землю.
Все трое благополучно укрылись в горах от свирепого князя.
Веб-сайт просит пользователя создать восьмизначный пароль, содержащий только цифры, где каждая цифра используется только один раз. Определите: сколько существует различных возможных паролей?
Решение:
Для создания такого пароля разрешается применять только цифры – 10 символов. Каждая цифра должна использоваться только один раз. Значит, для определения количества паролей необходимо использовать формулу размещения без повторений:
Тогда, количество размещений из 8 цифр, выбранных из 10, составляет 1814400 паролей
Ответ: 1814400 паролей, содержащих только цифры, где каждая цифра используется только один раз.
Какое наибольшее число полей на доске 8×8 можно закрасить в черный цвет так, чтобы в любом уголке из трех полей было по крайней мере одно не закрашенное поле?
Решение:
Если разбить шахматную доску на квадраты 2×2, то в каждом квадрате можно закрасить максимум две клетки. Значит, максимальное число закрашенных клеток 32. Это максимальное значение достигается при обычной шахматной раскраске.
Ответ: 32.
На доске написаны три различных числа от 1 до 9. Одним ходом разрешается либо прибавить к одному из чисел 1, либо вычесть из всех чисел по 1. Верно ли, что всегда можно добиться того, чтобы на доске остались только нули, сделав не более 23 ходов?
Решение:
Пусть вначале на доске написаны числа 1, 2 и 9, и через несколько ходов из них получились нули. Если из 9 в результате получился ноль, то вычитание производилось хотя бы девять раз. Значит, и из остальных чисел вычиталось хотя бы по девять единиц; значит, к 1 надо было сделать не меньше восьми прибавлений, а к двойке не меньше семи.
Итоговое количество ходов, таким образом, не меньше 9 + 8 + 7 = 24.
Ответ: неверно.
На острове Серобуромалин обитают 13 серых, 15 бурых и 17 малиновых хамелеонов. Если встречаются два хамелеона разного цвета, то они одновременно меняют свой цвет на третий (серый и бурый становятся малиновыми и так далее). Может ли случиться, что через некоторое время все хамелеоны будут одного цвета?
Решение:
Итак, имеется тройка чисел (13, 15, 17). Разрешается делать с ней следующие преобразования: к одному из чисел прибавить двойку, а от двух оставшихся одновременно отнять единицу. Спрашивается, можно ли получить один из наборов: (45, 0, 0); (0, 45, 0) или (0, 0, 45)?
Имеем процесс. Начнем искать инвариант. Прежде всего посмотрим, что можно сделать за один шаг. Можно получить (12, 14, 19)? Видны ли какие-либо грубые неизмененные вещи? Нет, разве что разность между первым и вторым членом не изменилась. А что с ней произойдет при каком-нибудь другом преобразовании? Мы можем получить из исходного набора также набор (12, 17, 16). Что здесь можно сказать относительно разности первого и второго? Она изменилась. Кстати, на сколько? На три. Ладно, и третье изменение из исходного: (15, 14, 16). Здесь разность совсем изменилась. А сейчас на сколько? Было −2, а стало +1. Разность –– 3. Что? Тройка у нас уже встречалась? Когда? В предыдущем случае. Только там в другую сторону. Все равно, что-то в этом есть.
Не пора ли перейти к остаткам? Остатки по модулю три. Исходная тройка чисел преобразуется в набор остатков (1, 0, 2). Требуется получить остатки (0, 0, 0) во всех трех случаях. Что можем получить после первого преобразования? (0, 2, 1), или (0, 2, 1), или... (0, 2, 1) –– каким путем ни иди! А на следующем шаге? (2, 1, 0). И на следующем шаге опять вернемся в исходное состояние (1, 0, 2). В общем-то понятно: с точки зрения остатков у нас совершается такое преобразование за один ход: к каждому остатку прибавляется 2 (или, что то же самое, с точки зрения остатков при делении на три –– отнимается по единице). Теперь понятно, что никогда три нуля мы не получим.
Промежуточное решение найдено. Теперь совсем нетрудно очистить его до конца: инвариант –– это разность между первым и вторым членом, взятая по модулю три. Она –– всегда единица. Это и есть нужный инвариант, который и покажет, что получить всех хамелеонов одного цвета не удастся (для них значение инварианта равно 0).
Имеются двое песочных часов: на 7 минут и на 11 минут. Каша должна вариться 15 минут. Как сварить кашу, переворачивая часы минимальное число раз?
Решение:
Следует составить соответствующее равенство, связывающее числа 7, 11 и 15. Заметим, что 15=2·11−7. Перепишем это равенство в виде 15=(11−7)+11 и опишем наши действия.
1) Переворачиваем одновременно песочные часы.
2) В тот момент, когда в 7-минутных часах закончится песок, в 11-минутных часах останется песка ровно на 4 минуты, начинаем варить кашу.
3) Когда в 11-минутных часах закончится песок (прошло 4 минуты с момента начала варки каши), переворачиваем их.
4) Когда во второй раз закончится песок в 11-минутных часах — каша готова.
Ответ: 15=11−7+11.
В классе 24 ученика. Каждый из учеников класса занимается не более чем в двух кружках, причем для любых двух учеников существует кружок, в котором они занимаются вместе. Докажите, что найдется кружок, в котором занимаются не менее 16 учеников.
Решение:
Если в некоторый кружок ходит весь класс, то все доказано. Далее будем считать, что такого кружка нет.
Пусть самый многочисленный кружок — математический. Его участников мы будем называть математиками. Поскольку не весь класс ходит в этот кружок, найдется ученик Петров, который в него не ходит. Рассмотрим его и одного из математиков. Они вместе ходят в другой кружок, допустим в физический (физики). Петров не может ходить в этот кружок вместе со всеми математиками, иначе математический кружок не будет самым многочисленным. Значит, с кем-то из математиков он ходит еще в один кружок, например, литературный (лирики).
Поскольку Петров занимается не более чем в двух кружках, то математики не могут заниматься больше ни в каких других кружках. Значит, каждый математик может еще быть только либо физиком, либо лириком, а Петров является физиком и лириком одновременно. То, что было сказано про Петрова, можно сказать и про любого другого ученика, который не является математиком: каждый из таких учеников — физик и лирик одновременно (и больше ни в какие кружки не ходит).
Таким образом, кружков всего три, и каждый ученик ходит ровно в два кружка. Так как в классе 24 ученика, то на три кружка в общей сложности приходится 48 их участников. Поэтому в математический кружок (самый многочисленный) ходит не менее чем 48:3=16 учеников. (В этой задаче крайним был самый многочисленный кружок).
Узлы бесконечного листа клетчатой бумаги раскрашены в два цвета. Доказать, что существуют две горизонтальные и две вертикальные прямые, на пересечении которых лежат точки одного цвета.
Решение:
Сначала рассмотрим три узла в одной горизонтали. Так как они покрашены в один из двух цветов, то всего возможно 8 вариантов раскраски этих точек. Тогда по принципу Дирихле, рассмотрев 9 наборов из трех узлов, расположенных в 9 горизонталях (друг под другом), мы получим как минимум два одинаковых набора. В каждом из этих наборов будет как минимум два узла одного цвета. Эти четыре точки (две из одного набора и две из другого) и будут искомыми четырьмя точками одного цвета.
На старт «Веселого забега» на 3000 м выходит команда из трех математиков. Им выдается один одноместный самокат. Дорога прямая, стартуют все одновременно, а в зачет идет время последнего пришедшего на финиш. Каково минимальное возможное время прохождения дистанции, если бегают все трое со скоростью 125 м/мин, а на самокате ездят со скоростью 250 м/мин?
Решение:
Пример. Первый едет треть пути на самокате, бросает его, бежит дальше пешком. Второй бежит треть пути, хватает валяющийся самокат, берет его, едет треть пути, бросает, бежит дальше пешком. Третий бежит две трети пути, хватает самокат и финиширует одновременно с теми, кто с ним в одной команде. В итоге каждый треть пути (1 км) едет и две трети пути (2 км) бежит. Значит, каждый спортсмен тратит 1000:250 + 2000:125 = 20 минут на преодоление дистанции.
Оценка. Очевидно, что возвращаться назад, чтобы передать транспортное средство товарищу, невыгодно. Поэтому на самокате нужно двигаться только вперед. Если кто-то проедет на самокате менее трети дистанции, то он потратит на весь забег более 20 минут. Значит, всем нужно проехать ровно треть.
Ответ: 20 минут.
Барон Мюнхгаузен утверждает, что может для некоторого N так переставить числа 1, 2, …, N в другом порядке и затем выписать их все подряд без пробелов, что в результате получится многозначное число-палиндром (оно читается одинаково слева направо и справа налево). Не хвастает ли барон?
Решение:
Числа можно выписать, например, так:
9.18.7.16.5.14.3.12.1.10.11.2.13.4.15.6.17.8.19
Объясним, почему нужно искать пример для N≥19. В палиндроме количество всех цифр, кроме, быть может, одной, должно быть четным. Однако если N = 2, …, 9, то цифры 1 и 2 встречаются в записи чисел 1, 2, …, N по одному разу, а если N = 10, …, 18, то по 1 разу встречаются цифры 0 и 9.
Ответ: нет, не хвастает.
Можно ли доску 8 × 8 разрезать по границам клеток на части и сложить из этих частей клетчатый прямоугольник 5 × 13?
Решение:
Заметим, что при разрезании площадь не меняется (то есть инвариант в этой задаче – площадь), но площадь изначальной фигуры равна 64, а площадь желаемой фигуры равна 65, поэтому требуемое разрезание невозможно.
Понятно, что в некоторых задачах совсем очевидно за что можно зацепиться, но это не всегда так, поэтому важно обращать внимание не только на решения, но и на рассуждения: как можно подойти к тем или иным инвариантам.
В клетках таблицы 99 × 99 расставлены плюсы и минусы. Если в каком-то ряду (строке или столбце) минусов больше, чем плюсов, разрешается в этом ряду поменять все знаки на противоположные. Докажите, что через некоторое время и во всех строках, и во всех столбцах плюсов будет больше, чем минусов.
Решение:
Заметим следующий полуинвариант: количество плюсов во всей таблице после операции увеличивается. Действительно, рассмотрим строку или столбец, в котором мы проводили операцию. Во всей доске, кроме рассмотренной линии, количество плюсов не изменилось, а в самой линии увеличилось, поэтому и во всей доске увеличилось. Теперь поймем, что количество плюсиков не может стать больше 992, поэтому количество проделанных операций конечно (за каждую операцию количество плюсиков увеличивается хотя бы на 1 и ограничено числом 992).
Осталось теперь рассмотреть момент, когда мы не можем сделать операцию, если бы нашлась линия, в которой минусов больше чем плюсов, то мы бы смогли применить к ней операцию и увеличить число плюсов, что противоречит рассмотренному моменту.
Несколько шестиклассников встали в круг. Оказалось, что каждый из шестиклассников не выше ростом хотя бы одного из своих соседей. Могут ли все они быть разного роста?
Решение:
Предположим, что такое возможно. Рассмотрим самого высокого человека А. По условию А не выше ростом хотя бы одного из своих соседей, но строго ниже быть не может, в силу нашего выбора. Таким образом, рядом с А стоит хотя бы один человек такого же роста, значит, наше предположение неверно.
Какое наибольшее число прямоугольников 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.
В гости пришло 10 человек, и каждый оставил в коридоре пару калош. Все пары калош имеют разные размеры. Гости начали расходиться по одному, надевая любую пару калош, в которые они могли влезть, т. е. каждый гость мог надеть пару калош, не меньшую, чем его собственные. В какой-то момент обнаружилось, что ни один из оставшихся гостей не может найти себе пару калош, чтобы уйти. Какое максимальное число гостей могло остаться?
Решение:
Сначала привести пример, потом сделать оценку. Следует разделить все калоши на маленькие и большие.
Расположим все калоши по возрастанию размеров и назовем первые 5 пар маленькими, остальные 5 пар — большими калошами.
Если гости с маленькими размерами ног наденут большие калоши, то останутся гости с большими размерами ног, которые не смогут надеть маленькие калоши. Это пример, когда 5 гостей не смогут найти себе пару калош, чтобы уйти.
Покажем, что не может остаться 6 гостей. Если осталось 6 пар калош, то среди них есть большие. А среди оставшихся шести гостей точно есть гость с маленьким размером ноги, и он может надеть большие калоши и уйти. Следовательно, максимальное число гостей, которые могли остаться, — это 5.
Ответ: 5.