|
|
 |
Условие
В магазине в ряд висят 21 белая и 21 фиолетовая рубашка. Найдите такое минимальное k, что при любом изначальном порядке рубашек можно снять k белых и k фиолетовых рубашек так, чтобы оставшиеся белые рубашки висели подряд и оставшиеся фиолетовые рубашки тоже висели подряд.
Решение
Сначала покажем, что k, равного 10, нам хватит.
Первый способ. Будем идти вдоль ряда рубашек и считать отдельно белые и фиолетовые рубашки. Как только мы насчитаем 11 одноцветных – допустим, без ограничения общности, фиолетовых – рубашек, остановимся. Теперь снимем все белые рубашки, которые мы прошли (их не больше 10), и все фиолетовые рубашки, до которых мы еще не дошли (их ровно 10). При необходимости снимем еще несколько белых рубашек. Очевидно, что все 11 фиолетовых рубашек висят подряд (все белые рубашки, висевшие между ними, мы сняли). Оставшиеся белые рубашки тоже висят подряд: все оставшиеся фиолетовые рубашки мы сняли.
Второй способ. Встанем между 21-й и 22-й рубашкой, тогда слева и справа будет по 21 рубашке. Не умаляя общности, можно считать, что слева белых рубашек не больше, чем фиолетовых. Тогда слева не больше чем 10 белых рубашек, а справа не больше чем 10 фиолетовых (потому что их должно быть столько же, сколько белых слева). Снимем все белые рубашки слева и все фиолетовые рубашки справа. После этого все оставшиеся фиолетовые рубашки будут висеть слева, а все оставшиеся белые – справа. Если мы сняли n < 10 рубашек какого-то цвета, то можно снять еще 10 – n рубашек этого цвета – выполнение желаемого условия от этого не нарушится.
Теперь покажем, что рубашки могут висеть так, что меньшего k нам может не хватить.
Пусть рубашки висят в следующем порядке: сначала 10 белых рубашек, затем 21 фиолетовая и затем еще 11 белых. В этом случае после снятия k < 10 рубашек каждого цвета первой и последней рубашкой будут белые. Следовательно, белые рубашки не будут идти подряд.
Ответ
k = 10.
Замечания
Подходит также любой пример, в котором среди первых 21 рубашки есть 10 белых и 11 фиолетовых, а среди последних – наоборот: 11 белых и 10 фиолетовых.
