Популярно о науке

Previous Entry Share Next Entry
Решение для хамелеончиков.
ahiin
Условие.

Правильный ответ: нет.

chameleon
(фотография, опять-таки, не моя, увы)

Пусть c — число серых хамелеонов, а b — число бурых. Заметим, что остаток от деления c – b на 3 — инвариант. Действительно, при встрече серого хамелеона с бурым, разность не меняется, при встрече серого с малиновым — уменьшается на 3, а при встрече бурого с малиновым — увеличивается на 3. В начале указанный остаток равен 1. Если же все хамелеоны станут одного цвета, то он равен 0 (разность c – b равна 0 или ±45). Следовательно, это невозможно.

Автор задачи В. Г. Ильичев, подробный разбор решения и обсуждение обобщений лежит здесь (задача М914).

  • 1
(Deleted comment)
В целом такое правило трудно указать, но среди олимпиадных задач инварианты на основе остатков от деления встречаются регулярно, так что их стоит проверять одними из первых.

+1 к к предыдущему оратору: чую основная фишка- это найти инвариант. причём при разборе вариантов изменения становится всё понятно на пальцах, но формально выразить- ой. сломал всю голову над суммами и чётностью.

Edited at 2014-10-30 06:57 pm (UTC)

Я собирался задать вопрос: рассматриваются ли "тройные встречи"? Но видимо нет.

  • 1
?

Log in

No account? Create an account