Решение. а) Обозначим (Ж, З, К) упорядоченную тройку чисел, характеризующую состояние мешка на данный момент, т. е. количество жёлтых, зелёных и красных шаров в мешке. Изначально мешок находится в состоянии (1, 1, 2).
Если в первый раз из мешка вынимают жёлтый и зелёный шар и заменяют их красным шаром, то мешок переходит в состояние (0, 0, 3), когда все шары в мешке — красные. Если в первый раз из мешка вынимают зелёный и красный шар и заменяют их жёлтым шаром, то мешок переходит в состояние (2, 0, 1). Дальнейшие переходы из одного состояния в другое определяются однозначно и описываются цепочкой: (2, 0, 1) → (1, 1, 0) → (0, 0, 1) Видим, что в мешке остался красный шар. Аналогично, если в первый раз из мешка вынимают жёлтый и красный шар и заменяют их зелёным шаром, то мешок переходит в состояние (0, 2, 1). Дальнейшие переходы из одного состояния в другое определяются однозначно и описываются цепочкой: (0, 2, 1) → (1, 1, 0) → (0, 0, 1).
Видим, что в мешке снова остался красный шар. Таким образом, в любом случае оставшиеся в мешке шары (или шар) будут красными.
б) Легко видеть, что в мешке могут остаться зелёные шары: (3, 4, 5) → (4, 3, 4) → (3, 4, 3) → (2, 5, 2) → (1, 6, 1).
Докажем, что в любом случае оставшиеся в мешке шары будут зелёными. Каждый раз общее количество шаров в мешке уменьшается на 1, поэтому процесс завершится не более чем за 11 шагов. В начальном состоянии количество жёлтых и красных шаров нечётно, а количество зелёных шаров — чётно. Поскольку за один ход (выемку и замену шаров) количество шаров каждого цвета изменяется на 1, количества жёлтых и красных шаров всегда будут одной чётности, а количество зелёных шаров — противоположной чётности. Поэтому, никогда нельзя получить состояние, в котором количество зелёных и количество красных шаров оба будут нулевыми, также, как никогда нельзя получить состояние, в котором количество зелёных и количество жёлтых шаров будут нулевыми. Следовательно, в любом случае в конце мы получим состояние, в котором все оставшиеся в мешке шары будут зелёными.
в) Обозначим f(С)=Ж − З, где Ж и З — количества жёлтых и зелёных шаров в данном состоянии С = (Ж, З, К). Предположим, что из состояния С за один шаг мы перешли в состояние С' = (Ж', З', К')
Докажем, что f(С) и f(С') дают одинаковые остатки при делении на 3. Для этого покажем, что разность Δf = f(С') ‐ f(С) делится на 3. Рассмотрим несколько случаев.
Случай 1. Ж' = Ж − 1, З' = З − 1, К' = К + 2. Δf = f(С') − f(С) = (Ж' − З') · (Ж − З) = 0.
Случай 2. Ж' = Ж − 1, З' = З + 2, К' = К − 1. Δf = f(С') · f(С) = (Ж' − З') − (Ж − З) = −3.
Случай 3. Ж' = Ж + 2, З' = З − 1, К' = К − 1. Δf = f(С') − f(С) = (Ж' − З') − (Ж − З) = 3.
Видим, что f(С) и f(С') дают одинаковые остатки при делении на 3.
Для начального состояния C0(3, 4, 5) находим: f(C0) = Ж − З = 3 − 4 = −1.
Oбщее количество шаров в мешке остаётся неизменным, поскольку каждый раз два вынутых шара заменяются двумя шарами другого цвета. Если бы в конце в мешке все шары оказались бы одного цвета, то конечным состоянием было бы одно из трёх состояний (12, 0, 0), (0, 12, 0) или (0, 0, 12).
В любом случае f(Cn) будет делиться на 3, и, значит, f(C0) и f(Cn) дают разные остатки при делении на 3. Следовательно, применяя указанную процедуру, добиться того, чтобы в мешке оказались шары одного цвета, нельзя.
Ответ: а) красный; б) зелёный; в) нельзя.
PDF-версии: 