На клетчатой доске 8 × 8 отмечены центры всех клеток Какое наибольшее кол-во отмеченных точек выбрать, чтобы все попарные расстояния были натуральными?

Решение.
В качестве примера подойдут любые 8 клеток в одном ряду.
Пусть какие-то две отмеченные клетки не лежат в одном ряду. Если расстояние между ними по
горизонтали a, а по вертикали — b, то a, b 6 7 входят в некоторую пифагорову тройку (то есть a
2+b 2 = c2 при некотором натуральном c). Заметим, что единственная подходящая тройка — это (3, 4, 5). Теперь рассмотрим шахматную раскраску доски. Очевидно, одноцветные отмеченные клетки попарно лежат в одном ряду, поскольку сдвиг на 3 по одной координате и 4 по другой меняет цвет. Значит всего отмечено не более четырёх чёрных и не более четырёх белых клеток.
Ответ: 8.