воскресенье, 3 марта 2013 г.

Плитка

Плиточный пол
Пол прямоугольной формы выложен квадратной плиткой. Сторона плитки равна 1. Размеры пола при этом 231x93. Если провести диагональ из одного угла комнаты в другой, то внутри скольких плиток будет проходить эта линия (то есть пересекать их)?
Заодно, сколько распилов потребуется?


update
Первым был sayressmith.
Ответ
321.
Когда диагональ входит в новую плитку, то каждый раз пересекает горизонтальную или вертикальную линию. Но когда диагональ пересекает угол плитки, она пересекает две линии, хотя входит только в одну плитку. Такие углы являются углами прямоугольников, диагонали которых находятся на главной диагонали. Число таких прямоугольников равняется наибольшему общему делителю 231 и 93, то есть 3. Учитывая выше сказанное, число пересеченных плиток можно найти так: 231+93-3=321.

7 комментариев:

  1. Этот комментарий был удален автором.

    ОтветитьУдалить
  2. Тоже 321 получилось.
    Проще всего (на мой взгляд) посчитать не количество именно плиток, а количество сегментов диагонали. А она делится границами плиток, которые образуются линиями сетки 231х93.
    Итого: диагональ пересекает 92 "горизонтальные" линии, 230 "вертикальных". При этом, поскольку НОД=3, то еще среди них два "перекрестка", которые надо вычесть. Получается 320 точек деления диагонали. Внутренних точек. Соответственно, сегментов 321, что совпадает и с числом "порезанных" плиток.

    ОтветитьУдалить
  3. Решение Dendr гораздо интереснее)
    Я просто в экселе посчитал количество плиток, с которыми нет пересечения.

    ОтветитьУдалить
  4. 321 - правильный ответ. Действительно, число перекрёстков определяется с помощью наибольшего общего делителя.

    ОтветитьУдалить