Скрыть решение
Решение
Без ограничения общности можем считать, что
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 гостям).
Значит, в разрезании пирога на минимальное количество кусков циклов не будет. Возьмём какую-нибудь из связных частей картинки, соответствующей минимальному разрезанию. Пусть в неё входят
p1 красных точек и
q1 синих. Тогда куски, входящие в линии этой связной части, составляют
p1/
p =
q1/
q часть всего пирога. Тогда
qp1 =
pq1. Поскольку
p и
q взаимно просты, это возможно лишь при
p1 =
p и
q1 =
q. Значит, картинка связна и в ней нет циклов. Тогда по индукции легко доказывается, что число линий в ней
p +
q – 1.
См. также данную задачу.
Ответ
p +
q – 1.