МАТЕМАТИЧЕСКИЕ ЗАДАЧИ С РЕШЕНИЕМ. Часть 5
Математические задачи с решениями: расчетные, головоломные и на стратегии математических игр. Источники разнообразные, только решения таких задач не является объектом авторского права.
Докажите, что среди любых шести человек всегда найдутся либо трое попарно знакомых, либо трое попарно незнакомых.
Решение:
У данного человека среди остальных пяти есть либо не менее трех знакомых, либо не менее трех незнакомых ему. Разберем, например, первый случай. Среди этих трех людей есть либо двое знакомых — тогда они вместе с выбранным нами исходно человеком образуют нужную тройку, либо они все трое попарно незнакомы.
Суммарное расстояние между съездами 1 и 20 на новой автомагистрали составляет 140 км. Между любыми двумя съездами должно быть не менее 7 км. Чему равно максимальное расстояние между любыми двумя соседними съездами?
Решение:
Прежде всего отметим, что между съездами 1 и 20 всего 19 «расстояний». Поскольку минимальное расстояние между любыми двумя съездами равно 7 км, рассмотрим крайний случай, в котором все расстояния, кроме одного, равны 7 км. Тогда минимальная сумма 18 «расстояний» составит 18 × 7 = 126 км. Таким образом, максимальное расстояние между любыми двумя съездами равно 140 – 126 = 14 км, иначе не хватит километров, чтобы выдержать 7-километровую дистанцию между остальными съездами.
Лиза, которая едет на велосипеде по мосту, соединяющему точки A и B, и уже преодолела 3/8 его длины, слышит, что сзади приближается поезд, движущийся со скоростью 60 км/ч. Она прикидывает расстояния и решает, что впритык сможет избежать столкновения, если поедет в любую сторону (к точке A или точке B) максимально быстро. Какова ее максимальная скорость?
Решение:
Раз Лиза впритык успевает доехать до любого конца моста, будем считать, что она едет вперед к точке B. К тому моменту, когда поезд подойдет к точке A, она преодолеет 3/8 еще пути, т.е. всего 6/8 = 3/4 длины моста. Теперь ей нужно проехать оставшуюся ¼ моста за то же самое время, которое требуется поезду, чтобы преодолеть полную длину моста. Таким образом, ее скорость равна ¼ скорости поезда, т.е. 15 км/ч.
В фотоателье залетели 20 птиц — 8 скворцов, 7 трясогузок и 5 дятлов. Каждый раз, как только фотограф щелкнет затвором фотоаппарата, какая-то одна из птичек улетит (насовсем). Сколько кадров сможет сделать фотограф, чтобы быть уверенным: у него останется не меньше пяти птиц одного вида, и не меньше трех — другого?
Решение:
Когда птиц каждого вида останется меньше 5? Тогда и только тогда, когда улетят хотя бы 4 скворца, 3 трясогузки и 1 дятел. Такое может случиться после 4+3+1 = 8 выстрелов. А если выстрелить 7 раз, то птиц какого-то вида будет как минимум 5, скажем, вида А.
Самое трудное — доказать (без лишнего перебора), что птиц какого-то другого вида останется хотя бы 3. Всего осталось 13 птиц, из них максимум 8 птиц вида А. Значит, не менее 5 птиц двух других видов в сумме. Из них птиц одного вида не менее 3 (если бы было не более 2 каждого из двух видов, то в сумме было бы не более 4).
Грани куба окрашены в 2 цвета. Докажите, что найдутся две соседние одноцветные грани.
Решение:
Рассмотрим три грани куба, имеющие общую вершину. Назовем их кроликами, а данные цвета — клетками. Поскольку кроликов больше, чем клеток, то по принципу Дирихле найдутся две грани, окрашенные в один цвет. Они и будут соседними.
На сковороде могут одновременно жариться две котлеты. Каждую котлету нужно обжарить с двух сторон, при этом для обжаривания ее с одной стороны требуется 2 минуты. За какое наименьшее время можно поджарить три котлеты?
Решение:
Три котлеты можно пожарить за 6 минут:
1. Сначала жарим на одной стороне две котлеты.
2. Затем через 2 минуты одну переворачиваем, а вторую снимаем и заменяем третьей.
3. Еще через 2 минуты снимаем готовую, заменяем ее отложенной, а третью переворачиваем.
Доказать, что из шести любых людей найдутся либо трое попарно знакомых, либо трое попарно незнакомых.
Решение:
Самая главная неприятность в задаче –– слишком «нематематическая» постановка вопроса. Что значит «знакомы»? Как это строго записать, какой формулой? А может, и не формулой вовсе, а геометрически? А что, если граф поможет? Надо как-то попробовать поставить в соответствие задаче граф, тогда она, по крайней мере, станет «виднее». Берем шесть точек (по точке на каждого человека) –– это вершины. А ребра будем строить так: если люди знакомы между собой, то и точки соединим. Не знакомы –– не соединяем. Как же теперь выглядит задача в такой интерпретации? А вот как: в любом графе с шестью вершинами найдутся либо три попарно соединенные вершины (по существу, треугольник, хотя, быть может, с кривыми сторонами), либо три попарно не соединенные вершины. Чисто геометрически это довольно ясно: если линий много, то должен быть треугольник, а если мало, то должны появиться три не связанные между собой вершины. Попробуем это как-то более тщательно обосновать.
Допустим, что линий много. Например, что из одной вершины их выходит более половины возможного. Всего возможно пять, так как остальных вершин осталось пять, а более половины –– это три. Итак, пусть из одной вершины выходит три ребра. Рассмотрим вершины, лежащие на другом конце этих ребер. Если какие-то две из них соединены, то и получаем треугольник вместе с двумя ребрами, соединяющими их с исходной вершиной. Значит, они не соединены и... все что надо получено –– нашли три вершины, попарно не соединенные. С этим случаем разобрались. Случай, когда ребер меньше, совершенно аналогичен уже рассмотренному. Маленькая подсказка в форме вопроса: что мы получили бы вышеприведенным доказательством, если бы строили граф, наоборот, соединяя те вершины, которые соответствуют незнакомым людям? (Такой граф, кстати сказать, называют дополнительным к исходному.)
В пять горшочков, стоящих в ряд, Кролик налил три килограмма меда (не обязательно в каждый и не обязательно поровну). Винни-Пух может взять любые два горшочка, стоящие рядом. Какое наибольшее количество меда сможет гарантированно съесть Винни-Пух?
Решение:
Следует привести такой пример расположения горшочков с медом, что в любых двух соседних горшках будет ровно 1 кг меда. Показать, что при любом расположении горшочков с медом Винни-Пух точно может получить не менее 1 кг меда. Попробуем рассмотреть случай, когда два горшочка пусты, а в остальных меда поровну.
Пронумеруем горшочки и заметим, что если в горшочки с номерами 1, 3 и 5 положить по 1 кг меда, то Винни-Пух, взяв любые два стоящие рядом горшочка, возьмет один пустой и один с 1 кг.
Теперь покажем, что при любом расположении горшочков с медом Винни-Пух точно может получить не менее 1 кг меда. Если в горшочках с номерами 1 и 2 меда меньше 1 кг и в горшочках с номерами 3 и 4 меда меньше 1 кг, то в горшочке с номером 5 меда не менее 1 кг. В этом случае, выбрав горшочек с номером 5, Винни-Пух получит не менее 1 кг меда.
Ответ: 1 кг.
В клетках таблицы 3 х 3 расставлены числа−1, 0, 1. Докажите, что какие-то две из 8 сумм по всем строкам, всем столбцам и двум главным диагоналям будут равны.
Решение:
Поскольку в строке, столбце и на диагонали стоят по три числа из набора−1, 0, 1, то каждая сумма может принимать значение от −3 до 3 — всего семь вариантов. В таблице 3 х 3 три строки, три столбца и две главные диагонали — всего 8 сумм. Тогда по принципу Дирихле какие-то две суммы обязательно совпадут.
В данном примере клетки мы создали из возможных значений сумм, а кроликов — из конкретных значений сумм по строкам, столбцам и главным диагоналям таблицы.
На квадратном поле 10 × 10 девять клеток 1 × 1 поросли бурьяном. После этого бурьян может распространиться на клетку, у которой не менее двух соседних клеток уже поросли бурьяном. Докажите, что тем не менее бурьян не сможет распространиться на все клетки.
Решение:
Рассмотрим один из частых полуинвариантов/инвариантов – периметр. Давайте посмотрим, как изменяется периметр всех клеток, которые поросли бурьяном, когда прорастает новая клетка. Возможны 4 случая (красным отметим новую клетку, а черным старые):
Значит полуинвариант такой: периметр рассматриваемой области не увеличивается. Периметр исходных клеток не больше чем 4·9=36, но периметр всего квадрата 40, что больше чем 36, поэтому весь квадрат зарасти не мог.
Убирая детскую комнату к приходу гостей, мама нашла 9 носков. Среди любых четырех носков хотя бы два принадлежали одному ребенку, а среди любых пяти носков не более трех имели одного хозяина. Сколько могло быть детей и сколько носков могло принадлежать каждому ребенку, если у каждого был хотя бы один носок?
Решение:
Если бы детей было больше трех, то можно было бы взять 4 носка, принадлежащих разным детям, и получить противоречие с тем, что среди любых четырех носков хотя бы два принадлежат одному ребенку. Итак, детей максимум трое. С другой стороны, каждому ребенку принадлежит не более трех носков (иначе можно было бы взять пять носков, из которых более трех принадлежат одному хозяину), а так как всего носков 9, то детей не более трех.
Итак, детей ровно трое и каждому принадлежат ровно три носка.
Докажите, что никакая прямая не может пересекать все три стороны треугольника (в точках, отличных от вершин).
Решение:
Прямая делит плоскость на две полуплоскости, которые будем считать клетками. Три вершины треугольника будем считать кроликами. По принципу Дирихле найдется клетка, в которой сидит по крайней мере два кролика, т.е. найдутся две вершины, лежащие в одной полуплоскости относительно данной прямой. Сторона, соединяющая эти вершины, не пересекает данную прямую.
В каждой клетке шахматной доски записано число. Оказалось, что любое число равно среднему арифметическому чисел, записанных в соседних (по стороне) клетках. Докажите, что все числа равны.
Решение:
Рассмотрим максимальное число 𝑛, если таких несколько, то любое. Тогда все соседи, чтобы их среднее арифметическое было равно 𝑛, должны быть сами равны 𝑛 (если есть число, которое строго меньше, тогда и среднее арифметическое будет меньше 𝑛). Так как соседи тоже являются максимальными, то рядом с ними числа тоже равны 𝑛. Таким образом, все числа в таблице равны 𝑛.
Вася думает, что если площадь первого прямоугольника больше площади второго, а также периметр первого больше периметра второго, то из первого можно вырезать второй. Прав ли он?
Решение:
Из прямоугольника 1×100 нельзя вырезать квадрат 2×2.
Ответ: нет, не прав.
В школе 500 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение:
Предположим, что это не так, т. е. в каждый день года родились не более одного ученика школы. Тогда, поскольку всего дней в году 366 (будем рассматривать максимально возможное число дней в году, т. е. високосный год), всего учеников в школе не более 366, что противоречит условию. Следовательно, наше предположение неверно и, значит, в школе есть хотя бы два ученика, которые родились в один день года. (В этой задаче роль кроликов играют ученики, а роль клеток — дни года).
В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.
Решение:
Выберем любых двух учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого имеется 24 друга, и задача решена). Из оставшихся 23 учеников каждый дружит с одним из этих двух, иначе мы имели бы тройку учеников, среди которых не было бы друзей. Тогда у одного из выбранных двух учеников не менее 12 друзей. (23 «кролика» рассажены в двух «клетках»).
Очень лёгкая задача на логику. «У Лёвы кот перед дождём всегда чихает. Сегодня он чихнул. «Значит, будет дождь» - думает Лев. Прав ли он?
Ответ:
Нет, не прав. Из необходимости условия вовсе не следует его достаточность.
На балу каждый кавалер танцевал с тремя дамами, а каждая дама — с тремя кавалерами. Докажите, что на балу число дам равнялось числу кавалеров.
Решение:
Определим число различных танцевавших пар.
Если число кавалеров принять за k, то число пар было равно 3k, так как каждый кавалер танцевал с тремя да¬мами. Если число дам принять за т, то число пар было равно 3m, так как каждая дама танцевала с тремя кава¬лерами. Значит, 3k=3m, или k=m.
На стол положили несколько одинаковых листов бумаги прямоугольной формы. Оказалось, что верхний лист покрывает больше половины площади каждого из остальных листов. Можно ли в таком случае воткнуть булавку так, чтобы она проколола все листы?
Решение:
Для этого нужно воткнуть булавку в центр верхнего листа бумаги, ибо этот центр, в силу условия задачи, принадлежит каждому из остальных прямоуголь¬ников.
Ответ:можно.
Набор состоит из 30 гирек с массами 1 г, 2 г, 3 г,..., 30 г. Из набора убрали 10 гирек, общая масса которых равна трети общей массы всех гирек. Можно ли оставшиеся гирьки расположить на двух чашках весов по 10 штук на каждой чашке так, чтобы весы оказались в равновесии?
Решение:
Две гирьки, сумма масс которых равна 31 г, назовем парой. Наш набор распадается на 15 пар. По¬скольку убрали только 10 гирек, не менее 5 пар остались нетронутыми. Возьмем 5 нетронутых пар и положим на одну чашку весов, а остальные оставшиеся гирьки поло¬жим на другую. Весы окажутся в равновесии.
Ответ: можно.