докажите что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками

20.05.202321.05.2023 admin 0 Comments

Лекция 2: Принцип Дирихле

Лекция 2: Принцип Дирихле.

Формулировка: Если в n «клетках» сидят не менее n+1 «кроликов», то в какой-то из «клеток» сидят не менее 2-х «кроликов». (Термины «кролики» и «клетки» являются общепринятыми в математике и будут применяться в том числе и в данной лекции.)
Доказательство: Противоречие к формулировке звучит так: «в каждой клетке сидит не более одного кролика». Но тогда кроликов, очевидно, не больше, чем клеток?! Поэтому есть клетка, где кроликов не менее двух ч. т.д.

Различные усиления, обобщения и т. п.:

1. Если в n клетках сидят не более n-1 кроликов, то есть пустая клетка.
Также доказывается от противного (как и все последующие пункты): если пустой клетки нет, то в каждой клетке сидит хотя бы 1 кролик. Тогда кроликов не меньше, чем клеток?! Значит, пустая клетка есть, ч. т.д.

2. Если в n клетках сидят ровно n кроликов, то либо в каждой клетке сидит ровно один кролик, либо есть и пустая клетка, и клетка, в которой не менее 2-х кроликов.
Действительно, если не в каждой клетке сидит ровно 1 кролик, то либо (а) есть пустая клетка, либо (б) есть клетка, в которой не менее 2-х кроликов. В случае (а) у нас n кроликов оказываются рассаженными в n-1 клеток, поэтому, по принципу Дирихле, есть и клетка, в которой не менее 2-х кроликов ч. т.д. В случае (б) у нас не более n-2 оставшихся кроликов оказываются рассаженными в n-1 клеток, следовательно, по п.1, есть и пустая клетка ч. т.д.

(!) П.2 очень полезен в тех случаях, когда мы знаем, что ровно по одному кролику в каждой клетке сидеть не может.

3. Если в n клетках сидят не менее n*(k-1)+1 кроликов, то в какой-то из клеток сидят не менее k кроликов.
Действительно, если в каждой клетке сидит не более k-1 кролика, то во всех клетках сидит не более n*(k-1) кроликов, а их хотя бы на 1 больше?! ч. т.д.

4. Если в n клетках сидят не более n*(k+1)-1 кроликов, то в какой-то из клеток сидят не более k кроликов.
Действительно, если в каждой клетке сидит не менее k+1 кролика, то во всех клетках сидит не менее n*(k+1) кроликов, а их хотя бы на 1 меньше?! ч. т.д.

5. (Это утверждение обобщает принцип Дирихле на случай нецелого числа кроликов.) Если сумма n чисел равна S, то среди них есть число, не меньшее S/n, и число, не большее S/n.
Действительно, если все числа (строго!) меньше S/n, то их сумма меньше S, а если все числа (строго!) больше S/n, то их сумма больше S. В обоих случаях получаем противоречие ч. т.д.

Задача 2. Дано 233 целых числа. Доказать, что разность каких-то двух из них делится на 232. (Принцип Дирихле часто используется и в задачах по теории чисел !)
Решение: У нас есть 233 числа, которые мы, скорее всего, сделаем кроликами. Найдем подходящие клетки: их должно быть не более 232, и разность 2-х чисел, «сидящих в одной клетке» должна делится на 232. Остатки от деления на 232 как раз подходят. Применяем принцип Дирихле для 233 кроликов-чисел и 232 клеток-остатков и получаем требуемое. (В теоретико-числовых задачах на Дирихле чаще всего клетками бывают остатки от деления чего-либо на какое-то число !)

Задача 3. В магазин привезли 25 ящиков яблок 3-х сортов (в каждом ящике все яблоки одного сорта). Доказать, что среди них есть, по крайней мере, 9 ящиков с яблоками одного сорта.
Решение: Возьмем ящики в качестве кроликов и сорта в качестве клеток. Тогда нам в точности подходит утверждение п.3 при n=3, k=9.

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

