Олимпиадная задача по теории чисел: минимум кусков пирога для p и q гостей

  Считая пирог длинным прямоугольником, разобьём его на p равных кусков  (p – 1  разрез) и на q равных кусков  (q – 1  разрез). Так как разрезов  p + q – 2,  то кусков  p + q – 1.

  Рассмотрим произвольное разбиение пирога объёма pq. Пусть гости – вершины графа (всего  p + q  вершин). По каждому куску строим ребро, соединяющее двух гостей, которым достаётся этот кусок при первой и второй раздаче. Рассмотрим одну из компонент связности. Сумма "объёмов" её рёбер должна быть кратна как p, так и q, значит, она равна pq. Следовательно, граф связен, а поэтому число его рёбер не меньше  p + q – 1  (см.задачу 131098 а, б).