Домашняя контрольная-3. Задачи на принцип Дирихле. Максимум 1 балл за задачу.

Решите ОДНУ задачу согласно Вашему варианту (номеру по списку группы)

1. Обязательно ли среди 25 монет достоинством 1,2,3,5 копеек найдется семь монет одинакового достоинства?
2. Обязательно ли среди 15 монет достоинством 1,3,5 рублей найдется семь монет одинакового достоинства?
3. На плоскости нарисовано 12 прямых, проходящих через точку О. Докажите, что можно выбрать две из них так, что угол между ними будет меньше 17 градусов.
4. Докажите, что в любой футбольной команде из 11 игроков есть два игрока, которые родились в один и тот же день недели.
5. Докажите, что среди жителей Москвы найдутся десять тысяч, празднующих день рождения в один и тот же день.
6. В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?
7. В каждой вершине куба написано число 1 или число -1. На каждой грани куба написана сумма четырех чисел, написанных в вершинах этой грани. Может ли так оказаться, что все числа, написанные на гранях, различны?
8. В каждой вершине куба написано число 1 или число 0. На каждой грани куба написана сумма четырех чисел, написанных в вершинах этой грани. Может ли так оказаться, что все числа, написанные на гранях, различны?
9. В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.
10. В лесу растет два миллиона елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся четыре елки с одинаковым числом иголок.
11. Сто человек сидят за круглым столом, причем более половины из них - мужчины. Докажите, что какие-то два мужчины сидят друг напротив друга
12. На планете Тау Кита суша занимает больше половины всей площади. Доказать, что таукитяне могут прорыть через центр планеты шахту, соединяющую сушу с сушей.
13. Какое наибольшее число королей можно расставить на шахматной доске так, чтобы никакие два из них не били друг друга? Подсказка: Если в квадрате из четырех клеток находятся два короля, то они бьют друг друга.
14. В классе 30 человек. В диктанте Витя Малов сделал 12 ошибок, а каждый из остальных учеников – не больше. Докажите, что по крайней мере трое учеников сделали одинаковое количество (быть может, и ноль) ошибок.
15. В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежат яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?
16. В шкафу лежат вперемешку 5 пар светлых носков и 5 пар темных носков одинаковых размера и фасона. Какое наименьшее количество носков надо взять наугад из шкафа, чтобы среди них была хоть одна пара (на правую и левую ноги) одинакового цвета?
17. Докажите, что из любых двенадцати натуральных чисел можно выбрать два, разность которых делится на 11.
18. В соревнованиях по вольной борьбе участвовало 12 человек. Каждый участник должен был встретиться с каждым из остальных по одному разу. Докажите, что в любой момент соревнования имеются два участника, проведшие одинаковое число схваток.
19. Класс, в котором 25 человек. Из любых случайно выбранных 3 учеников двое будут друзьями. Необходимо доказать, что в классе находится школьник, у которого больше 11 приятелей.
20. Прямоугольник с площадью 5 х 6 клеток (30 клеток), закрашенных только 19. Можно ли обнаружить квадрат площадью 2 х 2 клетки, в котором минимум три будут закрашены?
21. Предположим, на листике тетради в клетку ученик произвольно в узлах клеточек проставил 5 точек. Необходимо доказать, что как минимум один отрезок с вершинами в этих точках пройдет через узел клеточки.
22. Допустим, вокруг округлённого стола стоят на равном расстоянии друг от друга m флажков разных стран, а за столом сидят m представителей от каждой страны, причем каждый из них расположился рядом с чужим флажком. Нужно доказать, что при определенном вращении стола хотя бы двое из представителей окажутся возле своих флажков.
23. В середине равностороннего треугольника АВС (у которого АВ = ВС = АС = 1) разместилось 5 точек. Необходимо доказать, что две из них располагаются на расстоянии меньше 0,5.
24. Прямая k проходит через плоскость треугольника ABC, однако не пересекает ни одну его вершину. Необходимо доказать, что она не может пересекать три его стороны.
25. В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка — точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.
26. Пятеро программистов получили на всех зарплату - 1750 долларов. Каждый из них хочет купить себе новый компьютер за 360 долларов. Докажите, что кому-то из них это не светит.

Дискретная математика.