Задача 1. На олимпиаде 10 школьников решили в сумме 35 задач, причем среди них были решившие ровно одну, ровно две и ровно три задачи. Доказать, что кто-то из них решил не менее 5 задач.
Решение: (Стандартное соображение: если известно, что какие-то объекты есть, то есть хотя бы по одному экземпляру, который можно выделить и рассмотреть !) Возьмем одного школьника, решившего ровно одну задачу, одного, решившего ровно две и одного, решившего ровно три. Эти трое решили в сумме 6 задач. Остается еще 7 школьников, решивших в сумме 29 задач. Если взять задачи в качестве кроликов и школьников в качестве клеток, то получается в точности утверждение п.3 при n=7, k=5 ч. т.д.

Задача 2. Докажите, что равностронний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками. (Да, принцип Дирихле иногда используется и в геометрии !)
Решение: Главное соображение: меньший равносторонний треугольник, как его не клади, не сможет покрыть 2 вершины большего. Поэтому, взяв вершины в качестве клеток и маленькие треугольники в качестве кроликов, мы получим, что кроликов меньше, чем клеток (утверждение п.1 !), откуда следует, что есть пустая клетка. Это означает, что какую-то из вершин большого треугольника мы никогда не накроем, поэтому и не накроем его целиком ч. т.д.

Переформулировка принципа Дирихле для площадей и покрытий фигур:

0. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) больше S, то у нее имеется точка, покрытая не менее 2-х раз (именно им мы и пользовались, решая последнюю задачу 3).

1. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) меньшеS, то у нее имеется точка, ни покрытая ни разу.

2. Если фигура площади S покрыта несколькими фигурами с суммой площадей ровно S, то либо каждая точка покрыта ровно один раз, либо есть и точка, не покрытая ни разу, и точка, покрытая не менее 2-х раз.

3. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) больше (k-1)*S, то у нее имеется точка, покрытая не менее k раз.

4. Если фигура площади S покрыта несколькими фигурами с суммой площадей (строго!) меньше (k+1)*S, то у нее имеется точка, покрытая не более k раз.

(!) Обратите внимание, что эти утверждения является прямой аналогией утверждений с тем же номером, обобщающих простой принцип Дирихле. Строгих доказательств этих утверждений мы не приводим, тем более что в условиях олимпиады гораздо легче и лучше ссылаться на них, как на очевидные, чем пытаться вспомнить и записать доказательство 😉

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

В простейшем виде его выражают так: «Если десять кроликов сидят в девяти ящиках, то в некотором ящике сидят не меньше двух кроликов».

Общая формулировка: «Если n кроликов сидят в k ящиках, то найдётся ящик, в котором сидят не меньше чем n/k кроликов, и найдётся ящик, в котором сидят не больше чем n/k кроликов». Пусть вас не смущает дробное число кроликов – если получится, что в ящике не меньше 7/3 кроликов, значит, их не меньше трёх.

Доказательство принципа Дирихле простое, но заслуживает внимания, поскольку похожие рассуждения часто встречаются.

Допустим, что в каждом ящике сидят меньше чем n/k кроликов. Тогда во всех ящиках вместе кроликов меньше чем n/k*k = n. Противоречие.

Формулировка принципа Дирихле кажется очевидной, однако трудность состоит в том, что в задачах не указаны ни кролики, не ящики.

Зная принцип Дирихле, можно догадаться, в каких случаях его применять. Например, если каждому элементу множества А соответствует ровно один элемент множества В, то элементы А можно назвать кроликами, а элементы В – ящиками.

Принцип Дирихле бывает непрерывным: «Если n кроликов съели m кг травы, то какой-то кролик съел не меньше m/n кг и какой-то съел не больше m/n кг» (а если кто-то съел больше среднего, то кто-то съел меньше среднего).

Заметим, что в последней формулировке кролики играют роль ящиков для травы, а трава – роль кроликов, сидящих в ящиках.

Пример 1. В школе 400 учеников. Докажите, что хотя бы двое из них родились в один день года.

