Условие
Ювелир сделал незамкнутую цепочку из
N>3
пронумерованных звеньев.
Капризная заказчица потребовала изменить порядок звеньев в цепочке.
Из вредности она заказала такую незамкнутую цепочку, чтобы ювелиру
пришлось раскрыть как можно больше звеньев. Сколько звеньев придется раскрыть?
Решение
[
] звена (здесь
[
x]
– целая часть
числа
x ).
Заметим, что в каждой паре звеньев, бывших соседями, но
переставших ими быть, по крайней мере одно звено должно быть раскрыто.
Это же верно для пары несоседних звеньев, которые должны стать соседями.
Если разбить звенья на группы так, чтобы любые два звена в группе являлись
или впоследствии стали соседними (но не то и другое вместе), то из каждой
такой группы может остаться нераскрытым не более одного звена. Такой группой,
например, являются 4 звена, которые в старой цепочке следовали в порядке
1-2-3-4, а в новой должны быть в порядке 2-4-1-3. Другие примеры:
в старой 1-2-3, в новой 1-3 (а 2 с ними не связано), или в старой 1-2,
а в новой они не связаны.
Разбив мысленно цепочку на четверки, с возможным остатком в 1, 2 или 3 звена,
и потребовав такой порядок, при котором четверки и остаток изменяются
указанным образом, заказчица обеспечит раскрытие не менее
[
]
звеньев (лишнее звено из остатка прицепляется
с другого конца).
С другой стороны, раскрыв в исходной цепочке каждое второе звено, ювелир
мысленно разобьет вторую цепочку на части, где в сумме не менее половины
всех звеньев. В каждой части надо раскрыть не более половины звеньев,
поэтому не менее четверти звеньев можно оставить нераскрытыми.
Ответ
[
] звена.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
1998 |
|
Этап |
|
Вариант |
5 |
|
Класс |
|
Класс |
9 |
|
задача |
|
Номер |
98.5.9.7 |
