Задача 116
Красные, зеленые или синие плитки

В ряду черных квадратных плиток заменяют часть плиток цветными продолговатыми плитками, выбирая из красных (длиной две единицы), зеленых (длиной три) и синих (длиной четыре).

Если выбрать красные плитки, то замену можно осуществить ровно семью способами

 

Если выбрать зеленую плитку - таких способов только три.

 

И, наконец, если выбрать синюю плитку, то способов всего два.

Учитывая, что плитки нельзя смешивать, заменить черную плитку ряда длиной пять единиц можно всего 7 + 3 + 2 = 12 способами.

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

Примечание: Эта задача похожа на 117-ю задачу.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net