Винтик и Шпунтик проектировали нановездеход. Винтик начертил прямоугольник и наметил в нем двадцать отверстий для колес. Шпунтик разделил прямоугольник на отсеки, начертив две…
Винтик и Шпунтик проектировали нановездеход. Винтик начертил прямоугольник и наметил в нем двадцать отверстий для колес. Шпунтик разделил прямоугольник на отсеки, начертив две линии, параллельные одной стороне прямоугольника, и еще две, параллельные другой. При этом ни одно отверстие Винтика не попало на линии Шпунтика. Докажите, что обязательно найдется отсек с тремя или более отверстиями.
Для решения этой задачи давайте рассмотрим прямоугольник, в который Винтик поместил 20 отверстий для колес, и как Шпунтик разделил этот прямоугольник на отсеки.
Обозначим линии, проведенные Шпунтиком, которые разделяют прямоугольник. Пусть две линии, проведенные параллельно одной стороне прямоугольника, обозначим как вертикальные (например, линии x1 и x2), а две линии, параллельные другой стороне, обозначим как горизонтальные (например, линии y1 и y2). Это разделяет прямоугольник на 9 отсеков (или областей).
Согласно условию, ни одно из отверстий Винтика не попало на линии Шпунтика. На всякие 2 вертикальные линии и 2 горизонтальные линии создаётся 9 отсеков. Теперь мы можем воспользоваться принципом Дирихле, который утверждает, что если N объектов помещаются в K контейнеров, и если N > K, то по крайней мере один контейнер должен содержать более одного объекта.
В нашем случае, у нас есть 20 отверстий (N = 20) и 9 отсеков (K = 9). Подставив данные в неравенство:
20 отверстий > 9 отсеков.
Это значит, что по принципу Дирихле хотя бы один сектор должен содержать больше, чем N/K = 20/9 ≈ 2,22 отверстия. Поскольку мы имеем целые числа, это означает, что по крайней мере один отсек должен содержать минимум 3 отверстия.
Таким образом, мы доказали, что обязательно найдется отсек с тремя или более отверстиями.
