Разделы 
Дополнительно
Задача по математике - 3149
2019-05-26 
На прямой стоят две фишки, слева - красная, справа - синяя. Разрешается производить любую из двух операций: вставку двух фишек одного цвета подряд в любом месте прямой и удаление любых двух соседних одноцветных фишек. Можно ли за конечное число операций оставить на прямой ровно две фишки: красную справа, а синюю - слева?
Решение:
Первый способ. Будем называть две фишки, из которых левая - красная, а правая - синяя, инверсией. Рассмотрим число всех инверсий (например, на рис. число инверсий равно 3). Оказывается, четность этого показателя не может измениться.
Действительно, пусть, например, мы вставили две красные фишки так, что справа от них будет $k$ синих фишек. Тогда число инверсий увеличится на $2k$, и его четность не изменится. Аналогично разбираются три других случая (добавление двух синих фишек, удаление двух красных и удаление двух синих). Итак, четность числа инверсий является инвариантом.
Теперь заметим, что в исходной ситуации число инверсий равно 1, т. е. нечетно, а в желаемой - равно нулю, т. е. четно. Поэтому перейти к желаемой ситуации невозможно.
Комментарий. Иначе этот инвариант можно описать, как четность числа красных фишек, справа от которых стоит нечетное число синих.
Второй способ (выходящий за рамки программы 8-го класса). Рассмотрим прямую (эта прямая не имеет отношения к прямой, на которой стоят фишки) и две различных точки $A$ и $B$ на этой прямой. Поставим в соответствие каждому расположению фишек некоторое преобразование этой прямой. Это преобразование не будет изменяться при разрешенных операциях, т. е. будет инвариантом.
Преобразование строится так: мы двигаемся по прямой, на которой стоят фишки, слева направо. Когда встречается красная фишка, мы производим симметрию относительно точки $A$, а когда встречается синяя фишка - симметрию относительно точки $B$. Итак, последовательности фишек соответствует композиция симметрий.
Нетрудно видеть, что каждая операция над фишками не меняет композицию симметрий. Например, добавление двух красных фишек соответствует двум одинаковым симметриям, но композиция двух одинаковых симметрий - тождественное преобразование. Остальные случаи (добавление двух синих фишек, удаление двух красных и удаление двух синих фишек) аналогичны.
Итак, эта композиция является инвариантом, в то время как начальному и конечному расположению фишек соответствуют разные композиции - параллельные переносы на векторы 2 и -2 соответственно. Последнее утверждение можно проверить, введя координаты на прямой.
Комментарии.
1. Эта задача родилась из известной теоремы: два непрерывных пути внутри квадрата, соединяющие противоположные вершины, пересекаются. Дадим набросок доказательства.
Допустим, что пути не пересекаются. Тогда их можно заменить ломаными, которые тоже не пересекаются и звенья которых не параллельны сторонам квадрата. Покрасим одну ломаную в красный цвет, а другую - в синий. Будем параллельно передвигать прямую от одной стороны квадрата к другой. Прямая будет пересекать ломаную по набору красных и синих точек, с которым будет происходить то же самое, что с фишками в задаче (вставкам и удалением фишек соответствует прохождение прямой через некоторые внутренние точки звеньев ломаной, рис.).
2. Доказанное утверждение тесно связано с теоремой Жордана, которая утверждает, что всякая замкнутая несамопересекающаяся кривая делит плоскость на две части. Это интуитивно ясное утверждение отнюдь не просто доказать - дело в том, что кривая может не иметь ни одного гладкого участка, так что непонятно даже, как выбрать две точки по разные стороны от кривой.
Неэлементарный комментарий. Рассмотрим группу, порожденную двумя образующими a и b и соотношениями $a^2 = b^2 = 1$. Поставим в соответствие красной фишке элемент $a$, синей - элемент $b$, а последовательности фишек - элемент этой группы, который получается произведением слева направо соответствующих всем фишкам образующих $a$ и $b$. Ясно, что элемент группы не меняется при разрешенных операциях (в силу соотношений). Более того, из одной последовательности фишек можно получить другую тогда и только тогда, когда соответствующие элементы группы совпадают.
Можно проверить, что эта группа изоморфна полупрямому произведению групп $ \mathbb{Z}$ и $ \mathbb{Z}/2 \mathbb{Z}$. Она некоммутативна, а расположения фишек из условия задачи соответствуют элементам $ab$ и $ba$.
Ответ: Нельзя.
На прямой стоят две фишки, слева - красная, справа - синяя. Разрешается производить любую из двух операций: вставку двух фишек одного цвета подряд в любом месте прямой и удаление любых двух соседних одноцветных фишек. Можно ли за конечное число операций оставить на прямой ровно две фишки: красную справа, а синюю - слева?
Решение:
Первый способ. Будем называть две фишки, из которых левая - красная, а правая - синяя, инверсией. Рассмотрим число всех инверсий (например, на рис. число инверсий равно 3). Оказывается, четность этого показателя не может измениться.
Действительно, пусть, например, мы вставили две красные фишки так, что справа от них будет $k$ синих фишек. Тогда число инверсий увеличится на $2k$, и его четность не изменится. Аналогично разбираются три других случая (добавление двух синих фишек, удаление двух красных и удаление двух синих). Итак, четность числа инверсий является инвариантом.
Теперь заметим, что в исходной ситуации число инверсий равно 1, т. е. нечетно, а в желаемой - равно нулю, т. е. четно. Поэтому перейти к желаемой ситуации невозможно.
Комментарий. Иначе этот инвариант можно описать, как четность числа красных фишек, справа от которых стоит нечетное число синих.
Второй способ (выходящий за рамки программы 8-го класса). Рассмотрим прямую (эта прямая не имеет отношения к прямой, на которой стоят фишки) и две различных точки $A$ и $B$ на этой прямой. Поставим в соответствие каждому расположению фишек некоторое преобразование этой прямой. Это преобразование не будет изменяться при разрешенных операциях, т. е. будет инвариантом.
Преобразование строится так: мы двигаемся по прямой, на которой стоят фишки, слева направо. Когда встречается красная фишка, мы производим симметрию относительно точки $A$, а когда встречается синяя фишка - симметрию относительно точки $B$. Итак, последовательности фишек соответствует композиция симметрий.
Нетрудно видеть, что каждая операция над фишками не меняет композицию симметрий. Например, добавление двух красных фишек соответствует двум одинаковым симметриям, но композиция двух одинаковых симметрий - тождественное преобразование. Остальные случаи (добавление двух синих фишек, удаление двух красных и удаление двух синих фишек) аналогичны.
Итак, эта композиция является инвариантом, в то время как начальному и конечному расположению фишек соответствуют разные композиции - параллельные переносы на векторы 2 и -2 соответственно. Последнее утверждение можно проверить, введя координаты на прямой.
Комментарии.
1. Эта задача родилась из известной теоремы: два непрерывных пути внутри квадрата, соединяющие противоположные вершины, пересекаются. Дадим набросок доказательства.
Допустим, что пути не пересекаются. Тогда их можно заменить ломаными, которые тоже не пересекаются и звенья которых не параллельны сторонам квадрата. Покрасим одну ломаную в красный цвет, а другую - в синий. Будем параллельно передвигать прямую от одной стороны квадрата к другой. Прямая будет пересекать ломаную по набору красных и синих точек, с которым будет происходить то же самое, что с фишками в задаче (вставкам и удалением фишек соответствует прохождение прямой через некоторые внутренние точки звеньев ломаной, рис.).
2. Доказанное утверждение тесно связано с теоремой Жордана, которая утверждает, что всякая замкнутая несамопересекающаяся кривая делит плоскость на две части. Это интуитивно ясное утверждение отнюдь не просто доказать - дело в том, что кривая может не иметь ни одного гладкого участка, так что непонятно даже, как выбрать две точки по разные стороны от кривой.
Неэлементарный комментарий. Рассмотрим группу, порожденную двумя образующими a и b и соотношениями $a^2 = b^2 = 1$. Поставим в соответствие красной фишке элемент $a$, синей - элемент $b$, а последовательности фишек - элемент этой группы, который получается произведением слева направо соответствующих всем фишкам образующих $a$ и $b$. Ясно, что элемент группы не меняется при разрешенных операциях (в силу соотношений). Более того, из одной последовательности фишек можно получить другую тогда и только тогда, когда соответствующие элементы группы совпадают.
Можно проверить, что эта группа изоморфна полупрямому произведению групп $ \mathbb{Z}$ и $ \mathbb{Z}/2 \mathbb{Z}$. Она некоммутативна, а расположения фишек из условия задачи соответствуют элементам $ab$ и $ba$.
Ответ: Нельзя.
