Принцип крайнего
- Joined Oct 2017
- Published Books 32
Copyright © 2017
Задача 1
Зайчиха купила для своих семерых зайчат семь барабанов разных размеров и семь пар палочек разной длины. Если зайчонок видит, что у него и барабан больше, и палочки длиннее, чем у кого-то из братьев, он начинает громко барабанить. Какое наибольшее число зайчат сможет начать барабанить?
Решение
Все зайчата барабанить не могут, так как заведомо не будет барабанить зайчонок, которому достанется самый маленький барабан. С другой стороны, если дать этому же зайчонку и самые короткие палочки, то все остальные зайчата будут барабанить.
Задача 2
Докажите, что числа от 1 до 16 можно записать в строку, но нельзя записать по кругу так, чтобы сумма любых двух соседних чисел была квадратом натурального числа.
Доказательство
Если рядом с 16 стоит число x , то 16+116+x=a2
16+15 , откуда a2=25 и x=9 . Поэтому у 16 не может быть более одного соседа, и удовлетворяющее условию расположение чисел по кругу невозможно. Пример расположения в строку: 16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8.
Задача 3
На конгресс собрались учёные, среди которых есть друзья. Оказалось, что каждые два из них, имеющие на конгрессе равное число друзей, не имеют общих друзей. Доказать, что найдётся учёный, который имеет ровно одного друга из числа участников конгресса.
Решение
Возьмём учёного A, число друзей у которого максимально (если таких учёных несколько, возьмём любого из них); обозначим это число через N. Каждый из N друзей учёного A имеет хотя бы одного друга (A), не имеет более N друзей и никакие двое не имеют равного числа друзей. Следовательно, эти люди имеют 1, 2, 3, …, N друзей. В частности, один из них дружит только с A.
Задача 4
Рассматривается конечное множество M единичных квадратов на плоскости. Их стороны параллельны осям координат (разрешается, чтобы квадраты пересекались). Известно, что для любой пары квадратов расстояние между их центрами не больше 2.
Докажите, что существует единичный квадрат (не обязательно из множества M) со сторонами, параллельными осям, пересекающийся хотя бы по точке с каждым квадратом множества M.
Доказательство
Проведем ось абсцисс через самый нижний, а ось ординат – через самый левый центр квадрата. Тогда центры всех квадратов находятся в квадрате [0, 2] × [0, 2]. Ясно, что квадрат с центром в точке (1, 1) пересекается со всеми.
Задача 5
Каждый из 450 депутатов парламента дал пощечину ровно одному своему коллеге.
Докажите, что можно избрать парламентскую комиссию из 150 человек, среди членов которой никто никого не бил.
Решение 1
Рассмотрим наибольшую группу A депутатов, в которой никто никого не бил. Тогда каждый из оставшихся депутатов попадает в группу B тех, кого били депутаты из A, либо в группу C тех,кто бил депутатов из A (иначе его можно было бы добавить к A, что противоречит её максимальности). Ясно, что в B депутатов не больше, чем в A. Но и в C депутатов не больше, чем в A, поскольку в ней никто никого не бил. Следовательно, в A не меньше 150 депутатов.
Решение 2
Согласно задаче 108403 депутатов можно разбить на три группы, в каждой из которых никто никого не бил. В наибольшей из них не меньше 150 депутатов.
Задача 6
Солдаты построены в две шеренги по n человек, так что каждый солдат из первой шеренги не выше стоящего за ним солдата из второй шеренги. В шеренгах солдат выстроили по росту. Докажите, что после этого каждый солдат из первой шеренги также будет не выше стоящего за ним солдата из второй шеренги.
Решение
Обозначим через a1,a2,…,an рост солдат из первой шеренги в порядке убывания, аналогично обозначим через b1,b2,…,bn рост солдат из второй шеренги в порядке убывания (те же обозначения используем и для самих солдат). Пусть условие задачи неверно. Тогда для некоторого k выполнено ak>bk. Это означает, что до перестраивания по росту солдат ak мог стоять только перед одним из k-1 солдат b1,b2,…,bk-1. То же самое справедливо и для солдат a1,a2,…,ak-1, поскольку они не ниже солдата ak. Итак, мы получили, что до перестраивания шеренг k солдат a1,a2,…,ak могли стоять только перед k-1 солдатами b1,b2,…,bk-1. Ясно, что это противоречие.
Задача 7
Давным-давно страной Тарнией правил царь Ятианр. Чтобы тарнийцы поменьше рассуждали, он придумал для них простой язык. Его алфавит состоял всего из шести букв: А, И, Н, Р, Т, Я, но порядок их отличался от принятого в русском языке. Словами этого языка были все последовательности, использующие каждую из этих букв по одному разу. Ятианр издал полный словарь нового языка. В соответствии с алфавитом первым словом словаря оказалось “Тарния”. Какое слово следовало в словаре за именем Ятианр?
Решение
В первом слове буквы расположены в алфавитном порядке: Т, А, Р, Н, И, Я. Для удобства занумеруем буквы в алфавитном порядке: Т = 1, А = 2, Р = 3, Н = 4, И = 5, Я = 6. Заменим каждое слово соответствующим шестизначным числом. Если слова расположены по алфавиту, то числа – в порядке возрастания. Слово Ятианр запишется числом 615243. За ним следует 615324, что соответствует слову Ятиран.
Задача 8
В команде сторожей у каждого есть разряд (натуральное число). Сторож N-го разряда N суток дежурит, потом N суток спит, снова N суток дежурит, N – спит, и так далее. Известно, что разряды любых двух сторожей различаются хотя бы в три раза. Может ли такая команда осуществлять ежедневное дежурство? (Приступить к дежурству сторожа могут не одновременно, в один день могут дежурить несколько сторожей.)
Занумеруем сторожей в порядке убывания разряда. У сторожей жизнь делится на равные периоды сна и дежурства. При этом у каждого сторожа периоды, как минимум, втрое короче, чем у предыдущего; поэтому любой период предыдущего делится, как минимум, на три части периодами следующего, причем как минимум две из этих частей будут целыми периодами следующего. Следовательно, период сна предыдущего содержит целый период сна следующего. Так продолжая, найдём вложенный друг в друга набор периодов снов всех сторожей. В день, входящий в самый маленький из вложенных периодов сна, никто не дежурит.
Ответ: не может.
Задача 9
Докажите, что любой выпуклый многоугольник Ф содержит два многоугольника Ф1 и Ф2, которые не пересекаются и подобны Ф с коэффициентом подобия 1/2.
Пусть А и В – пара наиболее удаленных друг от друга точек многоугольника Ф. Тогда в качестве искомых фигур Ф1 и Ф2 можно взять многоугольники гомотетичные Ф относительно точек А и В соответственно с коэффициентом гомотетии 1/2. Действительно, Ф1 и Ф2 не пересекаются, поскольку лежат по разные стороны от серединного перпендикуляра отрезка АВ. Кроме того Фi содержится в Ф, поскольку Ф – выпуклый многоугольник.
Задача 10
Докажите, что если многоугольник имеет несколько (больше двух) осей симметрии, то все они пересекаются в одной точке.
Допустим, что у многоугольника нашлось три оси симметрии, которые не пересекаются в одной точке, то есть они образуют треугольник. Пусть Х – точка многоугольника, которая наиболее удалена от некоторой внутренней точки М этого треугольника. Точки Х и М лежат по одну сторону от одной из рассмотренных осей симметрии k. Если точка Х’ – точка, симметричная точке Х относительно прямой k, то МХ’ > МХ и точка Х’ более удалена от точки М чем точка Х. Получаем противоречие, поэтому все оси симметрии многоугольника пересекаются в одной точке.
Published: Oct 23, 2017
Latest Revision: Oct 23, 2017
Ourboox Unique Identifier: OB-376330
Copyright © 2017
