Олимпиадни задачи по математика на тема - принцип на Дирихле
Олимпиадни задачи по математика на тема "Принцип на Дирихле". Решения.
В гората има милион дървета. Известно е, че всеки от тях има не повече от 600 000 игли. Докажете, че в гората има две коледни елхи с еднакъв брой игли.
Пред нас има милион „заешки“ дървета и, уви, само 600 001 клетки с номера от 0 до 600 000. Всяко „заешко“ дърво е засадено от нас в клетка с номер, равен на броя на иглите на това дърво. Тъй като има много повече „зайци“, отколкото клетки, има поне два „зайци“ в някоя клетка - ако нямаше повече от един във всяка, тогава нямаше да има повече от 600 001 „зайци“-дървета. Но в края на краищата, ако две "заешки" дървета седят в една и съща клетка, тогава броят на иглите е еднакъв за тях.
Дадени са ви 12 цели числа. Докажете, че може да се изберат две от тях, чиято разлика се дели на 11.
Остатъците по модул 11 са „клетки“, числата са „зайци“.
Повече от 5 милиона души живеят в град Ленинград. Докажете, че някои двама от тях имат еднакъв брой косми на главите си, ако е известно, че всеки човек има по-малко от един милион косъма на главата си.
Изградете милион клетки с числа от 0 до 999999 и настанете хората там, като поставите всеки ленинградец в клетка, чийто брой е равен на броя на космите на главата му.
В магазина бяха донесени 25 кашона с три различни сорта ябълки (всяка кутия съдържа само един сорт ябълки). Докажете, че сред тях има поне 9 кашона с ябълки от един и същи сорт.
Ще бъдат засадени 25 сандъчета-"зайчета" в 3 килийки-разновидности. Тъй като 25 = 3 • 8 + 1, тогава прилагаме „обобщения принцип на Дирихле“ за N = 3, k = 8 и получаваме, че има поне 9 кутии в някаква клетка.
В страната на Курландия има m футболни отбора (по 11 футболисти). Всички играчи се събраха на летището за пътуване до друга държаваза важен мач. Самолетът е извършил 10 полета, превозвайки m пътници всеки път. Друг играч отлетя с хеликоптер до мястото на предстоящия мач. Докажете, че поне един екип е бил напълно доставен в друга държава.
Тъй като бяха транспортирани само 10m + 1 футболисти, след като ги настанихме в отборни клетки, получаваме, че 11 футболисти седят в някаква клетка.
Дадени са 8 различни естествени числа, не по-големи от 15. Докажете, че сред техните положителни двойки разлики има три еднакви.
Може да има 14 различни разлики - от 1 до 14 - това са 14-те клетки, в които ще засадим зайци. Кои ще бъдат нашите зайци? Те, разбира се, трябва да са разликите между дадените ни двойки естествени числа. Въпреки това има 28 двойки и те могат да бъдат поставени в 14 клетки, така че точно два „заека“ да седят във всяка клетка (и следователно всяка клетка ще има по-малко от три). Тук трябва да използваме допълнително съображение: не повече от един заек може да седи в клетка номер 14, тъй като числото 14 може да бъде написано като разликата на две естествени числа, непревишаващи 15, само по един начин: 14 \u003d 15 - 1. Следователно има поне 27 заека в останалите 13 клетки и прилагането на обобщения принцип на Дирихле ни дава желания резултат.
Докажете, че във всяка компания от 5 души има двама души, които имат еднакъв брой познати в тази компания.
Има само 5 опции за броя на познатите: от 0 до 4. Остава да отбележим, че ако някой има 4 познати, то никой не може да има 0 познати.
Няколко футболни отбора играят турнир от един кръг. Докажете, че във всеки момент от турнира има два отбора, които са изиграли еднакъв брой мачове досега.
Нека има общо n отбора. След това има n опции за броя на отборите, с които този отбор е играл: от 0 до n - 1. Оставаимайте предвид, че ако един отбор играе с всички n - 1-ви, тогава никой друг отбор не може да играе с никого.
а) Какъв е най-големият брой полета на дъската 8? 8 може да бъде боядисан в черно, така че да има поне едно незащриховано поле във всеки ъгъл на изгледа на трите полета?
б) Какъв е най-малкият брой полета на дъската 8? 8 може да бъде боядисан в черно, така че да има поне една черна кутия във всеки ъгъл на изгледа?
а) Разделете дъската на 16 квадрата 2? 2 са клетки; зайците, разбира се, ще бъдат черните полета.
10 ученици на олимпиадата решиха 35 задачи, като е известно, че сред тях има ученици, които са решили точно една задача, ученици, които са решили точно две задачи, и ученици, които са решили точно три задачи. Докажете, че има ученик, който е решил поне пет задачи.
От условията следва, че има 7 ученици, които са решили 35 - 6 = 29 задачи. Тъй като 29 = 4 • 7 + 1, има ученик, който е решил поне пет задачи.
Какъв е най-големият брой царе, които могат да бъдат поставени на шахматна дъска, така че двама от тях да не се атакуват един друг?
Отговор: 16 царе. Нека разделим дъската на 16 полета, всяко от които може да съдържа не повече от един цар.
Докажете, че един равностранен триъгълник не може да бъде покрит от два по-малки равностранни триъгълника.
Всеки от по-малките триъгълници не може да покрива повече от един връх на по-големия триъгълник.
51 точки се хвърлят в квадрат със страна 1 метър. Докажете, че някои три от тях могат да бъдат покрити от квадрат със страна 20 cm.
Нека разделим нашия квадрат на 25 квадрата със страна 20 см. Според обобщения принцип на Дирихле поне три точки от 51 хвърлени ще попаднат в един от тях.
Петима млади работници получиха заплата от 1500 рубли за всички. Всеки от тяхиска да си купи магнетофон за 320 рубли. Докажете, че един от тях ще трябва да изчака до следващата заплата, за да направи покупка.
Ако всеки от работниците можеше да си купи магнетофон, тогава те биха имали общо най-малко 5 х 320 = 1600 рубли.
В бригадата са 7 души, чиято обща възраст е 332 години. Докажете, че сред тях е възможно да изберете трима души, чийто сбор от възрасти е най-малко 142 години.
Нека боядисаме цялата земя в синьо, а всички точки, диаметрално противоположни на земята - в червено. След това задължително има точка, която е боядисана и в двата цвята. Необходимо е да се изкопае тунел в него.
Докажете, че има две степени на две, чиято разлика се дели на 1987.
Да разгледаме степените 1988 и техните остатъци по модул 1987.
Докажете, че от 52 цели числа винаги ще има 2, чиято квадратна разлика се дели на 100.
Квадратите, когато са разделени на 100, могат да дадат само 51 остатъка, тъй като остатъците от x и 100 - x, когато са повдигнати на квадрат, дават същия остатък.
Докажете, че сред числата, записани само с единици, има число, което се дели на 1987.
Помислете за 1988 числа - "зайци" 1, 11, 111, ..., 111 ... 11 (1988 единици) и ги поставете в 1987 клетки с числа 0, 1, 2, ..., 1986 - всяко число попада в клетка с число, равно на остатъка от деленето на това число на 1987. Тогава (според принципа на Дирихле) ще има две числа, които имат еднакви остатъци при деление за 1987. Нека това са числата 11 ... 11 (m единици) и 11 ... 11 (n единици), с m>gt; н. Но тяхната разлика, която е разделена на 1987 г., е равна на 11 ... 1100 ... 00 (m - n единици и n нули). Нека съкратим всички нули - защото те нямат нищо общо с делимостта на 1987 - и ще получим число само с единици, което се дели на 1987.
Докажете, че съществува степен на 3, завършваща на 001.
Ако 3m и 3n са степени на тройка, които дават един и същ остатък при разделяне на 1000, тогава 3m - 3n = 3n(3m - n - 1) се дели на 1000 (приемаме за категоричност, че m> n).
В клетките на таблица 3? Поставени са 3 числа - 1, 0, 1. Докажете, че някои две от 8-те суми по всички редове, всички колони и два главни диагонала ще бъдат равни.
Тези суми могат да приемат само 7 различни стойности: от -3 до 3.
На кръглата маса сядат стотина души, като повече от половината са мъже. Докажете, че двама мъже седят един срещу друг.
Разделяме всички хора на 50 двойки, така че във всяка двойка да има двама души, седнали един срещу друг. Ясно е, че в една от тези двойки "клетки" и двамата са мъже.
15 момчета събраха 100 ореха. Докажете, че някои двама от тях са събрали еднакъв брой ядки.
Ако това не е така, тогава е очевидно, че момчетата са събрали поне 0 + 1 + 2 + ... + 14 = 105 ядки - противоречие.
Числата 1, 2, ..., 9 бяха разделени на три групи. Докажете, че произведението на числата в една от групите е поне 72.
Произведението на числата във всички групи е 9! = 362880, но 71? = 357911.
В таблица 10? Подредени са 10 цели числа, като произволни две числа в съседни клетки се различават с не повече от 5. Докажете, че сред тези числа има две еднакви.
Тъй като можете да стигнете от всяка клетка до всяка друга, като се придвижите до следващата клетка не повече от 19 пъти, тогава всички числа са между числата a и a + 95, където a е минимумът от всички поставени числа. Следователно сред тези числа има не повече от 96 различни.
Докажете, че сред всеки 6 души има или трима по двойки познати, или трима по двойки непознати.
Този човек сред другите петима има или поне трима познати, или поне трима непознатина него. Да разгледаме например първия случай. Сред тези трима души има или двама познати - тогава те, заедно с първоначално избрания от нас човек, образуват необходимото трио, или и тримата са непознати по двойки.
На карираната равнина са дадени 5 произволни възела на мрежата. Докажете, че средата на една от отсечките, свързваща произволни две от тези точки, също е възел на мрежата.
Помислете за координатите на тези точки и техните остатъци, когато се разделят на 2.
Има 200 ботуши на склад в размери 41, 42 и 43, като сред тези 600 ботуши има 300 леви и 300 десни. Докажете, че от тях могат да се направят поне 100 чифта добри обувки.
Във всеки размер някои ботуши са по-малки: десни или леви. Нека напишем тези видове ботуши по размер. Някой тип, например ляво, ще се повтори поне два пъти, например в размери 41 и 42. Но тъй като броят на оставените ботуши в тези размери е не по-малко от 100 общо (защо?), тогава имаме поне 100 добри чифта обувки в тези размери.
Азбуката на езика на племето Ни-Бум-Бум има 22 съгласни и 11 гласни, а думата в този език е произволна буквена комбинация, в която няма две последователни съгласни и нито една буква не се използва два пъти. Азбуката беше разделена на 6 непразни групи. Докажете, че от всички букви на една от групите може да се образува дума.
Докажете, че в една от групите разликата между броя на съгласните и броя на гласните е най-много 1.
Докажете, че сред всеки 10 цели числа има няколко, чийто сбор се дели на 10.
Помислете за 10 суми: x1, x1 + x2, …, x1 + x2 + … + x10 и техните остатъци, когато се разделят на 10.
Дадени са 11 различни естествени числа, не по-големи от 20. Докажете, че от тях могат да се изберат две числа, едното от които се дели на другото.
Разбийте числата от 1 до 20 на 10 комплекта, във всеки от които по произволендвойка числа, едното се дели на друго: 11, 13, 15, 17, 19, 1,2,4,8,16, 3,6,12, 5,10,20, 7,14, 9,18.