Блог пользователя ilyaraz

Простая задача 3
Автор ilyaraz, 13 лет назад, По-русски

Раз уж всплыл мой пост годовой давности, то позволю себе запостить еще одну несложную, но, на мой вкус, очень красивую задачу. Если вы знали ее решение раньше, то не пишите его пожалуйста (можете написать фразу типа "я уже знал решение").

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

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Не очень понял, целая == с целочисленной длиной?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
я уже решал эту задачу)
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Я даже когда-то в AMM читал статью, в которой приводилось 14 различных доказательств этого замечательного факта (если кого-то заинтересует, позже смогу найти ее).
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

Придумал на остановке, когда ехал с работы, так что возможно где-нибудь и просчитался. Я не умею писать математические формулы в комментариях, поэтому приношу извинения за то, что текст возможно будет неудобен для чтения. И еще, так как не умею писать формулы, то напишу только идею, опустив вычисления.

Уложим прямоугольник на координатную плоскость так чтобы один угол лежал в (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, а это возможно только когда одна из сторон целая.

Пользуюсь тем, что при разрезании стороны всех прямоугольников параллельны осям координат. Это, вроде бы, нетрудно доказывается индукцией по количеству прямоугольников в разрезании, но не для прямоугольников, а для произвольных многоугольных областей, у которых все стороны параллельны осям.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Круто! На самом деле это решение можно "дематанализировать", и получится совершенно элементарная магия в три строчки.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А "дематанализируйте", пожалуйста. Я понимаю его суть, но никак строго без матана его оформить не могу.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится
        http://ilyaraz.wordpress.com/2010/05/02/strange-proof/ Это, вроде как, придумал Пьер Делинь.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Это гораздо круче, чем у меня) Идея очень похожа, но при этом все намного прозрачнее.
          → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

Покажем, что если одна из сторон (длина) исходного прямоугольника (назовем его А) нецелая и он разбит оговоренным в условии образом, то другая сторона (высота) должна быть целой.

Заметим, что любой горизонтальный разрез А содержит нецелый отрезок, принадлежащий некоторому прямоугольнику из разбиения (у такого прямоугольника должна быть целая высота по условию).

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

Представим, что мы пробегаемся по всем горизонтальным разрезам А сверху вниз, тогда надо доказать, что как только "заканчивается" один прямоугольник из разбиения с нецелой длиной, так сразу "начинается" другой прямоугольник с нецелой длиной, т.о. цепочка таких прямоугольников покрывает всю высоту А.

Доказать это несложно.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Это просто неверно. Во-первых прямоугольник с горизонтальной целой стороной может упереться в прямоугольник с вертикальной целой стороной. Еще бывает, что один прямоугольник с горизонтальной целой стороной закончился, а другие такие же уже давно начались.
→ Ответить