Задача на разрезание (индукция)

[fondet]

Задача:
В полоске $ 1 $ на $ 2\cdot n $ половина (то есть $n$) клеток белые, половина - черные (включая две крайних).
Докажите, что полоску можно разрезать на две, в которых черных и белых клеток поровну.

Задачу требуется решить, используя метод индукции.

Про переход я понял следующее: При доказательстве перехода мы можем считать, что мы умеем разрезать также и те полоски $2\cdot i$ (где $i$ черных и $i$ белых клеток), у которых по краям стоят не только две черные, но и две белые клетки. Ведь цвет, очевидно, не важен.

Также понял, что если мы докажем, что существует "разбиение" нашей полоски на 3 последовательные части такое, что в левой (и в правой) части стоит полоска, у которой равное количество черных и белых клеток, а в центре стоит полоска, у которой по краям стоят клетки одинакового цвета, то, применив предположение индукции к центральной полоске, мы получим требуемое. (Если в "левой" полоски равное количество цветов и в "правой" полоске равное количестве цветов - то, очевидно, в центральной полоске тоже будет равное количество)

Но мне не удалось доказать, что существует такое разбиение. Возможно, в этой задаче есть более простой способ совершить индукционный переход. Буду благодарен, если дадите идею.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[mihaild]

А обязательно по индукции? ИМХО "в лоб" сильно проще (возьмем самый длинный начальный кусок, в котором черных клеток больше, чем белых и внимательно на него посмотрим).

[fondet]

mihaild в сообщении #1471464 писал(а):

А обязательно по индукции? ИМХО "в лоб" сильно проще (возьмем самый длинный начальный кусок, в котором черных клеток больше, чем белых и внимательно на него посмотрим).

Ну, если мы к этому куску прибавим ещё 1 клетку, то получим место, по которому нам и надо разрезать.
Если так рассуждать, то мы сразу можем сказать "возьмем любой левый кусок длины меньше 2n, в котором число черных клеток равно числу белых. Произведя разрез, решим задачу". Но нам в таком случае надо доказать, что такой кусок вообще существует.

[svv]

fondet в сообщении #1471467 писал(а):

Но нам в таком случае надо доказать, что такой кусок вообще существует.

Один начальный кусок, в котором чёрных клеток больше, чем белых, существует по условию — это кусочек из одной самой левой чёрной клетки. Могут существовать и другие. Так как различных чёрнодоминантных начальных кусков конечное число, среди них найдётся самый длинный.

[fondet]

Да, действительно. Такой отрезок не может совпадать со всей полоской (так как в ней, по условию, одинаковое число белых и черных клеток). Как минимум один такой отрезок существует по условию. То есть "в лоб" задача действительно решается за 2 строчки.

[svv]

Если любите формалистику. Припишем чёрным клеткам значение $+1$, белым $-1$. Введём функцию $f(k)$, равную сумме значений всех клеток с номерами от $1$ до $k$ включительно. Очевидно,
$f(1)=1$
$f(2n-1)=-1$
$f(k)-f(k-1)=\pm 1$
Тогда существует такое $k$, что $1<k<2n-1$ и $f(k)=0$. Справа от клетки с этим номером разрезаем полоску.

[Cash]

С индукцией тоже проблем нет. В полоске найдутся соседние белая и чёрная (не из тех двух с краю) клетки. Убираем их, делаем разрез «по индукции», а затем снова добавляем.
Наверное, стоит выделить случай, когда разрез проходит «по шву», но проблем он не доставляет.

[mihaild]

Cash в сообщении #1471635 писал(а):

В полоске найдутся соседние белая и чёрная клетки

Тут нужно аккуратно - эта черная клетка может оказаться первой или последней.

[Cash]

Наверное да, но не сильно напряжно.

[TOTAL]

fondet в сообщении #1471446 писал(а):

Про переход я понял следующее: При доказательстве перехода мы можем считать, что мы умеем разрезать также и те полоски $2\cdot i$ (где $i$ черных и $i$ белых клеток), у которых по краям стоят не только две черные, но и две белые клетки. Ведь цвет, очевидно, не важен.

При доказательстве вообще забудем про цвет на краях.

[mihaild]

TOTAL в сообщении #1471688 писал(а):

При доказательстве вообще забудем про цвет на краях.

И будем доказывать, что любую полоску можно так разрезать? Это же неправда.

[TOTAL]

mihaild в сообщении #1471689 писал(а):

TOTAL в сообщении #1471688 писал(а):

При доказательстве вообще забудем про цвет на краях.

И будем доказывать, что любую полоску можно так разрезать? Это же неправда.

Доказывать будем не про любую. В индукции не будем обращать на это внимание, то есть будем выбрасывать внутреннюю пару разноцветных клеток.

[Sasha2]

Может условие для начала сформулировать как то более прозрачным образом.
Например непонятно, как вот такую полоску разрезать указанным способом?

ББЧЧ.

Вот что ней должно быть поровну?
В каждой половине должно быть по одному и тому же числу белых и черных клеток или просто число черных клеток в одной половине должно быть равно числу белых клеток в другой половине?