| Описание и условия задач |
Решения задач части 1 |
Решения задач части 2 |
Решения задач части 3 |
Решения задач части 4 |
1.1 В учреждении работает 40 человек. Найдется месяц в году в котором отмечают свой день рождения не менее четырех сотрудников?
Как известно в году всегда 12 месяцев. 12 месяцев и есть те полочки по которым раскладываем 40 сотрудников. Делим 40 на 12, получаем: $3\frac{1}{3}$, таким образом $\left\lceil\frac{40}{12}\right\rceil=4$. Ответ утвердительный. Между прочим, так как $\left\lfloor\frac{40}{12}\right\rfloor=3$, найдется также месяц, где день рождения отмечают не более 3х человек.
1.2 На заводе 45 цехов и 1000 работников. Какое максимально возможное количество работников может быть в самом маленьком цеху?
Согласно второму утверждению принципа Дирихле, обязательно найдется цех, в котором работает не более чем $\left\lfloor\frac{1000}{45}\right\rfloor=\left\lfloor22\frac{2}{9}\right\rfloor=22$ человека. Цех из 22х человек будет минимальным, если, например, в 44х цехах работает 22 человека, а в оставшемся цеху $1000-22\cdot44=32$ человека. (Другой пример: 40 цехов по 22 человека и 5 цехов по 24 человека.) С другой стороны, если в минимальном цеху работает не менее 23х человек, то общее количество работников не менее $45\cdot23=1035$, что противоречит условию. Таким образом, ответ: 22 человека.
1.3 В ковре размером 4м×4м моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1м×1м, не содержащий внутри себя дырок. (Дырки считать точечными.)
Источник: E.Ю.Иванова. «Олимпиадные задачи» МГУ Мехмат М 2008. Задача 19 (без решения)
Еще один пример на округление вниз. Разрезаем на 16 ковриков размером 1м×1м каждый. Дырки, находящиеся на линии разреза можно игнорировать, но даже если таких нет, найдется коврик, содержащий не более $\left\lfloor\frac{15}{16}\right\rfloor = 0$ дырок.
1.4Сколько карт надо вытянуть наугад из преферансной колоды, чтобы среди них наверняка были: а) две карты одной масти; б) две карты красной масти; в) две карты одного достоинства; г) четыре карты одной масти; д) два туза.
а) 4 карточных масти являются ящиками. Общее количество карт не имеет значения, так как из 5 карт обязательно найдутся две карты одной масти.
б) Здесь ящиками являются цвета мастей: красный и черный. Имеется два таких ящика, следовательно достаточно трех карт, чтобы две из них были одной масти.
б) Имеется 8 достоинств: числа: 7,8,9,10 и «картинки»: В,Д,К,Т. Таким образом достаточно 9 карт.
г) Следует найти наименьшее $x$, такое, что $\left\lceil\frac{x}{4}\right\rceil = 4$. Таким числом является $13=4\cdot3+1$, поскольку $\left\lceil\frac{12}{4}\right\rceil = 3$. В общем случае наименьшее количество предметов, гарантирующих $k$ предметов в одном из $n$ ящиков равно $n(k-1)+1$.
д) В данном случае принцип Дирихле не работает, так как речь идет о конкретном достоинстве. Рассмотрим наихудший вариант, когда все четыре туза окажутся в конце колоды. Тогда придется перебрать 30 карт, чтобы получить, наконец, заветные тузы.
Источник: «А.И.Орлов. «Принцип Дирихле». Квант №7, 1971 стр. 20
Присоединим к отмеченным дугам дуги, симметричные им относительно центра окружности. Получим множество дуг, симметричное относительно центра окружности, общая длина которых в два раза больше общей длины исходных дуг, а следовательно меньше длины окружности. Согласно принципу Дирихле в «непрерывной» формулировке, на окружности найдется точка $P_1$, не принадлежащая ни одной из дуг. В силу симметричности множества дуг, точка $P_2$, симметричная точке $P_1$ относительно центра окружности, также не принадлежит ни одной из дуг. Таким образом, $P_1P_2$ — искомый диаметр окружности.
1.6В квадрате $ABCD$, длина стороны которого равна 1, расположены окружности, сумма радиусов которых равна 0,6. Докажите, что существует прямая, параллельная стороне $AB$, содержащая точки как минимум двух окружностей.
Источник: «А.И.Орлов. «Принцип Дирихле». Квант №7, 1971 стр. 20
Спроецируем окружности на сторону $AD$. Проекция каждой из окружностей является отрезком, длиной равной диаметру окружности. Поскольку сумма радиусов окружностей равна 0,6, сумма их диаметров, а следовательно сумма длин отрезков равна 1,2, что больше длины стороны $AD$, равной 1. Таким образом, согласно принципу Дирихле, на стороне $AD$ найдется точка $P$, принадлежащая как минимум двум отрезкам $s_1$ и $s_2$. Пусть $O_1$ и $O_2$ — окружности, проецирующиеся в отрезки $s_1$ и $s_2$. Каждая из этих окружностей, содержит точки (одну или две), проецирующиеся в точку $P$. Через точку $P$ проведем прямую, параллельную $AB$. Эта прямая перпендикулярна $AD$, следовательно содержит все точки, проецирующиеся в точку $P$. В частности она содержит точки окружностей $O_1$ и $O_2$.
1.7Для всякого ли натурального числа $n$ существуют две различные степени $n^{k_1}$, $n^{k_2}$ у которых совпадают: а) последняя цифра; б) две последние цифры; в) три последние цифры?
Очевидно, если выполнено в), то выполнено также а) и б), поэтому достаточно доказать совпадение трех последних цифр. Для этого заметим, что число, составленное последними тремя цифрами есть остаток от деления на 1000. Поскольку при делении на 1000 возможны 1000 различных остатков, среди 1001 различных степеней числа $n$, найдутся два числа, дающие одинаковые остатки при делении на 1000. У этих чисел последние три цифры совпадают.
1.8Какое наименьшее количество из первых 555 натуральных чисел следует выбрать случайным образом, чтобы среди них обязательно нашлись: а) число оканчивающееся нулем; б) два четных числа; в) три с совпадающей последней цифрой; г) четыре с совпадающим остатком от деления на 7; д) пять с совпадающей суммой цифр.
а) В каждой из 4х полных сотен есть 10 чисел оканчивающихся нулем (10а+10, 10a+20 ... 10a+100). Остается неполная сотня содержащая 5 чисел с нулем в конце: 510, 520 ... 550. Таким образом имеется 45 чисел, оканчивающихся нулем, и если перемешать все 555 чисел случайным образом, то в худшем случае требуемые 45 чисел окажутся в конце, так что придется выбрать $500-45+1=446$ чисел.
б) Среди первых 555 натуральных чисел есть 277 четных и 278 нечетных. При этом можно перебрать все нечетные числа и лишь потом попадутся 2 четных. Стало быть, чтобы действовать наверняка, надо выбрать 280 чисел и ничуть ни меньше. Еще один пример неоправданного соблазна применения принципа Дирихле.
в) Учитывая опыт предыдущих задач, достаточно лишь сверить ответ: $2\cdot10+1=21$
г) И здесь применим принцип Дирихле. Ответ: $3\cdot7+1=22$
д) Среди натуральных чисел, не бо́льших 555, наименьшую сумму цифр, равную 1 имеет число 1, тогда как наибольшей суммой цифр, равной 22, обладает число 499. Таким образом получаем 22 возможных сумм цифр, что на первый взгляд дает $4\cdot22+1=89$ чисел.
На самом деле, некоторые суммы цифр встречаются менее 5 раз, так что если они попадутся при выборе, это лишь удлинит поиск. Выпишем эти суммы:
| Сумма цифр | Соответствующие числа | Количество |
|---|---|---|
| 1 | 1 10 100 | 3 |
| 21 | 399 489 498 | 3 |
| 22 | 499 | 1 |
Таким образом, получаем 3 «лишних» суммы цифр, соответствующих 7 «лишним» числам, выбор которых заведомо идет мимо цели. По закону бутерброда, все эти 7 чисел могут оказаться среди выбранных. Остается $22-3=19$ «порядочных» сумм, так что требуется еще $4\cdot19+1=77$ чисел, что вместе с «лишними» дает $84$ числа.
К возможному сюрпризу некоторых читателей, результат оказался меньше, чем первоначальное значение. В действительности, здесь нет никакого сюрприза: рассматривая некоторые суммы цифр в отдельности, мы уменьшаем количество оставшихся сумм, что с лихвой компенсирует наличие «лишних» чисел.
А если пойти дальше? Тогда, поиск, возможно удастся сделать еще короче. Сумму цифр 2 дают пять чисел: 2, 11, 101, 110, 200. Предположим, что только 4 из них появились вначале, а последнее, как назло, никак не появится. Вместе с предыдущими суммами получаем 7+4=11 «лишних» чисел и 18 оставшихся «порядочных» сумм, что дает $4\cdot18+1+11=84$ пробы, ровно столько же, сколько и раньше.
Следующая попытка: сумму цифр 20 дает 6 чисел: 299, 389, 398, 479, 488, 497. Снова предположим, что только 4 из них появились, так что 11+4=15 «лишних» чисел и 17 оставшихся «порядочных» сумм дает ... $4\cdot17+1+15=84$! Какой-то заколдованный круг ... хотя ... конечно, увеличивая на 4 количество «лишних» чисел, мы уменьшаем на единицу количество «порядочных» сумм, а это есть ничто иное, как множитель числа 4. Теперь понятно, что меньше 84 никак не получится.
| Описание и условия задач |
Решения задач части 1 |
Решения задач части 2 |
Решения задач части 3 |
Решения задач части 4 |
Комментариев нет:
Отправить комментарий