Олимпиадные задачи из источника «2009-2010» для 11 класса - сложность 3 с решениями

<img align="right" src="/storage/problem-media/115364/problem_115364_img_2.gif"> Назовём лестницей высоты <i>n</i> фигуру, состоящую из всех клеток квадрата <i>n</i>×<i>n</i>, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты <i>n</i> на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?

В клетки квадрата 100×100 расставили числа 1, 2, ..., 10000, каждое – по одному разу; при этом числа, различающиеся на 1, записаны в соседних по стороне клетках. После этого посчитали расстояния между центрами каждых двух клеток, числа в которых различаются ровно на 5000. Пусть <i>S</i> – минимальное из этих расстояний. Какое наибольшее значение может принимать <i>S</i>?

Назовём тройку натуральных чисел  (<i>a, b, c</i>)  <i>квадратной</i>, если они образуют арифметическую прогрессию (именно в таком порядке), число <i>b</i> взаимно просто с каждым из чисел <i>a</i> и <i>c</i>, а число <i>abc</i> является точным квадратом. Докажите, что для любой квадратной тройки найдётся другая квадратная тройка, имеющая с ней хотя бы одно общее число. (Тройка  (<i>c, b, a</i>)  новой тройкой не считается.)