Решение. Всего в году 365 дней. Назовём дни ящиками, а учеников кроликами. Тогда в некотором ящике сидят не меньше 400/366 кроликов, т. е. больше одного. Следовательно, не меньше двух.

Можно рассуждать от противного. Допустим, что каждый день отмечают день рождения не больше одного ученика, тогда всего учеников не больше 366. Противоречие.

Решение. Допустим, что квадрат составлен. Тогда суммы чисел могут меняться от –6 до +6. Всего 13 значений. Строк в квадрате 6, столбцов 6, диагоналей 2. Получаем 14 различных сумм. Противоречие, значит, составить такой квадрат невозможно.

Пример 3. На планете Земля океан занимает больше половины площади поверхности. Докажите, что в мировом океане можно указать две диаметрально противоположные точки.

Решение. Отразим океан симметрично относительно центра Земли. Поскольку сумма площадей океана и его образа превышает площадь земной поверхности, то существует точка, принадлежащая океану и его образу. Возьмём эту точку вместе с противоположной к ней.

Пример 4. На собеседование пришли 65 школьников. Им предложили 3 контрольных работы. За каждую контрольную ставилась одна из оценок: 2,3,4 или 5. Верно ли, что найдутся два школьника, получившие одинаковые оценки на контрольных?

Решение. Рассмотрим множество наборов из трёх оценок за соответствующие контрольные. Количество таких наборов равно 43 иливозможности за каждую из трёх контрольных). Поскольку число учащихся больше 64, по принципу Дирихле каким-то двум учащимся отвечает один набор оценок.

1. 1. В классе 30 учеников. Во время контрольной работы Петя сделал 13 ошибок, а остальные – меньше. Докажите, что найдутся три ученика, сделавшие одинаковое число ошибок.

2. 2. На земле больше 4 миллиардов человек, которые моложе 100 лет. Докажите, что на Земле есть два человека, родившихся в одну и ту же секунду.

3. 3. На плоскости проведено 12 прямых. Докажите, что какие-то две из них образуют угол не больше 15о.

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

5. 5. На карьере добыли 36 камней. Их веса соответственно 490 кг, 495 кг, 500 кг, …, 665 кг (арифметическая прогрессия). Можно ли увезти эти камни на семи трёхтонных грузовиках?

6. 6. Какое наименьшее число карточек спортлото «6 из 49» надо купить, чтобы наверняка хоть на одной из них был угадан хоть один номер?

7. 7. Докажите, что среди любых пяти человек есть двое с одинаковым числом знакомых среди этих пяти человек. (Возможно, эти двое ни с кем не знакомы).

8. 8. Докажите, что из любых 52 целых чисел всегда можно выбрать два, сумма или разность которых делится на 100.

9. 9. Квадратная таблица (2n + 1) x (2n + 1) заполнена числами от 1 до 2n + 1 так, чтобы в каждой строке и в каждом столбце были представлены все эти числа. Докажите, что если это расположение симметрично относительно главной диагонали, то на главной диагонали тоже представлены все эти числа.

10. 10. В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

11. 11. Комиссия из 60 человек провела 40 заседаний, причём на каждом заседании присутствовало ровно 10 членов комиссии. Докажите, что какие-то два члена комиссии встречались на её заседаниях по крайней мере дважды.

12. 12. На столе лежат 50 правильно идущих часов. Докажите, что в некоторый момент сумма расстояний от центра стола до концов минутных стрелок будет больше, чем сумма расстояний от центра стола до центров часов.

13. Каждая из 9 прямых разбивает квадрат на два четырёхугольника, площади которых относятся как 2:3. Докажите, что по крайней мере три из этих прямых проходят через одну точку.

Источник

Докажите что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками

Логический прием, использованный в приведенном доказательстве, называется принципом Дирихле – по имени Петера Густава Дирихле (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 сумм: x₁, x₁ + x₂, …, x₁ + x₂ + … + x₁₀ и их остатки при делении на 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.

Источник

Докажите что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками

Олимпиадные задачи по математике по теме «Принцип Дирихле». Решения.