Задача
На полосе бумаги написаны подряд 60 знаков: "×" и "0". Эту полоску разрезают на куски с симметричным расположением знаков. Например:
0, × ×, 0 × × × × 0, × 0 ×, ... .
а) Докажите, что существует такой способ разрезания, при котором кусков не больше 24.
б) Приведите пример такого расположения знаков, при котором меньше 15 кусков получить нельзя.
Решение
а) Разобьём полоску на 12 полосок длины 5. Перебором нетрудно проверить, что любую такую полоску можно разбить на два симметричных куска. б) Достаточно построить полоску, в которой нет симметричных кусков длины больше 4. Это, например, полоска, состоящая их 10 кусков вида
× 0 × 0 0 ×.
Действительно, любой симметричный кусок длины больше 4 содержит в середине симметричный кусок длины 5 или 6. Выпишем все теоретически возможные симметричные куски такой длины, не содержащие трёх одинаковых знаков подряд (таких в нашей полоске заведомо нет): × [0 × 0 ×],
[0 0 × 0] 0, × [× 0 × ×], [0 × 0 ×] 0, 0 0 [× × 0 0], [× 0 × ×] 0 ×, [× × 0 0] × ×, 0 × [0 0 × 0]. В каждом из них есть фрагмент (выделен скобками), отсутствующий в нашей полоске.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь