Олимпиадная задача по комбинаторике для 8-10 классов от Произволова В. В.
Задача
2n радиусов разделили круг на 2n равных секторов: n синих и n красных, чередующихся в произвольном порядке. В синие сектора, начиная с некоторого, записывают против хода часовой стрелки числа от 1 до n. В красные сектора, начиная с некоторого, записывают те же числа, но по ходу часовой стрелки. Докажите, что найдётся полукруг, в котором записаны все числа от 1 до n.
Решение
Обойдём сектора против часовой стрелки. Где-то сразу за красным сектором K стоит синий сектор S. Можно считать, что в S написана единица (мы можем нужное число раз сдвинуть по "кругу" 1 → 2 → ... → n → 1 все числа в секторах – на результат это не повлияет). Пусть в K написано число k. "Пройдём" группу из k секторов против часовой стрелки, начиная с K. Пусть среди них b синих и r краcных. Тогда в них стоят синие числа 1, 2, ..., b и красные k, k – 1, ..., k – (r – 1). Поскольку b + r = k, то k – (r – 1) = b + 1, то есть в этих секторах стоят числа от 1 до k ровно по разу.
"Пройдём" теперь группу из n – k секторов по часовой стрелке, начиная со следующего за K. Пусть среди них с синих и d краcных. Тогда синие числа – это n, n – 1, ..., n – (c – 1), а красные – это k + 1, k + 2, ..., k + d, и ввиду равенства c + d = n – k числа от k + 1 до n встречаются по разу.
Объединение двух групп и даст нам искомый полукруг.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь