Подсчеты в клетчатых задачах

Переберём все квадраты по длины стороны :

Зафиксируем все квадраты со стороной положением их левого нижнего угла.

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

Таким образом, квадрат со стороной один, квадратов со стороной имеется четыре, квадратов со стороной будет девять, и так далее, вплоть до квадратов со стороной , которых будет .

Итак, всего квадратов:

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

Получаем ответ