4. Джуди написала на доске число 3. Нику разрешено только прибавлять к написанному числу 1 или умножать написанное число на 3 (старое число при этом стирается). Сколькими способами Ник может получить из числа 3 число 20?

Обозначим через \(f(n)\) количество способов получить число \(n\). Последним действием можно прибавить 1 к \(n-1\), либо умножить на 3 число \(n/3\), если \(n\) делится на 3. Начальное число 3 уже получено одним способом: \(f(3)=1\).

Последовательно применяем правило: \(f(4)=1\), \(f(5)=1\), \(f(6)=1\), \(f(7)=1\), \(f(8)=1\), \(f(9)=2\), \(f(10)=2\), \(f(11)=2\), \(f(12)=3\), \(f(13)=3\), \(f(14)=3\), \(f(15)=4\), \(f(16)=4\), \(f(17)=4\), \(f(18)=5\), \(f(19)=5\), \(f(20)=5\). Например, при получении 9 есть два пути: прибавить 1 к 8 или умножить 3 на 3.

Ответ: 5 способов.