|
|
 |
Условие
Хозяйка испекла для гостей пирог. За столом может оказаться либо 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 (см.задачу 31098 а, б).
Ответ
На p + q – 1 кусок.
Замечания
1. 10 баллов.
2. См. также задачу 35627.
3. Задача предлагалась также на Ленинградской математической олимпиаде (1990, заключительный тур, 9 кл., №7).
4. Ср. с задачей М1232 из Задачника "Кванта".
