Задача о разрезании пирога

Не задумывались ли вы над вопросом: “Сколько кусков пирога можно получить, делая n прямолинейных разрезов ножом”? Или более научно: каково максимальное число L областей, на которые плоскость делится n прямыми? Впервые эта задача была решена в 1826 году швейцарским математиком Якобом Штейнером.

Начнем с рассмотрения крайних случаев, памятуя, что начинать надо с самого крайнего. Плоскость без прямых — это одна область, с одной прямой — две области, с двумя прямыми — четыре области:

 

Рис. 1
(каждая прямая неограниченно продолжается
в обоих направлениях²)

Вы наверняка думаете, что L_n = 2ⁿ! Добавление новой прямой попросту удваивает число областей. К сожалению, это неверно. Мы могли бы достигнуть удвоения, если бы новая n-я прямая рассекала каждую старую область на две части. Но когда добавляется третья прямая — жирная линия на рис. 2, — мы быстро обнаруживаем, что она может рассекать самое большее три старые области вне зависимости от того, как расположены первые две прямые.

Таким образом, L₃ = 4 + 3 = 7 — самое большее, что можно сделать.

 

Рис. 2

А по некотором размышлении на ум приходит и подходящее обобщение, позволяющее нам установить формулу зависимости расчета количества плоскостей при n прямых от такого же количества при n – 1 прямых³. Новая n-я прямая (при n > 0) увеличивает число областей на k тогда и только тогда, когда рассекает k старых областей, а рассекает она k старых областей тогда и только тогда, когда пересекает прежние прямые в k – 1 различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать n – 1 старых прямых не более чем в n – 1 различных точках, и мы должны иметь k n. Нами установлена верхняя граница L_n L_{n – 1} при n > 0.

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

L_n = L_{n – 1} + n при n > 0,

L₀ = 1.

Уже известные значения L₁, L₂ и L₃ превосходно согласуются с этим соотношением, так что мы его берем. На его основе можем составить программу для расчета числа кусков пирога (мы забываем на время про “науку” и возвращаемся к “пирогу”), которая на школьном алгоритмическом языке имеет вид:

алг Пирог

нач цел число_разрезов, число_кусков, i

|Ввод исходного значения

вывод нс, "Введите число разрезов"

ввод число_разрезов

число_кусков := 1 |Когда разрезов нет

|Последовательно определяем число кусков

|для одного, двух, … разрезов,

|используя "предыдущее значение"

нц для i от 1 до число_разрезов

число_кусков := число_кусков + i

кц

|Вывод результата

вывод нс, "Общее число кусков пирога равно "

вывод число_кусков

кон

Так как для расчета значения L_n нужно знать L_{n – 1}, то можно использовать прием, который в программировании называют “рекурсией” [2]. Создадим простую и логичную рекурсивную (использующую самую себя в качестве вспомогательной) функцию:

алг цел Число_кусков(арг цел число_разрезов)

нач

если число_разрезов = 0

то

|Значение функции

знач := 1

иначе

|Используем рекурсию

знач := Число_кусков(число_разрезов - 1)

+ число_разрезов

все

кон

Основная часть программы, использующая эту функцию, оформляется очень кратко:

алг Пирог

нач цел число_разрезов

|Ввод исходного значения

вывод нс, "Введите число разрезов"

ввод число_разрезов

вывод нс, "Общее число кусков пирога равно "

вывод Число_кусков(число_разрезов)

кон

Конечно, компьютер — исполнитель “добросовестный”, делающий все, что нужно (в приведенных программах — выполняет 100 операций сложения). А нельзя ли облегчить ему задачу — найти формулу для расчета искомого значения?

Зачастую можно разобраться в рекуррентности, “развертывая” или “разматывая” ее всю до конца (точнее — до начала) следующим образом:

L_n = L_{n – 1} + n =

= L_{n – 2} + (n – 1) + n =

= L_{n – 3} + (n – 2) + (n – 1) + n =

…

= L₀ + 1 + 2 + … + (n – 2) + (n – 1) + n =

= L₀ + S_n, где S_n = 1 + 2 + … + (n – 2) + (n – 1) + n.

Учитывая, что L₀ = 1, можем записать: L_n = 1 + S_n. Другими словами, L_n на единицу больше суммы S_n первых n положительных целых чисел.

Таблица нескольких первых значений S_n выглядит так:

Эти числа называются также “треугольными числами”, поскольку S_n представляет собой число шаров, расставленных треугольником в n рядов. Например, четырехрядная расстановка состоит из S₄ = 10 шаров:

С учетом полученной зависимости можем составить программу решения обсуждаемой задачи, не использующую рекуррентное соотношение и рекурсию:

алг Пирог2

нач цел число_разрезов

вывод нс, "Введите число разрезов"

ввод число_разрезов

число_кусков :=

Сумма_чисел(число_разрезов) + 1

вывод нс, "Общее число кусков пирога равно "

вывод Число_кусков(число_разрезов)

кон

— где Сумма_чисел — функция для расчета суммы первых n целых чисел:

алг цел Сумма_чисел(арг цел n)

нач цел сумма, i

сумма := 0

нц для i от 1 до n

сумма := сумма + i

кц

знач := сумма

кон

Но для вычисления S_n вместо использования функции можно воспользоваться рассуждениями, представленными в виде формул:

Мы просто складываем S_n с самой собой, записанной в обратном порядке, так что сумма в каждой из n колонок справа равна n + 1⁴. После упрощения имеем:

Ну вот мы и получили требуемую формулу:

Соответствующая программа будет совсем небольшой:

алг Пирог3

нач цел число_разрезов, число_кусков

вывод нс, "Введите число разрезов"

ввод число_разрезов

число_кусков := div(число_разрезов *

* (число_разрезов + 1), 2) + 1

вывод нс, "Общее число кусков пирога равно "

вывод Число_кусков(число_разрезов)

кон

Задание для самостоятельной работы

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

Литература

1. Школа программирования: Тематический выпуск газеты-вкладки “В мир информатики” (“Информатика” № 11/2005).

2. Рекурсия / “В мир информатики” № 5 (“Информатика” № 37/2003).

3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.

Десять утверждений

Определите, есть ли среди следующих утверждений истинные:

1) только одно утверждение в этом списке ложно;

2) только два утверждения в этом списке ложны;

3) только три утверждения в этом списке ложны;

4) только четыре утверждения в этом списке ложны;

5) только пять утверждений в этом списке ложны;

6) только шесть утверждений в этом списке ложны;

7) только семь утверждений в этом списке ложны;

8) только восемь утверждений в этом списке ложны;

9) только девять утверждений в этом списке ложны;

10) все десять утверждений в этом списке ложны.

---

2 Но пирог, к сожалению, ограничен в размерах :(.

3 Напомним (см., например, [1]), что формулу, выражающую очередной член последовательности через один или несколько предыдущих членов, называют “рекуррентным соотношением”. Например, для арифметической прогрессии такая формула: a_i = a_{i – 1} + d (каждый последующий член равен предыдущему, увеличенному на разность прогрессии).