Разбор задачи c3 (демо егэ 2012)

Время выполнения-30 мин, уровень сложности-высокий

У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 3. Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 29? Ответ обоснуйте.

Решение:

Нам нужно построить граф, описывающий выполнение команд Утроителя. Строим его до тех пор, пока не получим число 9. 29/3=9 с остатком. Числа больше 9 дают только одну программу, т.к. нельзя применить команду "умножить на 3".

Построим этот граф:

После выполнения 2-х команд получаем числа: 3, 6, 4, 9. Определим число программ-решений, для получения из каждого из них числа 29.

Обозначим количество программ-решений для получения из числа n числа 29 как Р(n).

Количество программ-решений для получения из 1-цы числа 29 определяется по формуле: N=P(3)+P(6)+P(4)+P(9).

Выберем из чисел 3, 6, 4, 9 самое большое. Это 9. Определим P(9):

10*3>29, поэтому к 29 ведет только 1 решение.

27*3>29, поэтому к 29 ведет только 1 решение.

Получили, P(9)=1+1=2.

Остались числа: 3, 6, 4. Наибольшее из них число 6. Определим P(6):

18*3>29, поэтому к 29 ведет только 1 решение.

21*3>29, поэтому к 29 ведет только 1 решение.

24*3>29, поэтому к 29 ведет только 1 решение.

P(9)=2 решения.

Получили, P(6)=1+1+1+2=5.

Остались числа: 3,4. Наибольшее из них число 4. Определим P(4):

12*3>29, поэтому к 29 ведет только 1 решение.

15*3>29, поэтому к 29 ведет только 1 решение.

P(6)=5 решений.

Получили, P(4)=1+1+5=7.

Осталось число 3. Определим P(3):

Получили, P(3)=P(4)+P(9)=7+2=9.

N=P(9)+P(6)+P(4)+P(3)=2+5+7+9=23 программы.

Краткое решение:

P(N)=1 при N>9.

P(9)=P(10)+P(27)=2 программы.

P(6)=P(9)+P(24)+P(21)+P(18)=2+1+1+1=5 программ.

P(4)=P(6)+P(15)+P(12)=5+1+1=7 программ.

P(3)=P(4)+P(9)=7+2=9 программ.

P(1)=P(3)+P(4)+P(6)+P(9)=9+7+5+2=23 программы.