Сколько клеток пересекает диагональ в клетчатом прямоугольнике размером 239х566? (Только...

Question

Дан 1 ответ

Guerrino_zn · Answer 1 · 2024-08-27T16:06:05+0000

Рассмотрим вертикальные линии и горизонтальные. Каждую из них диагональ пересекает ровно один раз. При этом каждое пересечение вертикальной или горизонтальной линии соответствует пересечению двух (соседних) клеток. Посчитаем сумму вертикальных ( $v$ ) и горизонтальных клеток ( $h$ ): каждая клетка, которую пересекают (кроме двух крайних), считается дважды (она дважды участвует в паре), но также каждое пересечение считается дважды. Поэтому $\frac{2(v+h)+2}{2}=v+h+1$ есть количество пересеченных клеток (мы добавили двойку в числителе вот почему: 2(v+h) - это удвоенное количество средних клеток (т.е. не крайних), а крайние посчитаны только один раз. Добавляя 2, мы считаем и крайние два раза. Теперь все клетки посчитаны дважды — можем делить на 2)

Пусть дан прямоугольник $a\times b$ , причем числа $a,b$ не имеют общих делителей (иначе какая-то клетка пересекалась бы по вершине — мы ее не считали). Тогда $v=a-1$ , $h=b-1$ . Получаем $a-1+b-1+1=a+b-1$ пересеченная клетка. Поскольку числа 239 и 566 не имеют общих делителей, к ним применима эта формула. Получаем, что диагональ пересекает 239+566-1=804 клетки