Процессы и алгоритмы

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

Случай 1. Предположим, что переполз на соседнюю клетку, то есть на вторую. Тогда на первую мог переползти только иначе бы мы и также отрезали. Если переполз на третью клетку, то они с образуют искомую пару. Если переполз на четвертую клетку, то они с образуют искомую пару, значит, этот случай рассмотрен.

Случай 2. Предположим, что переполз на клетку через одну, то есть на третью. Тогда, чтобы и не образовали искомую пару, червячку необходимо переползти в четвертую клетку. Но первую и вторую клетки тоже кто-то должен занять, и этом могут сделать только червячки и Получили картинку Тогда эту четверку также можно отрезать и продолжить рассуждения. Так как мы всегда отрезаем полоску из 2 или 4 клеток, то есть полоску четной длины, то рано или поздно произойдет первый случай, и в нем обязательно найдутся два нужных червячка.