Образовательный портал Павла Добряка

8.5. Комбинаторно-рекурсивная задача

В конце книги решим задачу, которую можно отнести как к комбинаторике, так и к рекурсии (во время написания книги она «гуляла» по нескольким разделам). Это сложная олимпиадная задача, которая интегрирует разные навыки, формируя находчивость. Символично то, что эта задача называется «счастливый билет».

 

Задача 8.5.1. Пусть номер билета состоит из n десятичных цифр (n-четное). Билет называется счастливым, если сумма левой половины цифр равна сумме правой половины цифр.

Например, билет 4563 счастливый, так как 4 + 5 = 6 + 3.

Сколько возможно различных счастливых билетов при:

  1. n = 4,
  2. n = 6,
  3. n = 8.

Примечание 1. Мы решили задачу рекурсивным способом, причем рекурсия в задаче используется два раза: при увеличении результата (то есть при переходе к новой строчке таблицы) и при увеличении (при переходе к новому столбцу). Хотя комбинаторика тоже использовалась, но на предварительном этапе рассуждений, когда мы определяли количество перестановок слагаемых.

Если мы вспомним задачи на подсчет количества программ (например, 3.2.9: из одного числа получить другое при операциях +1 и +2), то мы решали их тремя методами: графовым, комбинаторным и рекурсивным. Подумаем, можно ли нашу нынешнюю задачу решить полностью комбинаторным методом.

Если мы посмотрим на столбцы в последней заполненной нами таблице, то мы увидим числа, очень нам знакомые по комбинаторным задачам. Это же числа из треугольника Паскаля! Сравните:

Резуль-

тат

Вариан-

тов при 

n=2

Вариан-тов при n=4

Вариан-тов при n=6

Вариан-тов при n=8

0

1

1

1

1

1

1

2

3

4

2

1

3

6

10

3

1

4

10

20

4

1

5

15

35

5

1

6

21

56

6

1

7

28

84

 

 

 

Примечание 2. Для чего еще применяются срезы треугольника Паскаля? Посчитайте количество кругов в треугольнике и сравните со срезом:

Такие числа зазываются треугольными.

Числа из следующего среза – это количество пирамидок (тетраэдров), которые мы можем сложить из шаров. Поэтому эти числа называются тетраэдрическими.

Итак, мы решили несколько задач, где используются срезы треугольника Паскаля:

В целом же комбинаторика – большой и увлекательный раздел математики. Решая дополнительные задачи из этого приложения, мы освоили ряд исследовательских приемов, развив навыки, которые нужны на тот случай, если в ЕГЭ попадется задача нового типа, которую мы еще не прорешивали.