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