Разбор задачи C3 (демо ЕГЭ 2012)
У исполнителя Утроитель две команды, которым присвоены номера:
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 программы.