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

Для решения этой задачи давайте рассмотрим прямоугольник, в который Винтик поместил 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 отверстия. Таким образом, мы доказали, что обязательно найдется отсек с тремя или более отверстиями.