Гуляй, Очкарик
Виталик учится на математическом факультете, а в свободное от занятий время подрабатывает в небольшой гостинице «Шахматная партия».
В отеле всего 16 номеров, и Виталик следит за перемещением подчинённых ему уборщиц, двигая по клеткам шахматной доски «пучеглазую» фигуру короля (показана на рисунке), которую он любовно называет Очкариком.
В один прекрасный день ему в голову приходит идея подсчитать, сколько существует способов, при помощи которых фигура короля "Очкарик" сможет добраться от верхней левой клетки (А) доски до нижней правой (Б), если будет перемещаться исключительно в показанных стрелками направлениях.
Ответ:
Виталик понимает, что решить эту головоломку будет гораздо проще, если разбить её на несколько более локальных задач, то есть задуматься о том, сколькими способами можно добраться до каждой из клеток поля.
В силу того, что до клеток верхнего ряда и левого столбца можно добраться только одним способом, он пишет в этих семи клетках по единице.
Во всех остальных пустых ячейках он ставит числа, равные количеству всех клеток, находящихся выше и слева, а также строго влево от них.
К примеру, к моменту достижения последней клетки второго ряда ему придется сложить 1 (выше) + 1 (выше слева) + 5 (строго слева), в результате чего получится 5 + 1 + 1 = 7.
В результате последовательного продвижения по клеткам оставшихся строк он приходит к числу 63, которое и показано на рисунке в нижнем правом углу поля.
