Выбрана 1 задача 
Убрать все задачи
На химической конференции присутствовало k учёных химиков и алхимиков, причём химиков было больше, чем алхимиков. Известно, что на любой вопрос химики всегда отвечают правду, а алхимики иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждого учёного хочет установить, химик тот или алхимик. Для этого он любому учёному может задать вопрос: "Кем является такой-то: химиком или алхимиком?" (В частности, может спросить, кем является сам этот учёный.) Доказать, что математик может установить это за 2k − 3 вопросов.
Решение
|
|
 |
Условие
Хозяйка испекла для гостей пирог. За столом может оказаться либо 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 из Задачника "Кванта".
