Формула количества диагоналей в квадратной матрице
Есть такая очевидная формула, что кол-во диагоналей в квадратной матрице равна 2n-1, где n - размерность матрицы. Я до нее сам додумался, но мне очень интересно как ее можно доказать. Я посмотрел кучу книг по матеше и программированию, но нигде не нашел строгого математического доказательства. Я понимаю, что занимаюсь шизой, но вдруг кто-то шарит.
Ответы (2 шт):
Количество элементов в квадратной матрице на основной диагонали равно длине её стороны, так-же имеются смежные сонаправленные диагонали по удалению от основной они становятся меньше на 1, т.к. каждая следующая диагональ является основной для матрицы меньшой размерности(данный факт можно доказать через индукцию), минимальное кол-во элементов в диагонали 1, получается что по одну сторону от основной диагонали n-1, и с другой стороны n-1. Получается, что кол-во сонаправленных диагоналей n-1+n-1+1 = 2n-1 Если считать не только сонаправленные, а все диагонали, то их будет в 2 раза больше.
Диагональ это прямая с уравнением x - y = d. Все числа в уравнении целые. 1 ≤ x, y ≤ n, где n - размер матрицы. Какие бывают d для диагоналей проходящих через клетки доски? Надо подставить все возможные пары x и y. Максимальное значение dmax = n - 1, минимальное dmin = 1 - n.
Будем перебирать пары (x, y) в таком порядке: (1, n), (2, n), ..., (n-1, n), (n, n), (n, n-1), ..., (n, 2), (n, 1). Эти клетки идут по краю матрицы из одного угла в противоположный. Через каждую клетку проходит новая диагональ, они не повторяются, потому что у них не повторяются, растут параметры d. Диапазон d имеет размер dmax - dmin + 1 = n - 1 - (1 - n) + 1 = 2n - 1. Формула доказана.
Другую группу диагоналей задаёт уравнение x + y = s. Оставлю в качестве упражнения вывод формулы для числа s-диагоналей.