Ответ:
Поскольку у Агнес только пять плиток, дорожка никогда не может сдвигаться в южном или западном направлении: любой такой шаг назад затрачивал бы расстояние на сетке, которое невозможно вновь покрыть всего лишь пятью плитками. Таким образом, конечная точка растущей дорожки всегда продвигается в северном и/или восточном направлении. Мы считаем дорожки, заполняя таблицу : В каждом квадрате решетки мы пишем количество дорожек тримино, текущая конечная точка которых (свободный конечный квадрат последней плитки) лежит в этом квадрате.
После размещения первой плитки, идущей из левого нижнего угла, конечная точка должна быть на расстоянии ровно двух квадратов: либо двух вправо (горизонтальная первая плитка), либо двух вверх (вертикальная первая плитка). Следовательно, мы ставим в квадратах и (координаты считаются снизу слева).
Теперь заполним остаток таблицы, двигаясь из левой нижней части к правой верхней. Чтобы определить значение в квадрате , рассмотрим способы, которыми тримино может там заканчиваться. Плитка, заканчивающаяся на , может быть вертикальной или горизонтальной, и в любом случае она должна касаться предыдущей тримино одним из конечных квадратов. Это дает четыре возможных предшествующих конечных точки: и в случае вертикального расположения и и в случае горизонтального расположения. Каждый из этих вариантов соответствует корректному способу продлить существующую дорожку на одну плитку. Таким образом, записанное в значение является суммой значений, уже записанных в квадратах
|
с любым квадратом вне решетки, дающим .
После заполнения таким образом всех квадратов значение 75 в правом верхнем угловом квадрате является как раз числом допустимых дорожек тримино из левого нижнего угла в правый верхний.
Альтернативное решение: Расположим пять I-тримино непрерывной цепью начиная с левого нижнего угла следующим “скелетным” образом: последовательные плитки соприкасаются только углами (на концевых квадратах). Каждая плитка приближается к конечной точке либо на ( “вертикальный” тримино) или (“горизонтальный” тримино). После 5 тримина конечная точка в , где . Если это число вертикальных тримино и число горизонтальных тримино, тогда и .
Чтобы превратить цепь тримино касающихся углами в правильный путь, где последовательные тримино соприкасаются гранью, мы "исправляем"каждое из 4 соединений между последовательными тримино. Пусть -ое соединение будет между тримино и ; для каждого соединения мы выбираем одну из двух операций: либо сдвигаем весь хвост из тримино на одну клетку влево, или сдвигаем этот хвост на одну клетку вниз. Это гарантирует, что тримино и будут иметь общую грань вместо угла.
Пусть это общее число соединений которые мы решили сдвинуть влево, а это общее число соединений которые мы решили сдвинуть вниз. Так как существует ровно 4 соединения, мы имеем . После выполнения всех 4 сдвигов конечная точка скелетной цепочки сдвинется в . Чтобы достичь необходимого нам пути от точки до верхнего угла , эта финальная точка должна удовлетворять условию .
Теперь проверим шесть случаев:
- : не может достичь 4 сдвигами влево/вниз .
- : тоже не может достичь.
- : необходимо, чтобы , (все 4 сдвига вниз). Существует скелетных цепочек и только один вариант сдвигов, что дает возможных путей.
- : необходимо, чтобы , . Возможны скелетных цепочек и вариантов выбора какие соединения сдвинуть влево (остальные сдвинуть вниз), что дает нам возможных путей.
- : необходимо, чтобы , (все сдвиги вниз). There are скелетных цепочек и 1 вариант сдвина, что дает возможных путей.
- : невозможно достичь.
Таким образом, общее число допустимых дорожек .