Принцип дирихле что это такое как решать
Принцип дирихле что это такое как решать
ПРИНЦИП ДИРИХЛЕ
Автор работы награжден дипломом победителя III степени
Введение
Объектом моих исследований являются способы и методы решения логических задач. Логическая задача – это особый вид задачи, который развивает логику, образное и творческое мышление, поэтому часто такие задачи являются олимпиадными. Решение таких задач увлекательное занятие, поскольку для решения большинства из них требуется не только знание определенного программного материала, но и логическое мышление. Я уже рассматривал применение кругов Эйлера и задачи на шахматной доске.
Разнообразие логических задач велико, велико и количество способов их решения. При решении многих задач я столкнулся с еще одним методом рассуждения — «от противного». Меня заинтересовала одна из его форм — принцип Дирихле. Способ решения задач с помощью данного принципа я сделать предметом исследования данной работы.
Гипотеза: принцип Дирихле позволяет решать некоторые логические задачи, которые сложно решать другими способами.
Цель работы:
исследование эффективности применения принципа Дирихле в решении задач;
получение знаний о применении и сферах использования принципа Дирихле.
В ходе выполнения работы мной были решены следующие задачи:
изучить литературу и собрать информацию о принципе Дирихле;
отобрать и систематизировать задачи, решаемые с помощью принципа Дирихле;
научиться самостоятельно решать задачи данным методом.
Мной использовались следующие методы исследования:
Моя работа весьма актуальна, так как принцип Дирихле не рассматривается в учебниках математики, а полученные знания пригодятся для сдачи экзаменов и решении практических задач в жизни.
I. Общая информация о принципе Дирихле
I. 1. Биография Дирихле
Дирихле Петер Густав Лежен (13.02.1805 – 05.05.1859) – немецкий математик. Родился в Дюрене. В 1822-1827гг. был домашним учителем в Париже. Входил в кружок молодых ученых, которые группировались вокруг Ж. Фурье.
В 1825 г. Дирихле вместе с А. Лежандром доказал великую теорему Ферма для частного случая n=5. В 1827 занял место доцента в Бреславе; с 1829 работал в Берлине. В 1831-1855гг. – профессор Берлинского университета, после смерти К. Гаусса (1855г.) – Гёттингенского университета.
Сделал ряд крупных открытий в теории чисел; установил формулы для числа классов бинарных квадратичных форм с заданным определителем и доказал теорему о бесконечности количества простых чисел в арифметической прогрессии из целых чисел, первый член и разность которой взаимно просты. К решению этих задач применил аналитические функции, названные функциями (рядами) Дирихле. Создал общую теорию алгебры, единиц в алгебраическом числовом поле. В области математического анализа впервые точно сформулировал и исследовал понятие условной сходимости ряда, дал строгое доказательство возможности разложения в ряд Фурье кусочно-непрерывной и монотонной функций, что послужило обоснованием для многих дальнейших исследований. Значительны труды Дирихле в механике и математической физике, в частности, в теории потенциала. С именем Дирихле связаны задача, интеграл (ввел интеграл с ядром Дирихле), принцип, характер, ряды. Лекции Дирихле имели огромное влияние на выдающихся математиков более позднего времени, в том числе на Г. Римана, Ф. Эйзенштейна, Л. Кронекера, Ю. Дедекинда.
I. 2. Различные формулировки принципа Дирихле
При решении многих задач используется логический метод рассуждения — «от противного». Здесь мы рассмотрим одну из его форм — принцип Дирихле. Этот принцип утверждает, что если множество из n элементов разбито на m непересекающихся частей, не имеющих общих элементов, где n > m то, по крайней мере, в одной части будет более одного элемента.
На языке отображений эта формулировка означает, что если в А (множестве предметов) больше элементов, чем в В (множестве ящиков), то не существует обратимого отображения А в В.
Другая формулировка “ принципа Дирихле“: если n + 1 предмет поместить в n мест, то обязательно хотя бы в одном месте окажутся хотя бы два предмета.
В шутливой форме принцип Дирихле выглядит так: “нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев “.
I. 3. Обобщение принципа Дирихле
Обобщенный принцип Дирихле также достаточно очевиден: если бы в каждой клетке сидело не более k зайцев, то во всех клетках было бы не более nk зайцев, что противоречит условию. Обобщение принципа используют, когда требуется выявить несколько (три и более) объектов, обладающих некоторым свойством.
В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта. Решение.
Вывод: таким образом, имея принцип Дирихле, мы можем каждый раз не расписывать решение задачи методом от противного, а будем лишь ссылаться на Дирихле фразой «согласно с принципом Дирихле».
II. Применение принципа Дирихле для решения различных задач
II. 1. Принцип Дирихле и арифметика
Задача 2. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.
Решение: 400 > 366.
Задача 3. В классе 40 учеников. Найдётся ли такой месяц в году, в котором отмечают свой день рождения не меньше чем 4 ученика этого класса?
Решение: Рассуждаем от противного. Если бы такого месяца не нашлось, то в каждом из 12 месяцев день рождения отмечали бы не более трёх учеников. Значит, всего учеников было бы не более 12 · 36. Но 40 > 36. Противоречие.
II. 2. Принцип Дирихле в теории чисел
Возможна следующая переформулировка принципа Дирихле:
«Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток».
Задача 1. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.
Задача 2. Из любых трёх целых чисел можно выбрать два, сумма которых чётна. Докажите это.
Решение: Все числа можно разбить на два класса: чётные и нечётные. Невозможно распределить три числа по двум классам так, чтобы ни в какой класс не попало более одного числа. Значит, среди любых трёх целых чисел найдутся два числа одинаковой чётности. Их сумма чётна.
II. 3. Принцип Дирихле и геометрия
Задача 1. В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см.
Решение: Разобьем наш квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадёт, по крайней мере, три точки из 51 брошенной.
Задача 2. Внутри равностороннего треугольника со стороной 1см расположено 5 точек. Докажите, что расстояние между некоторыми двумя из них меньше 0,5см.
Решение: Можно получить 4 «клетки», разбив равносторонний треугольник с помощью проведения отрезков, соединяющих середину сторон. Тогда получим 4 равносторонних треугольника со сторонами по 0,5 см, которые и будут у нас «клетками».
Теория чисел, или высшая арифметика — раздел чистой математики, изучающий свойства натуральных и целых чисел.
Чётное число — целое число, которое делится на 2 без остатка: …−4,−2,0,2,4,6,8,10.
Принцип Дирихле: задачи с решениями
В математике существует множество принципов. Некоторые из них достаточно просты и понятны даже новичку, а некоторые требуют определенных объяснений и доказательств. Однако все они весьма эффективны, и их легко можно применять на практике. Одним из них является принцип Дирихле (известный также как принцип голубей/кроликов). Это достаточно простое утверждение, способное помочь в решении многих математических задач.
История
Современная формулировка и доказательство
На сегодняшний день существует несколько разных формулировок данного принципа. Самая понятная и простая подразумевает, что нельзя посадить 8 кроликов в 3 клетки так, чтобы в каждой было не больше 2. Более научная и сложная формулировка, объясняющая принцип Дирихле, гласит: если в k ячеек находится k+1 зайцев, то, по крайней мере, в 1 ячейке будет располагаться больше одного зайца. А если в k ячеек находится k-1 зайцев, то по крайней мере в 1 ячейке будет располагаться меньше одного зайца. Доказательство этого утверждения совсем простое, так сказать, от противного. Если предположить, что в каждой ячейке располагается зайцев меньше, чем k-1/k, тогда в k ячеек зайцев меньше чем k*k-1/k = k-1, а это противоречит первоначальным условиям.
В действительности такой простой и понятный принцип значительно облегчает решение задач по математике и доказательства многих трудоемких теорем. Просто необходимо учитывать, что зайцев и ячейки можно легко заменить на математические предметы и объекты (цифры, точки, отрезки, фигуры и т. д.).
Еще одна формулировка
Если отобразить множество S, содержащее d+1 элементов, в множество R с совокупностью d элементов, то два элемента из множества S будут иметь одинаковый образ.
Хотя современные ФГОС по математике предъявляют к ученикам творческие требования и предлагают нестандартные варианты, решение через утверждение Дирихле не всегда такое простое и понятное. Иногда очень трудно определить, какую величину считать животным, а какую – клеткой, и каким образом факт наличия двух животных в одной клетке поможет решению задачи. Да и если удастся в этом разобраться, все равно нельзя определить, в какой именно клетке будет находиться объект. То есть можно просто доказать существование такой ячейки, но нельзя конкретизировать ее.
Пример № 1. Геометрия
Современные примеры решения задач демонстрируют, что животными и клетками могут выступать совершенное различные математические предметы.
Прямая k проходит через плоскость треугольника ABC, однако не пересекает ни одну его вершину. Необходимо доказать, что она не может пересекать три его стороны.
Альтернативное решение
В данной задаче мы предположили, что в одной плоскости находятся точки А и В, однако принцип Дирихле не указывает конкретную ячейку, поэтому точно так же мы могли указать, что в одной плоскости разместились вершины С и В, или А и С. Для данной задачи совсем не важно, какую сторону треугольника не пересекает прямая k. Поэтому указанный принцип идеально подходит для ее решения.
Пример № 2. Геометрия
В середине равностороннего треугольника АВС (у которого АВ = ВС = АС = 1) разместилось 5 точек. Необходимо доказать, что две из них располагаются на расстоянии меньше 0,5.
Если провести в правильном треугольнике АВС средние линии, они разделят его на 4 маленьких правильных треугольника со сторонами ½ = 0,5. Предположим, что эти треугольники – ячейки, а точки внутри них – кролики. Получается, у нас есть 5 кроликов и 4 ячейки, следовательно, в одной из них будет находиться как минимум два кролика. Учитывая то, что точки не являются вершинами (так как они располагаются внутри треугольника АВС, а не на одной из его сторон), они будут размещаться внутри маленьких фигур. Следовательно, расстояние между ними будет меньше, чем 0,5 (поскольку величина отрезка внутри треугольника никогда не превышает величины его самой большой стороны).
Пример № 3. Комбинаторика
В других областях также можно удачно применять принцип Дирихле: комбинаторика и математическая физика уже давно опираются на него при решении задач.
Допустим, вокруг округлённого стола стоят на равном расстоянии друг от друга m флажков разных стран, а за столом сидят m представителей от каждой страны, причем каждый из них расположился рядом с чужим флажком. Нужно доказать, что при определенном вращении стола хотя бы двое из представителей окажутся возле своих флажков.
Получается, что существует m-1 способов развернуть стол так, чтобы изменилось взаиморасположение представителей и флажков (если исключить начальное размещение стола), но при этом остается m представителей.
Применим к решению утверждение Дирихле и обозначим, что представители выступают кроликами, а определенные положения стола при вращении – ячейками. При этом нужно провести аналогию между расположением представителя рядом с соответствующем флажком и заполненными ячейками. То есть положительный результат (1 представитель размешается возле своего флажка) равносилен результату «кролик оказывается в клетке». Мы понимаем, что у нас на одну ячейку меньше, чем нужно (m-1), а значит, в одной из них окажется как минимум 2 кролика. При этом не исключены ситуации, что какая-то клетка будет пустой (ни один представитель не совпал с флажком), а в какой-то клетке окажется два, три или даже больше кроликов (два, три и больше представителей совпадут с флажками). Таким образом, при одном определенном вращении как минимум два представителя очутятся возле своих флажков (как минимум два кролика попадут в одну ячейку).
Приступая к решению такой задачи, важно понимать, что начальное положение – это тоже ячейка, но по условию задачи она заведомо пустует, поэтому мы уменьшаем общее количество на 1 (m-1).
Пример № 4. Теория чисел
Принцип Дирихле в теории чисел также имеет огромное значение.
Предположим, на листике тетради в клетку ученик произвольно в узлах клеточек проставил 5 точек. Необходимо доказать, что как минимум один отрезок с вершинами в этих точках пройдет через узел клеточки.
Пример № 5
Достаточно много задач разной сложности можно решить через принцип Дирихле. Задачи с решениями разнообразных математических и логических вопросов достаточно часто опираются на этот принцип.
На прямой дороге вырыты маленькие поперечные канавки. Расстояние между всеми канавками одинаковое и равно оно Ö2 м. Необходимо доказать, что, независимо от ширины канавок, человек, шагающий по дороге с интервалом 1 м, однажды попадет ногой в одну из них.
Для того чтобы облегчить решение, необходимо вообразить, что дорогу можно «намотать» на окружность длиной в Ö2 метров. Получается, что все канавки сольются в 2 противоположных, а шаги человека будут отображаться в форме дуги, равной 1 м. Нам необходимо последовательно отметить все шаги, пока один из них не окажется в дуге, обозначающей канавку, независимо от того, какая будет длина k дуги (ширина канавки). Конечно, очевидно, что если бы человек шагал на расстояние, равное меньше, чем k, то он рано или поздно наступил бы в канаву. Ведь у человека никак не получится переступить расстояние k, если длина его шага меньше, чем k. А значит, нам необходимо найти два следа, расстояние между которыми не будет превышать величину k. Для этого уместно будет воспользоваться принципом Дирихле. Мы мысленно разделим всю окружность на дуги размером меньше k и будем считать их ячейками. Допустим, их окажется n штук. Предположим, что число шагов будет больше чем число дуг (n + m), хотя никакие два шага не будут совпадать из-за иррациональности числа Ö2, тогда по принципу Дирихле, по крайней мере, в одной из ячеек разместится больше одного шага. А поскольку длина дуги составляет меньше k, то и расстояние между шагами будет меньше. Таким образом, мы обнаружили необходимые для доказательства шаги.
Обобщение принципа
Материалы по математике, кроме стандартных (простых и не очень) формулировок, содержат также одну обобщенную, которая используется для выявления более двух объектов, похожих друг на друга. Она утверждает, что если dm + 1 кроликов поместить в d ячеек, то как минимум m + 1 кролик окажется в одной ячейке.
Пример № 6. Обобщение
Прямоугольник с площадью 5 х 6 клеток (30 клеток), закрашенных только 19. Можно ли обнаружить квадрат площадью 2 х 2 клетки, в котором минимум три будут закрашены?
Нашу фигуру необходимо разделить на 6 блоков по 5 клеток. Исходя из утверждения Дирихле, в одной из них будет закрашено не менее 4 клеточек (19/6 = 4). Тогда в одном из квадратов площадью 4 клеточки, расположенном в одном из блоков, будет закрашено минимум 3 клетки.
Пример № 7
Класс, в котором 25 человек. Из любых случайно выбранных 3 учеников двое будут друзьями. Необходимо доказать, что в классе находится школьник, у которого больше 11 приятелей.
Два решения вопроса
Принцип дирихле что это такое как решать
Логический прием, использованный в приведенном доказательстве, называется принципом Дирихле – по имени Петера Густава Дирихле (1805-1895) немецкого математика, автора описанного метода.
Вот общая форма принципа Дирихле:
Если k∙n+1 предмет разложен в k ящиков, то, по крайней мере, в одном из ящиков лежит не меньше, чем n+1 предмет.
По традиции в популярной литературе принцип Дирихле объясняют на примере “зайцев” и “клеток’:
Если N зайцев сидят в n клетках и N>n, то хотя бы в одной клетке сидит более одного зайца.
Этим принципом в неявном виде пользовался, например, Ферма в XVII веке; но широко применяться в доказательствах он стал лишь с прошлого века! Несмотря на свою простоту, это рассуждение оказалось чрезвычайно плодотворным. Вот только один пример. Если делить одно целое число на другое, например 1 на 7, что мы получим? Будем делить в столбик, получая все новые и новые остатки. Но поскольку остатками от деления на 7 могут быть лишь числа 1, 2, 3, 4, 5, 6 и 0, мы либо должны на каком-то шаге получить 0 и остановиться, либо после шестого деления один из остатков обязан повториться. Дальше делить нет смысла — этот остаток мы уже разделили на 7, и все результаты у нас перед глазами. Ясно, что деление будет продолжаться бесконечно, но мы будем получать снова и снова одну и ту же последовательность цифр — период.
Выходит, при делении целого числа на целое мы получим либо конечную десятичную дробь, либо периодическую — и более ничего!
Как видим – все гениальное просто, и к этому же относится и принцип Дирихле.
В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.
Перед нами миллион «кроликов»-елок и, увы, всего лишь 600001 клетка с номерами от 0 до 600000. Каждый «кролик»-елка сажается нами в клетку с номером, равным количеству иголок на этой елке. Так как «кроликов» гораздо больше, чем клеток, то в какой-то клетке сидит по крайней мере два «кролика» – если бы в каждой сидело не более одного, то всего «кроликов»-елок было бы не более 600001 штук. Но ведь, если два «кролика»-елки сидят в одной клетке, то количество иголок у них одинаково.
Дано 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 = 15 – 1. Значит, в оставшихся 13 клетках сидят не менее 27 кроликов, и применение обобщенного принципа Дирихле дает нам желаемый результат.
Докажите, что в любой компании из 5 человек есть двое, имеющие одинаковое число знакомых в этой компании.
Вариантов числа знакомых всего 5: от 0 до 4. Осталось заметить, что если у кого-то 4 знакомых, то ни у кого не может быть 0 знакомых.
Несколько футбольных команд проводят турнир в один круг. Докажите, что в любой момент турнира найдутся две команды, сыгравшие к этому моменту одинаковое число матчей.
Пусть всего команд n. Тогда вариантов числа команд, с которыми сыграла данная команда n: от 0 до n – 1. Осталось заметить, что если одна команда сыграла со всеми n – 1-й, то никакая другая команда не могла ни с кем не сыграть.
10 школьников на олимпиаде решили 35 задач, причем известно, что среди них есть школьники, решившие ровно одну задачу, школьники, решившие ровно две задачи и школьники, решившие ровно три задачи. Докажите, что есть школьник, решивший не менее пяти задач.
Из условий следует, что найдутся 7 школьников, решивших 35 – 6 = 29 задач. Так как 29 = 4 • 7 + 1, то найдется школьник, решивший не менее пяти задач.
Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга?
Ответ: 16 королей. Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля.
Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками.
Каждый из меньших треугольников не может накрывать более одной вершины большого треугольника.
В квадрат со стороной 1 метр бросили 51 точку. Докажите, что какие-то три из них можно накрыть квадратом со стороной 20 см.
Разобьем наш квадрат на 25 квадратов со стороной 20 см. По обобщенному принципу Дирихле, в какой-то из них попадет по крайней мере три точки из 51 брошенной.
Пятеро молодых рабочих получили на всех зарплату – 1500 рублей. Каждый из них хочет купить себе магнитофон ценой 320 рублей. Докажите, что кому-то из них придется подождать с покупкой до следующей зарплаты.
Если бы каждый из рабочих мог купить магнитофон, то у них в сумме было бы не менее 5 • 320 = 1600 рублей.
В бригаде 7 человек и их суммарный возраст – 332 года. Докажите, что из них можно выбрать трех человек, сумма возрастов которых не меньше 142 лет.
Покрасим всю сушу в синий цвет, а все точки, диаметрально противоположные суше – в красный. Тогда обязательно есть точка, которая покрашена в оба цвета. В ней и надо рыть туннель.
Докажите, что среди степеней двойки есть две, разность которых делится на 1987.
Рассмотрите 1988 степеней и их остатки по модулю 1987.
Докажите, что из 52 целых чисел всегда найдутся два, разность квадратов которых делится на 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 > n. Но их разность, которая делится на 1987, равна 11 … 1100 … 00 (m – n единиц и n нулей). Сократим все нули – ведь они не имеют никакого отношения к делимости на 1987 – и получим число из одних единиц, которое делится на 1987.
Докажите, что существует степень тройки, оканчивающаяся на 001.
Если 3m и 3n – степени тройки, дающие один и тот же остаток при делении на 1000, то 3m – 3n = 3n(3m – n – 1) делится на 1000 (мы считаем для определенности, что m > n).
Эти суммы могут принимать лишь 7 разных значений: от – 3 до 3.
Сто человек сидят за круглым столом, причем более половины из них – мужчины. Докажите, что какие-то два мужчины сидят друг напротив друга.
Разобьем всех людей на 50 пар так, что в каждой паре – два человека, сидящих друг напротив друга. Ясно, что в одной из этих пар-«клеток» оба человека – мужчины.
15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.
Если это не так, то, очевидно, что мальчики собрали не менее, чем 0 + 1 + 2 + … + 14 = 105 орехов – противоречие.
Цифры 1, 2, …, 9 разбили на три группы. Докажите, что произведение чисел в одной из групп не меньше 72.
Произведение чисел во всех группах равно 9! = 362880, а 71? = 357911.
Поскольку от любой клетки до любой другой можно добраться, не более 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.