Если бы мне нужно было научить кого-то только одному математическому принципу или инструменту, я бы выбрал то, что считаю одним из самых впечатляющих интеллектуальных инструментов математики, настолько простым, что любой может его понять, — это принцип Дирихле.
В этой статье мы используем этот простой принцип, чтобы показать впечатляющие результаты. В частности, мы докажем, что следующие утверждения верны:
В Москве должны быть по крайней мере два человека с одинаковым количеством волос на голове. Не существует алгоритма, который без потерь сжимает любые данные. Как бы вы ни расположили 5 точек на сфере, всегда можно найти (закрытую) полусферу, содержащую как минимум 4 из этих точек. На любой вечеринке всегда найдутся как минимум два гостя, которые пожмут руки одинаковому количеству людей. Эти утверждения кажутся трудными для доказательства (некоторые даже недостижимыми). Но их можно доказать несколькими строчками простых логических аргументов без единого уравнения.
Давайте начнем.
Принцип Дирихле
По какой-то причине этот удивительный логический инструмент не преподается на начальных уровнях математики, хотя он совершенно доступен даже для людей с минимальным математическим опытом. На самом деле, сам принцип до смешного прост.
Он гласит:
«Если n объектов распределены по m контейнерам, причем n > m, то по крайней мере в одном контейнере будет более одного объекта.»
Действительно!? И это все? Слышу ваш вопрос, и да, это все! Но, как вы скоро увидите, мы можем использовать этот принцип и его вариации для доказательства удивительных и порой совершенно неинтуитивных вещей.
Он получил свое название от того, как мы его представляем. Мы представляем стаю голубей, которые должны поместиться в голубятни, но голубей больше, чем голубятен. Тогда хотя бы в одной голубятне должно быть более одного голубя.
Мы можем быть более точными. Более аккуратная версия принципа звучит так:
«Если n объектов распределены по m контейнерам, причем n > m, то по крайней мере в одном контейнере будет как минимум ⌈n/m⌉ объектов.»
Здесь круглые скобки вокруг n/m обозначают функцию потолка, которая округляет до ближайшего целого числа. Например, если у нас есть 22 голубя и 3 голубятни, то по крайней мере в одной голубятне будет ⌈22/3⌉ = 8 голубей. Мы будем называть это количественной версией принципа Дирихле.
Лохматые близнецы
Мы начнем использовать наши новые суперспособности, доказав, что в Москве есть как минимум 2 человека с одинаковым количеством волос на голове.
Это утверждение сначала кажется недостижимым. Мы не можем посетить всех в Москве и попросить их стоять совершенно неподвижно часами. Это не только грубо, но и займет примерно 1000 лет, чтобы один человек посчитал все волосы. Но мы можем доказать это простым логическим аргументом, используя принцип Дирихле.
Мы исключим лысых людей, так как в Москве наверняка есть два лысых человека, и проблема будет слишком простой.
Обратите внимание, что среднее количество волос на человеческой голове примерно 150 000, и поэтому не так уж неправдоподобно предположить, что никто не имеет более 1 миллиона волос на голове. Но население Москвы превышает 1 миллион человек, поэтому по принципу Дирихле должно быть как минимум два человека с точно таким же количеством волос.
Используя количественную версию принципа, мы можем сказать, что как минимум 13 человек имеют одинаковое количество волос на голове. Здесь количество волос играет роль голубятен, а люди в Москве играют роль голубей.
Конечно, этот аргумент обобщается на многие другие группы людей, а не только на население Москвы!
Также обратите внимание, что принцип не дает нам абсолютно никакого ключа к тому, как найти этих «лохматых близнецов», и мы также не можем сказать, есть ли у Петра Иванова лохматый близнец. Он только утверждает, что такие люди существуют.
Пять точек на сфере
Какие бы 5 точек на сфере вы ни выбрали, как бы умно вы их ни расположили, я могу найти закрытую полусферу, содержащую 4 из них. Под закрытой полусферой мы подразумеваем, что если точка находится на границе, то мы также считаем эту точку «содержащейся».
Обратите внимание, что принцип Дирихле уже дает нам, что 5 точек на сфере должны выбрать между двумя непересекающимися половинами, и поэтому 3 из них всегда должны находиться в одной из полусфер. То есть, если полусферы выбираются первыми, то принцип Дирихле гарантирует, что 3 точки всегда будут находиться в одной из них.
Но если точки размещены первыми, мы можем быть умными при выборе полусфер. В частности, возьмите две точки и проведите большой круг, пересекающий их. Тогда три оставшиеся точки должны подчиняться принципу Дирихле, и мы получаем две дополнительные точки в одной из полусфер.
Это означает, что если вы возьмете 5 мест, в которых вы побывали на Земле (например, в отпуске), то можно быть уверенным, что 4 из этих мест находятся в одной полусфере! Удивительная мощь этого результата заключается в том, что тот же принцип применим на Луне… Или на Марсе… Захватывающие вещи.
Вышеприведенная «умность» является частью более общей тактики при попытке применить принцип, как мы увидим чуть позже.
Любая дробь из целых чисел будет иметь повторяющуюся хвостовую часть цифр
Думаю, большинство из нас знает это, но это не означает, что мы это понимаем. Почему дроби целых чисел или рациональных чисел, как мы их называем, имеют повторяющиеся хвосты цифр?
Один простой аргумент заключается в следующем: при длинном делении деления типа n/m мы получаем новый остаток на каждом шаге где-то между 0 и m-1, и этот остаток приведет к следующей цифре соответствующего десятичного числа. Но после m итераций нашего алгоритма длинного деления у нас должен быть остаток дважды, так как итераций больше, чем возможных остатков, и принцип Дирихле применяется.
Как только это происходит, детерминированная природа алгоритма будет производить точно такие же цифры, как и раньше, и так далее до бесконечности. Упражнение для читателя: почему обратное тоже верно, что если у вас есть десятичное число с повторяющимся хвостом цифр, то это должно быть рациональное число?
Плитка шахматных досок с домино
Представьте шахматную доску с удаленными двумя противоположными углами, скажем, черными квадратами a1 и h8. Теперь осталось всего 62 доступных квадрата. Вопрос в том, можно ли замостить доску домино размером 1×2 квадрата?
Сначала это также кажется трудной задачей. Обратите внимание, что поскольку осталось 32 белых квадрата и домино всегда покрывает как черный, так и белый квадрат, нам действительно нужно 16 домино, чтобы покрыть доску. Теперь, поскольку 32 домино покрывают 64 квадрата, а на нашей доске осталось всего 62 квадрата, мы знаем по принципу Дирихле, что по крайней мере один квадрат был покрыт более одного раза!
Таким образом, мы не можем замостить такую доску.
Не существует идеального алгоритма сжатия
Это весело. Вам не нужно знать теорию компьютерных наук или что-то подобное, чтобы следить за этим абзацем, но для полноты я объясню, что это значит.
Алгоритм сжатия — это компьютерная программа, которая берет некоторые данные, такие как документ или другой файл, и производит данные на выходе, которые занимают меньше места на компьютере. Вы, вероятно, знаете это по файлам zip или подобным.
Существуют два вида алгоритмов сжатия: сжатие без потерь и сжатие с потерями. Алгоритмы сжатия без потерь всегда могут воспроизвести оригинальный файл, который был сжат, точно так же, как он был, в то время как алгоритмы с потерями могут воспроизвести только подобную версию оригинального файла. В математике мы бы сказали, что алгоритмы сжатия без потерь являются биекциями между категориями данных.
Вопрос, на который мы хотели бы ответить, заключается в том, существует ли алгоритм сжатия, способный сжать любые данные. Ответ — нет, и аргумент действительно прост. Если бы такой алгоритм существовал, то он бы брал строки битов и производил более короткие строки битов, но поскольку существует больше длинных строк битов, чем коротких строк битов, по принципу Дирихле возникли бы коллизии, например, некоторые строки были бы сжаты в одну и ту же строку битов, но это не может случиться, так как алгоритм предполагался без потерь (биекция).
Это также означает, что алгоритмы сжатия без потерь на самом деле расширяют некоторые данные и сжимают другие данные.
На самом деле файлы не являются битами, но шаг к использованию этого аргумента несложен.
Алгоритмические орбиты на кубике Рубика
Во-первых, алгоритм на кубике Рубика — это количество ходов подряд. Это все. Важное для нас заключается в том, что они всегда обратимы. То есть из определенного состояния (конфигурации кубика) вы всегда можете инвертировать алгоритм, чтобы вернуться к предыдущему состоянию.
Оказывается, если вы начинаете с решенного кубика, все стороны которого отсортированы по цветам, и применяете один и тот же алгоритм снова и снова, вы в конце концов вернетесь к решенному состоянию.
Аргумент прост. Сначала заметим по принципу Дирихле, что существует больше потенциальных применений алгоритма к кубику, чем конфигураций кубика (хотя конфигураций кубика очень много), потому что вы можете продолжать применять алгоритм. И поскольку конфигурация меняется каждый раз, когда вы используете алгоритм, в конце концов вы попадете в конфигурацию, в которой кубик уже был.
Последнее, что нам нужно доказать, это то, что эта конфигурация должна быть той, с которой вы начали эксперимент. Видите ли, если мы попадем в конфигурацию где-то между начальной конфигурацией и тем местом, где вы находитесь, то эта конфигурация была бы достижима нашим алгоритмом из двух разных состояний. Поскольку наш алгоритм обратим, это невозможно.
На самом деле каждый алгоритм делит все конфигурации кубика на отдельные циклы, и те из вас, кто знаком с теорией групп, должны думать о смежных классах!
Кстати, существует 43252003274489856000 конфигураций кубика Рубика. Это:
«Сорок три квинтиллиона, двести пятьдесят два квадриллиона, три триллиона, двести семьдесят четыре миллиарда, четыреста восемьдесят девять миллионов, восемьсот пятьдесят шесть тысяч» конфигураций!
Рукопожатие
На любой вечеринке, где происходят рукопожатия (понимаю, что это может быть редким явлением после COVID-19, но вспомним добрые старые времена), всегда найдутся как минимум два гостя, которые пожмут руки одинаковому количеству людей.
Это немного сложнее доказать, потому что нам нужно быть умными в этот раз.
Скажем, есть N+1 гостей. Во-первых, заметим, что хотя один человек может пожать от 0 до N рук (мы исключаем одиночное рукопожатие), если кто-то не пожимает руки никому, мы можем быть уверены, что никто не пожимает руки всем остальным и наоборот.
Это означает, что возможное количество рукопожатий, которое может совершить один человек, либо в множестве {0, 1, 2, …, N-1}, либо {1, 2, …, N}, но в любом случае существует N возможных рукопожатий и N+1 гость, так что по принципу Дирихле по крайней мере два гостя пожмут руки одинаковому количеству людей.
Веселье с суммами
Если взять 10 случайно выбранных двузначных чисел, всегда найдутся два непустых непересекающихся множества, которые в сумме дадут одинаковое число.
Аргумент следующий: наименьшая сумма, которую мы можем получить, составляет 10, если мы выберем наименьшее двузначное число как наше множество. Наибольшая возможная сумма, с другой стороны, должна быть суммой 9 наибольших двузначных чисел, то есть 91 + 92 + 93 + 94 + 95 + 96 + 97 + 98 + 99 = 855. Таким образом, существует 846 различных возможных сумм.
Сколько существует множеств? Ну, для 10 случайно выбранных двузначных чисел число может быть либо в множестве (или подмножестве), либо не в множестве. Таким образом, должно быть 2¹⁰ = 1024 (размер булеана) возможных множеств из выбранных 10 чисел. Но это включает пустое множество и полное множество, и мы не хотим их, так что остается 1022 возможных множества.
Мы почти закончили, потому что теперь у нас есть 1022 множества и 846 сумм, что означает, что по принципу Дирихле по крайней мере два множества будут иметь одинаковую сумму. Однако мы хотели, чтобы множества были непересекающимися, то есть неперекрывающимися. Но это не так сложно решить. Если два множества имеют общий элемент, мы можем просто удалить этот элемент из обоих множеств, и они все равно будут суммироваться до одного и того же числа. Это в основном вычитание одного и того же числа с обеих сторон знака равенства. Продолжайте повторять это, пока два множества не будут непересекающимися.
Для более продвинутой версии вы можете доказать следующее, что я оставлю в качестве задачи для заинтересованного читателя.
Если у вас есть 101 натуральное число (положительное целое число), равномерно распределенное по кругу, сумма которого равна 300, всегда будет дуга на круге, содержащая последовательные числа, сумма которых равна 200. (Обратите внимание, что числа последовательные, а не последовательные).
Заключительные замечания
Надеюсь, я показал мощь принципа Дирихле, демонстрируя эти замечательные задачи и красивые решения. Если у вас есть вызовы или другие известные задачи, решаемые с использованием этого принципа, пожалуйста, оставьте их в комментариях.
Как всегда, спасибо за чтение.