Индукция в комбинаторике

Докажем по индукции для досок вида со стрелочками, что фишка упадет за пределы доски за конечное число перемещений. Тогда и для доски фишка упадет за пределы доски за конечное число шагов.

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

Переход: рассмотрим внешние клеточки доски (по периметру). Опять-таки на каждую из внешних клеток доски можно попасть не более раз, после чего стрелка на этой клетке повернется вне доски, а тогда после попадания фишки на нее, фишка выпадет. При этом по предположению индукции, если фишка попадает во внутренний квадрат то за не более чем конечное число шагов она окажется, вне его пределов. Тогда за не более чем конечное число шагов — фишка будет поворачивать хотя бы из стрелок во внешних клетках. Но так как клеток внешних конечное число, а также мы попадаем на краевые клетки за конечное число переходов, то за конечное число шагов все внешние стрелки будут направлены вне доски, тогда при попадании на них фишка вылетает за пределы (фишка снова попадет на внешние клетки, так во внутреннем квадрате она находится лишь конечное число ходов).