Показать скрытый текст
Чтобы привести пример нужного разрезания, представим пирог в виде отрезка, разбитого р—1 точками на р равных частей и q—1 точками на q равных частей. При взаимно простых р и q всего получится p+q—2 точек деления, а при НОД (р, q)=d образуется всего р+q—d—1 различных точек деления (d—1 из точек деления совпадут), так что отрезок будет разбит как раз на указанное в ответе число частей. (Ясно, что таким же образом можно разрезать пирог: если он имеет форму прямоугольника, достаточно провести ряд разрезов параллельных стороне.)
Например, на рисунке 1, где р=5, q=3, все 6 точек деления различны, и отрезок разбит на 7 кусков, а на рисунке 2, где р=15, 9=12 и d=3, различных точек деления 23 и отрезок разбит на 24 куска.
Приведем два различных доказательства, что указанное в ответе число кусков минимально.
Первое доказательство изложим сразу для обоих пунктов задачи.
Пусть пирог разрезан на несколько кусков так, что соблюдены условия задачи. Изобразим р гостей первой группы и q гостей второй группы точками на плоскости и соединим отрезками тех гостей, которым достается один и тот же кусок (см. примеры на рисунках). Мы получим систему вершин и ребер некоторого графа. Рассмотрим некоторую связную компоненту этого графа (множество всех вершин, в которые можно добраться из какой-то одной по ребрам графа). Соберем вместе куски, соответствующие ребрам этой компоненты. Из них можно собрать некоторое целое число k частей по 1/р пирога и некоторое целое число m частей по 1/q пирога. Но если k/p=m/q, то k должно делиться на p/d, a m — на q/d, тем самым, в этой компоненте собраны куски, составляющие не менее чем одну d-ю часть пирога. Если р и q взаимно просты, d=1 и компонента только одна, в общем случае их не более d. Но в каждой компоненте число вершин не более чем на 1 превышает число ребер. (Откинув некоторые ребра, можно получить из нее дерево — граф, в котором из каждой вершины в любую другую ведет один путь. Для него число вершин на 1 больше числа ребер.) Таким образом, общее число кусков не превосходит p+q—d.
Второе доказательство — более короткое — мы приведем лишь для случая когда р и q взаимно просты. Заметим здесь, что наша задача эквивалентна следующей: доказать, что наименьшее количество чисел, которые надо расставить в клетках таблицы рxq так, чтобы суммы по строкам равнялись 1/р, а суммы по столбцам — 1/q, равно p+q—1.
Докажем более общий факт. Пусть а1, а2,..., ар и b1, b2,..., bq - два набора положительных чисел с одинаковой суммой такие, что никакая подсумма чисел первого набора не равна никакой подсумме второго. Тогда количество чисел, которые можно вписать в клетки таблицы рxq так, чтобы суммы по строкам и столбцам соответственно равнялись числам этих двух наборов, не меньше p+q—1. Применяя этот факт к наборам из чисел 1/p,..., 1/p и 1/q,..., 1/q (взаимная простота p и q гарантирует выполнение условия о подсуммах), получим нужный результат.
Проведем индукцию по p+q (для р=q=1 все очевидно). Пусть p>q. Тогда в некоторой строке таблицы встречается лишь одно число из первой группы (иначе общее количество чисел в таблице не меньше 2р>р+q—1) — пусть это будет число а1, стоящее в первой строке и первом столбце, b1 — сумма чисел в этом столбце. Вычеркнув первую строку, применим утверждение к наборам a2, а3,..., ар и b1—а1, b2,..., bр — для него количество чисел на 1 меньше и условие о подсуммах очевидно выполнено. По предположению индукции в таблице (р—1)xq должно содержаться не менее чем (р—1)+(q—1)=р+q — 2 чисел. Добавляя выброшенное число а1 получим нужную оценку р+q—1 для таблицы pxq.
Записан