Математикадан облыстық олимпиада, 2009-2010 оқу жылы, 9 сынып

Қабырғалары әр түрлі түсті болатын 100 ыдыс бар: әрбір ыдыстың бір жағы көк түсті, ал екінші жағы қызыл түсті(реверси ойынындағыдай). Осы ыдыстардың дұрыс 100-қабырғалы көпбұрыштардың төбелерінде орналасуын \emph{конфигурация} деп атаймыз. Бір жүрісте қатар тұрған үш ыдыс аударуға болады. Бастапқы мөлшерленген шекті жүріс санына байланысты ыдыстардың қанша түрлі конфигурациясын алуға болады? (екі конфигурация әр түрлі болады, егер олар кем дегенде бір төбедегі түсі әр түрлі болса.)

Комментарий/решение

Пронумеруем все шашки от $1$ до $100$ заметим мы за $67$ ходов сможем перевернуть одну шашку и остальные оставить в прежнем положении тогда .Допустим хотим перевернуть шашку с номером $1$ Заметим мы эту шашку перевернем $3$ раза а другие $2$ раза .Если мы смогли перевернут одну шашку то сможем все остальные откуда ответ $2^{100}$

67

Переформулируем задачу в более общее утверждение.

Пусть у нас имеется $N$ шашек, расставленных в вершинах правильного $N -$ уголника (по одной шашке в каждой вершине). Каждая шашка покрашена в один из $s$ цветов: $1, 2, 3, ..., s$. За один ход разрешается перекрасить любые $k$ подряд идущих шашек, при этом если цвет какой-нибудь (из перекрашиваемых шашек) был $i$, то её красят в цвет $i+1$ (если цвет шашки был $s$, то её перекрашивают в цвет $1$). Будем доказывать, что если $k$ $|$ $N-1$ и $(s,k)=1$, то из любой начальной раскраски шашек можно получить любую другую за конечное число ходов. Тогда ответ $2^{100}$ следует из частного случая утверждения при $N=100$, $k=3$ и $s=2$.

Вместо номера цвета каждой шашки будем рассматривать число применённых к ней операций перекрашивания, взятое по модулю $s$. Тогда изначальная раскраска шашек соответсвует набору $(0,0, ..., 0)$ (поскольку никакая шашка ещё не перекрашивалась). В таком случае один ход соответствует увеличиванию $k$ подряд идущих чисел в наборе на единицу.

Далее, поскольку $N-1$ кратно $k$, то в наборе можно зафиксировать любое число, а остальные $N-1$ разбить на блоки по $k$ подряд идущих чисел и увеличить их на единицу. Такую операцию будем называть переходом.

Теперь используем переходы последовательно:

1. Фиксируем первое число в наборе, получим:

$$ (0, 1, 1, ..., 1) $$

2. Фиксируем второе число в наборе. Поскольку все кроме него увеличиваются на один, то получим:

$$ (1, 1, 2, 2, ..., 2) $$

3. Фиксируем третье число в наборе, получим:

$$ (2, 2, 2, 3, 3, ..., 3) $$

Продолжая так, после $k$ шагов имеем набор вида:

$$ (k-1, k-1, ..., k-1, k, k, ..., k) $$

где первые $k$ чисел в наборе имеют значение $k−1$, а остальные — $k$.

4. Теперь увеличим на единицу первые $k$ чисел в наборе и получим:

$$ (k, k, ..., k) $$

Таким образом, мы показали, что из любого набора можно получить набор, в котором каждое число увеличено на $k$. (*)

Пусть $r \equiv k$ $(mod$ $s)$. Выполнив операцию перехода к начальному набору (при фиксированном первом числе) $s-r$ раз подряд, получим:

$$ (0, 0, 0, ..., 0) \to (0, s-r, s-r, ..., s-r)$$

Тогда из (*) следует, что

$$ (0, s-r, s-r, ..., s-r) \to (k, k+s-r, k+s-r, ..., k+s-r) \equiv (r, 0, 0, ..., 0) (mod s)$$

Таким образом из $(0, 0, 0, ..., 0)$ можно получить набор $(r, 0, 0, ..., 0)$. Аналогичным образом из $(r, 0, 0, ..., 0) \to (2r, 0, 0, ..., 0) \to (3r, 0, 0, ..., 0)$ и т.д.

В виду того, что $(s,k)=1$, то существует такое $i$, что $ir$ $\equiv 1$ $(mod$ $s)$. Стало быть

$$ (0, 0, 0, ..., 0) \to (r, 0, 0, ..., 0) \to (ir, 0, 0, ..., 0) \equiv (1, 0, 0, ..., 0)$$.

Из равенства (если так можно сказать) крайних членов в последней выкладке, следует, что из любой начальной раскраски шашек можно получить такую же, за исключением одной шашки (выбранной нами), цвет которой поменялся с $i$ на $i+1$. А значит из любой начальной конфигурации можно получить любую другую.