Голуби и покрытия

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

Первый — самый простой: если мы подбросим игральную кость 12 раз, может случиться так, хотя это маловероятно (насколько маловероятно?), что каждое из шести чисел выпадет дважды, поэтому нам придется подбросить ее 13 раз, чтобы быть абсолютно уверенными , что какое-то число выпадет по крайней мере три раза.

Ко второму можно подойти по-разному. Вот как это сделал Луис Ортис:

«Проблема с 12 цифрами наглядно проиллюстрирована с помощью таблицы. Мы располагаем 100 возможных двузначных чисел в ряды по 11 последовательных цифр в каждом, начиная с 00, следующим образом:

00 01 02 03 04 05 06 07 08 09 10

11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32

· · ·

88 89 90 91 92 93 94 95 96 97 98

99

В этой таблице разница между любыми двумя числами в одном столбце кратна 11, или, другими словами, обе цифры равны. Если мы выберем любые 12 чисел в таблице, по крайней мере два из них должны быть в одном столбце, то есть их разность будет иметь обе цифры равными. Действительно: в конечном счете, это голубятня с 11 ящиками и 12 голубями.

В конце предыдущего поста я сказал, что принцип «ящика» позволяет нам эффективно решать некоторые проблемы, объединяя его с теорией графов, и решение, предоставленное Мануэлем Аморосом для третьей из проблем прошлой недели, является хорошим примером этого:

«Проблема дружбы наглядно видна на цветном графе, где точки — это люди, а ребра выражают отношения: синее ребро, если они знают друг друга, и красное в противном случае. Цель состоит в том, чтобы продемонстрировать существование монохромного графа. Из любой вершины P исходят 5 ребер, синих или красных. Обязательно будет 3 одного цвета, скажем, синего. 3 соответствующие вершины, в свою очередь, будут соединены друг с другом , и может быть два случая: либо все 3 ребра указанного треугольника красные (мы получим монохромный треугольник), либо есть одно синее ребро. Это ребро вместе с 2, которые исходят из его концов по направлению к P, образуют синий треугольник».

Покрытия с аналогичными рисунками

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

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

Эти меньшие треугольники не обязательно должны быть равными и могут перекрываться (иначе ответ, очевидно, был бы 4).

Задача допускает интересные вариации и обобщения : дана квадратная площадь, сколько меньших квадратов требуется, как минимум, чтобы покрыть ее? Можно ли обобщить критерий на другие правильные многоугольники? И на неправильные многоугольники? И на круг?

И наконец, еще одна задача (тонко связанная с задачей СФ), в которой сходятся принципы равностороннего треугольника и ящика:

Могут ли любые 5 точек равностороннего треугольника со стороной 1 метр находиться на расстоянии более 50 см друг от друга?