Раз уж всплыл мой пост годовой давности, то позволю себе запостить еще одну несложную, но, на мой вкус, очень красивую задачу. Если вы знали ее решение раньше, то не пишите его пожалуйста (можете написать фразу типа "я уже знал решение").
Задача: прямоугольник разбит на несколько прямоугольников так, что у каждой части есть по крайней мере одна сторона с целой длиной. Доказать, что и у исходного прямоугольника хотя бы одна целая сторона.
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 19:41:47 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Уложим прямоугольник на координатную плоскость так чтобы один угол лежал в (0, 0), а стороны располагались вдоль осей. Рассмотрим функцию f(x,y) = sin(x*2*pi) * sin(y*2*pi). Так как sin(x*2*pi) - функция периодическая с периодом 1 (UPD. и интеграл sin(x*2*pi) от 0 до 1 равен 0), то интеграл по любому прямоугольнику, у которого одна из сторон целая и стороны параллельны осям координат, равен 0. Тогда интеграл по всему прямоугольнику равен также 0, а это возможно только когда одна из сторон целая.
Пользуюсь тем, что при разрезании стороны всех прямоугольников параллельны осям координат. Это, вроде бы, нетрудно доказывается индукцией по количеству прямоугольников в разрезании, но не для прямоугольников, а для произвольных многоугольных областей, у которых все стороны параллельны осям.
Покажем, что если одна из сторон (длина) исходного прямоугольника (назовем его А) нецелая и он разбит оговоренным в условии образом, то другая сторона (высота) должна быть целой.
Заметим, что любой горизонтальный разрез А содержит нецелый отрезок, принадлежащий некоторому прямоугольнику из разбиения (у такого прямоугольника должна быть целая высота по условию).
Далее надо доказать, что существует подмножество прямоугольников из разбиения у которых нецелые длины и целые высоты при этом высоты этих прямоугольников являются разбиением высоты исходного прямоугольника А, а следовательно высота А - целая величина.
Представим, что мы пробегаемся по всем горизонтальным разрезам А сверху вниз, тогда надо доказать, что как только "заканчивается" один прямоугольник из разбиения с нецелой длиной, так сразу "начинается" другой прямоугольник с нецелой длиной, т.о. цепочка таких прямоугольников покрывает всю высоту А.
Доказать это несложно.