В мешке лежат шарики двух разных цветов. Какое наименьшее число шариков нужно вынуть из мешка, чтобы среди ни обязательно оказались два шарика одного цвета?

Принцип Дирихле

Рассмотрим пример.

В классе 34 ученика. Докажите, что среди них обязательно найдутся по крайней мере два ученика, у которых фамиля начинается с одной буквы.

Доказательство простое. В русском языке алфавит содержит 33 буквы. Предположим, что нет таких учеников, у которых бы фамилия начиналась с одной буквы. Тогда учеников должно быть не более 33, а их 34.

Логический прием, который был использован при решении этой задачи, называется принципом Дирихле.

 Существует несколько формулировок этого принципа. Самая популярная следующая: «Если в п клетках сидят т зайцев, причем т > п, то хотя бы в одной клетке сидят, по крайней мере, два зайца»

Например, если 4 кролика разместить в 3 клетках, то найдется хотя бы одна клетка, в которой будет не менее 2 кроликов (сделать рисунок). Предположим, что не существует клетки, где сидят два кролика. Тогда в трех клетках окажется не более 3 кроликов (сделать рисунок), а их 4 – противоречие.

Запишем принцип Дирихле: если по N разложить предметы, число которых M больше N, то найдется ящик, в котором будет находится больше одного предмета.

На первый взгляд непонятно, почему это совершенно очевидное предложение, тем не менее, является мощным математическим методом решения задач, причем, самых разнообразных. Дело в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «предметов», а что – в роли «ящиков».

Вернемся к первой задаче. Что в ней предметы? (ученики, M=34). Что в ней ящики? (количество букв в алфавите, N =33). M>N, то по принципу Дирихле хотя бы на одну букву будет приходится две фамилии.

Вернемся ко второй задаче. Что в ней предметы? (кролики, M= 4). Что в ней ящики? (клетки, N=3).M>N, то по принципу Дирихле хотя бы в одной клетке окажется два кролика.

Обобщенный принцип Дирихле: если по N ящикам разложить предметы, число которых М больше, чем N (где к – натуральное число), то найдется ящик, в котором находятся более к предметов.

В мешке лежат шарики двух разных цветов. Какое наименьшее число шариков нужно вынуть из мешка, чтобы среди ни обязательно оказались два шарика одного цвета?

Решение:

Здесь роль предметов играют шарики (М=?), роль ящиков - цвета (N=2).Чтобы M>N, т.е. в одном ящике оказалось два предмета, их должно быть больше двух, т.е. М=3

В коробке лежат карандаши: 7 красных и 5 синих. В темноте берут карандаши. Сколько карандашей надо взять, чтобы среди них было не менее 2 красных и не менее 3 синих?

Решение: Если предположить, что сначала будут попадаться только красные карандаши, то для того, чтобы было 3 синих, нужно взять 7(красные)+3(N)=10. Это «худший» вариант развития событий, т.к. красных карандашей больше.

В мешке лежат 10 черных и 10 белых шаров. Они тщательно перемешены и неразлечимы на ощупь. Какое наименьшее количество шаров нужно вынуть из мешка, чтобы среди них наверняка оказались два шара 1) одного цвета, 2)разного цвета, 3) белого цвета.

Решение:1)Если предположить, что предметы – шарики, которые нужно взять (М=?), а количество ящиков - цвета N=2, то по принципу Дирихле М=3

2)если предположить, что сначала будут попадаться шары только одного цвета, то N=10,следовательно, М=11

3)если предположить, что все время будут попадаться шары черного цвета, то М=12.

При каком наименьшем количестве учеников школы среди них обязательно найдутся двое, у которых день и месяц рождения совпадают?

Решение: Дней в году N=365 или 366,то принципу Дирихле М= 366 или 367.

В лесу растет миллион елок. Известно, что на каждой из них не более 600 000 иголок. Докажите, что в лесу найдутся хотя бы две елки с одинаковым числом иголок.

Решение: Если предположить, что у всех елок разное количество иголок, то таких елок 600 000 (это ящики, N= 600 000), а по условию елок 1000 000=М, то М>N,по принципу Дирихле найдутся хотя бы две елки «в одном ящике», т.те с одинаковым количеством иголок.

В городе Санкт-Петербурге живет более 4млн. человек. Докажите, что у каких-то двух из них одинаковое количество волос на голове, если известно, что у любого человека на голове не более миллиона волос.

