Турнир городов 2015 и ранее
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Хозяйка испекла для гостей пирог. За столом может оказаться либо 
человек, либо 
(
и 
— взаимно простые числа). На какое
минимальное количество кусков (не обязательно равных) нужно заранее разрезать пирог, чтобы в любом случае его можно было раздать
поровну?
Подсказка 1
Попробуем сначала построить пример. Пускай торт будет прямоугольным. Как тогда разрезать его на равные кусочки?
Подсказка 2
Верно! Нужно сделать p-1 засечку ножом на одной стороне и q-1 на другой так, чтобы они разбились на равные отрезки. Останется провести прямолинейные разрезы согласно засечкам! Попробуем для оценки построить по разбиению пирога граф. Как это сделать?
Подсказка 3
Вершинами будут p+q вершин, соответствующих гостям. Ребро соединяет двух гостей, если есть кусок, соответствующий данным вершинам при раздаче на p и на q гостей. Как показать, что граф связен?
Подсказка 4
Придадим торту еще одну характеристику — объем, равный pq. Что можно сказать о сумме объемов кусков, соответствующих ребрам одной компоненты связности?
Подсказка 5
Точно! Она равна pq, поскольку сумма всех ребер внутри компоненты делится на p и q. А что тогда можно сказать о графе?
Пример: Рассмотрим торт прямоугольной формы. Выберем одну из сторон и сделаем на ней 
засечек ножом, чтобы они делили её на
равных частей. Сделаем на той же стороне ещё 
засечек, которые делят её на 
равных частей. Теперь сделаем разрезы по нашим
засечкам и получим 
кусок. Если придёт 
человек, то отдадим им куски полученные по первым засечкам, а
если 
то по вторым.
Оценка: Рассмотрим произвольное разбиение пирога объёма 
и построим по нему граф. Пусть вершинами графа будут гости (всего
вершин). По каждому куску строим ребро, соединяющее двух гостей, которым достаётся этот кусок при первой и второй раздаче.
Рассмотрим одну из компонент связности. Сумма «объёмов» её рёбер (то есть объёмов кусков, соответствующих рёбрам)
должна быть кратна как 
так и 
(это следует из того, что если человек есть в этой компоненте, то в ней есть рёбра,
соответствующие всем кускам, которые ему полагаются, поскольку на каждый кусок претендует как человек из первой
группы, так и человек из второй), значит, она равна 
Следовательно, граф связен, поэтому число его рёбер не меньше
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
