ПВГ 2022, 10–11 классы, задача 9 (творческая III)
Коридор имеет ширину и длину . Имеется паркетная плитка двух размеров: и . Найдите количество способов уложить паркет на пол в этом коридоре. В ответе укажите две последние цифры найденного числа (например, если получено число , то в ответе следует указать ).
Ответ
Ответ: .
Решение. Пусть — количество вариантов укладки для коридора размера , а — количество вариантов укладки полосы размера , у которой вырезана одна угловая клетка. Тогда:
Соотношение получено с учётом того (см. рис. ), что варианты укладки, изображённые столбиком под номером , содержатся в вариантах укладки, изображённых столбиком , а варианты укладки, изображённые столбиком под номером , содержатся в вариантах укладки, изображённых столбиком .
Соотношение получено с учётом того (см. рис. ), что варианты укладки, изображённые столбиком под номером , содержатся в вариантах укладки, изображённых столбиком .
Из уравнения следует, что
Если к уравнению прибавить удвоенное уравнение и вычесть удвоенное уравнение , то получим, что
Будем искать решение уравнения в виде (где и — константы). Тогда рекуррентное соотношение можно записать в виде , откуда или .
Таким образом , где и — неопределенные константы. Учитывая начальные условия , , находим , . Следовательно для четных получили соотношение
Других решений нет, так как эта формула верно задает и , а по двум начальным условиям решение рекуррентного соотношения задаётся однозначно.
Здесь мы использовали , так как несуществующий коридор можно уложить только единственным способом — никаким.
Для всех нечетных получаем (, , откуда по рекуррентному соотношению получаем тождественный нуль). То, что для нечетных , можно показать и без рекуррентных соотношений. В этом случае площадь коридора нечетна, а плитками можно покрыть только четную площадь.
Определим две последние цифры числа . Пусть . Тогда
Общий ответ: , где .