В городе Плоском нет ни одной башни. Для развития туризма жители города собираются построить несколько башен общей высотой в 30 этажей. Инспектор Высотников, поднимаясь на каждую башню, считает число более низких башен, а потом складывает получившиеся величины. После чего инспектор рекомендует город тем сильнее, чем получившаяся величина больше. Сколько и какой высоты башен надо построить жителям, чтобы получить наилучшую возможную рекомендацию?

   Решение

Темы:    [ Разбиения на пары и группы; биекции ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 5 Классы: 8,9,10

Прислать комментарий

Условие

Ювелир сделал незамкнутую цепочку из N>3 пронумерованных звеньев. Капризная заказчица потребовала изменить порядок звеньев в цепочке. Из вредности она заказала такую незамкнутую цепочку, чтобы ювелиру пришлось раскрыть как можно больше звеньев. Сколько звеньев придется раскрыть?

Решение

[] звена (здесь [x] – целая часть числа x ). Заметим, что в каждой паре звеньев, бывших соседями, но переставших ими быть, по крайней мере одно звено должно быть раскрыто. Это же верно для пары несоседних звеньев, которые должны стать соседями. Если разбить звенья на группы так, чтобы любые два звена в группе являлись или впоследствии стали соседними (но не то и другое вместе), то из каждой такой группы может остаться нераскрытым не более одного звена. Такой группой, например, являются 4 звена, которые в старой цепочке следовали в порядке 1-2-3-4, а в новой должны быть в порядке 2-4-1-3. Другие примеры: в старой 1-2-3, в новой 1-3 (а 2 с ними не связано), или в старой 1-2, а в новой они не связаны. Разбив мысленно цепочку на четверки, с возможным остатком в 1, 2 или 3 звена, и потребовав такой порядок, при котором четверки и остаток изменяются указанным образом, заказчица обеспечит раскрытие не менее [] звеньев (лишнее звено из остатка прицепляется с другого конца). С другой стороны, раскрыв в исходной цепочке каждое второе звено, ювелир мысленно разобьет вторую цепочку на части, где в сумме не менее половины всех звеньев. В каждой части надо раскрыть не более половины звеньев, поэтому не менее четверти звеньев можно оставить нераскрытыми.

Ответ

[] звена.

Источники и прецеденты использования