В одном из предыдущих постов, а именно в
я записал условие математической задачи о странном роботе по имени Тензик. Если Вы не ознакомились с условием, то кратко я приведу его здесь:
1. Есть таблица m на n клеток. В каждой клетке расположена стрелка. Стрелка обязательно обращена на одну из соседних (по горизонтали или вертикали) клеток этой же таблицы.
2. В одну из клеток таблицы помещён робот.
3. На каждом шаге робот перемещается из текущей клетки на одну клетку в направлении стрелки. После перемещения робота стрелка поворачивается по часовой стрелке до тех пор, пока не будет указывать на новую клетку. Робот же готовится к новому шагу.
Вопрос: сколько клеток сможет обойти робот, и от чего это зависит? процесс считается бесконечным, то есть количество шагов не ограничено. Всегда ли можно быть уверенным, что робот обойдёт все клетки таблицы, или нет?
Что ж, условия задачи записаны, и можно перейти к решению.
Под ситуацией внутри таблицы будем понимать определённую ориентацию стрелок в клетках вкупе с определённым положением робота в конкретной клетке таблицы. Начальная ситуация - это то, как выглядит таблица на первом шаге.
Факт 1: количество ситуаций, которые могут быть внутри таблицы, конечно: оно равно количеству всевозможных ориентаций стрелок в клетках таблицы, умноженному на количество возможных положений робота (последнее число равно m*n).
Факт 2: от ситуации на каком-то шаге однозначно зависят все последующие ситуации. Как следствие, из одной и той же начальной ситуации робот будет всегда двигаться по таблице одним и тем же образом.
Из фактов 1 и 2 следует, что рано или поздно начальная ситуация повторится (ведь количество ситуаций конечно), и робот вновь будет двигаться по той же траектории, что и в самом начале пути. Это значит, что робот движется по ЦИКЛУ. Возможно, что цикл самопересекается.
Осталось доказать, что цикл содержит все клетки таблицы. Допустим, что с клеткой A, по которой проходит цикл, граничит (по горизонтали или вертикали) клетка B, которая не принадлежит циклу. Так как клетка A лежит в цикле, то робот проходит по ней бесконечное количество раз. Из чего следует, что робот поворачивает стрелку на клетке A бесконечное количество раз. Стрелка при каждом повороте указывает на новую соседнюю клетку, следовательно, на каком-то шаге она станет указывать на клетку B. При следующем проходе по A робот пройдёт по направлению стрелки и попадёт на клетку B. Значит, B тоже лежит в цикле.
По индукции легко показать, что таким образом все клетки таблицы оказываются принадлежащими циклу. Робот пройдёт по ВСЕЙ таблице! Этот факт не зависит ни от каких начальных условий и от чисел m и n.
Вот такое вот элегантное решение!
