---

Показать решение

---

Скрыть решение

Решение

Без ограничения общности можем считать, что p > q. Разделим пирог на p равных частей. А затем разделим пирог на q равных частей, начав с одного из уже проведённых разрезов (рис. 1). Тогда q – 1 разрезов, делящих пирог на q частей, пройдут через q – 1 из имеющихся p частей, и всего частей станет p + q – 1 (см. рис. 1, где p = 5, q = 3).
Теперь нужно доказать, что на меньшее число кусков пирог разрезать нельзя. Заметим, что каждый кусок входит в какую-то долю для p гостей и в какую-то долю для q гостей. Нарисуем такую картинку: поставим p красных точек, соответствующих долям для p гостей, и q синих точек, соответствующих долям для q гостей. Каждый кусок изобразим линией, соединяющей те доли, в которые он входит. Сумма размеров кусков, входящих в любую красную точку, равна 1/p, сумма размеров кусков, входящих в любую синюю точку, равна 1/q. Если в получившейся картинке имеется цикл, то одну из линий с минимальной массой в этом цикле можно удалить, изменяя веса остальных рёбер, чтобы сохранить указанное свойство (в точности означающее, что можно раздать пирог поровну и p, и q гостям).
Значит, в разрезании пирога на минимальное количество кусков циклов не будет. Возьмём какую-нибудь из связных частей картинки, соответствующей минимальному разрезанию. Пусть в неё входят p₁ красных точек и q₁ синих. Тогда куски, входящие в линии этой связной части, составляют p₁/p = q₁/q часть всего пирога. Тогда qp₁ = pq₁. Поскольку p и q взаимно просты, это возможно лишь при p₁ = p и q₁ = q. Значит, картинка связна и в ней нет циклов. Тогда по индукции легко доказывается, что число линий в ней p + q – 1.

См. также данную задачу.

Ответ

p + q – 1.