Решение: Если предположить, что у всех людей разное количество волос, то таких людей N=1000 000 (ящики), а по условию людей М=4 000 000. М>N, то по принципу Дирихле найдутся хотя бы два человека с одинаковым количеством волос.

В магазин привезли 25 ящиков с яблоками трех сортов, причем в каждом ящике лежали яблоки какого-то одного сорта. Можно ли найти 9 ящиков с яблоками одного сорта?

Решение. 25:3=8 (ост.1). 25=8*3+1. к=3, N=8, M>N, то принципу Дирихле найдутся хотя бы один ящик, в котором находятся более, чем к=3 предметов, т.е. 4 предмета.

В темной кладовой лежат ботинки одного размера: 10 пар черных и 10 пар коричневых. Найдите наименьшее число ботинок, которое нужно взять из кладовой, чтобы среди них оказалась хотя бы одна пара (левый и правый) одного цвета. В темноте нельзя определить не только цвет ботинок, но и левой от правого.

Решение: Если предположить (худший вариант), что подряд попадаются ботинки на одну ногу (20), а затем ботинок на другую ногу, то20+1=21, среди них будут ботинки на одну ногу.

В ящике 25 белых шаров, 25 черных, 20 синих и 10 красных. На ощупь шары неотличимы друг от друга. Шары вынимают из ящика в темноте. Какое наименьшее количество шаров нужно вынуть, чтобы среди них обязательно оказалось: 1)10 шаров одного цвета; 2) 10 белых шаров?

Решение: 1)в худшем случае это будут 9 белых шаров+9 черных шаров+9 синих+9 красных=36 шаров. В любом случае, следующий шар будет иметь цвет, который станет 10. М=37.

2)В худшем случае это будут 25 черных + 20 синих + 10 красных + 10 белых шаров =65 шаров.

Принцип Дирихле

Рассмотрим пример.

В классе 34 ученика. Докажите, что среди них обязательно найдутся по крайней мере два ученика, у которых фамиля начинается с одной буквы.

Доказательство простое. В русском языке алфавит содержит 33 буквы. Предположим, что нет таких учеников, у которых бы фамилия начиналась с одной буквы. Тогда учеников должно быть не более 33, а их 34.

Логический прием, который был использован при решении этой задачи, называется принципом Дирихле.

 Существует несколько формулировок этого принципа. Самая популярная следующая: «Если в п клетках сидят т зайцев, причем т > п, то хотя бы в одной клетке сидят, по крайней мере, два зайца»

Например, если 4 кролика разместить в 3 клетках, то найдется хотя бы одна клетка, в которой будет не менее 2 кроликов (сделать рисунок). Предположим, что не существует клетки, где сидят два кролика. Тогда в трех клетках окажется не более 3 кроликов (сделать рисунок), а их 4 – противоречие.

Запишем принцип Дирихле: если по N разложить предметы, число которых M больше N, то найдется ящик, в котором будет находится больше одного предмета.

На первый взгляд непонятно, почему это совершенно очевидное предложение, тем не менее, является мощным математическим методом решения задач, причем, самых разнообразных. Дело в том, что в каждой конкретной задаче нелегко понять, что же здесь выступает в роли «предметов», а что – в роли «ящиков».

Вернемся к первой задаче. Что в ней предметы? (ученики, M=34). Что в ней ящики? (количество букв в алфавите, N =33). M>N, то по принципу Дирихле хотя бы на одну букву будет приходится две фамилии.

Вернемся ко второй задаче. Что в ней предметы? (кролики, M= 4). Что в ней ящики? (клетки, N=3).M>N, то по принципу Дирихле хотя бы в одной клетке окажется два кролика.

Обобщенный принцип Дирихле: если по N ящикам разложить предметы, число которых М больше, чем N (где к – натуральное число), то найдется ящик, в котором находятся более к предметов.

В мешке лежат шарики двух разных цветов. Какое наименьшее число шариков нужно вынуть из мешка, чтобы среди ни обязательно оказались два шарика одного цвета?

Решение:

Здесь роль предметов играют шарики (М=?), роль ящиков - цвета (N=2).Чтобы M>N, т.е. в одном ящике оказалось два предмета, их должно быть больше двух, т.е. М=3