Лабиринтом называется клетчатый квадрат  
  10*10, некоторые пары соседних узлов в  
  котором соединены отрезком - "стеной" таким образом, что  
  переходя из клетки в соседнюю по стороне клетку и не проходя через  
  стены, можно посетить все  
  клетки квадрата. Границу квадрата будем также считать обнесенной  
  стеной.  
 В некоторой клетке некоторого лабиринта стоит робот.  
 Он понимает 4 команды - Л, П, В, Н, по которым соответственно  
 идет влево, вправо, вверх и вниз, а если перед ним "стена", то стоит  
 на месте. Как написать программу для робота, выполняя которую он  
 обойдет все клетки независимо от лабиринта и от своего начального  
 положения?  
   
 


			
Рассмотрим все начальные состояния.  
 Каждое состояние определяется лабиринтом и начальным  
 положением робота в этом лабиринте. Тем самым, состояний всего  
 конечное число. Занумеруем состояния числами 1,2,...,N.  
 Нетрудно написать программу П1 обхода лабиринта исходя  
 из начального состояния с номером 1.  
 Далее, посмотрим, как двигался робот под действием программы  
 П1 исходя из начального состояния номер 2. Припишем к  
 программе П1 в конце несколько команд так, чтобы робот  
 закончил обход лабиринта из начального состояния номер 2.  
 Получим программу П2, выполняя которую, робот обходит  
 лабиринт как из начального состояния номер 1, так и из начального  
 состояния номер 2. Далее действуем таким же образом - приписываем  
 к уже написанной программе Пk (выполняя которую робот  
 обходит лабиринт из первых k начальных состояний), несколько  
 команд так, чтобы робот обходил лабиринт и из (k+1)-го начального  
 состояния. Полученная в конце программа ПN, как  
 нетрудно видеть, будет искомой.
			
Теория алгоритмов (прочее) Индукция (прочее)