Задачи заочного тура региональной олимпиады по информатике 2001

Когда известный американский мастер головоломок Сэм Лойд был маленьким, ему подарили 9 огромных томов «Истории Англии» Хьюма. Он не прочитал эти книги, но обнаружил, что если расположить тома на двух полках, как показано на рисунке, то получится дробь 6728/13458, в точности равная 1/2.

Как смог бы Сэм Лойд получить дробь, равную 1/2, если бы ему подарили энциклопедию из 12 томов? Сколько существует вариантов расположения всех 12 томов, дающих дробь, равную 1/2?

Сэм Лойд составил много шахматных задач, и, возможно, что он придумал бы и эту задачу, если бы в его время существовали компьютеры:

"Сколько существует различных путей для путешествия ладьи из левого верхнего угла доски размером 5x6 в правый нижний угол, при котором ладья не проходит дважды по одной и той же клетке?"

Будем считать, что ладья при движении на несколько клеток по горизонтали или вертикали проходит каждую клетку этого отрезка. На рисунке показаны два возможных пути.