Замена элементов

[wpoms.]

Дана конечная последовательность с членами из множества `A={0, 1, 2, ... , 121}`, разрешено заменять любой её член на число из множества `A` таким образом, чтобы одинаковые члены последовательности заменялись одинаковыми числами, а разные — разными. (Можно оставлять члены последовательности без замены.) Цель — получить из данной последовательности с помощью некоторого числа таких замен новую последовательность, чья сумма делилась бы на `121`. Доказать, что возможно достичь цели при любой начальной последовательности.

Исправление: в множество A добавлен нулевой элемент.

@темы: Теория чисел

Comments

[Adjirranirr]

Немного не проникся условием. Одинаковые на одинаковые и vice versa — общее правило для одной замены или всей последовательности?
Т.е. разрешено ли провести последовательно замены `1 -> 121,\ 121 -> 1`, `2 -> 121,\ 1 -> 2`, или число `2` во второй замене заменять на `121` уже нельзя?

И еще. При замене, например, `1 -> n` заменяются все единицы, или произвольное число?

[wpoms]

Возможная трактовка условия

Предположим, что наша последовательность состоит из чисел 1, 2, 3, 4, 4.

На очередном шаге нужно указать замену для каждого числа последовательности
1 -> n1
2 -> n2
3 -> n3
4 -> n4
4 -> n5

n1, n2, n3, n4 должны быть различны, но n4 и n5 должны совпадать.

Некоторые числа могут оставаться без изменения (т.е. отображаться сами на себя).

или число `2` во второй замене заменять на `121` уже нельзя?

Нельзя (речь идет о заменах одного шага?)

При замене, например, `1 -> n` заменяются все единицы, или произвольное число?

Все

[All_ex]

Всё равно не понятно можно ли использовать при замене числа, которые уже есть в исходной последовательности...
То есть в приведённом примере может ли, например, `n_1 in {2; 3; 4}`...
Иначе, получим такой алгоритм...
На первом шаге все единицы заменяем на 121, а остальные не меняем....
На втором шаге все двойки меняем на 121.... ну, и так далее...

Хотя так видимо можно, поскольку изначально элементов последовательности может быть больше, чем 121... и все элементы множества уже могут быть использованы как члены последовательности не менее одного раза...

[Гость]

На первом шаге все единицы заменяем на 121, а остальные не меняем....

Это хорошо, если 121 не присутствует в последовательности

На втором шаге все двойки меняем на 121.... ну, и так далее...

А вот это уже не получится

Впрочем,

Хотя так видимо можно, поскольку изначально элементов последовательности может быть больше, чем 121...

А вот это совсем неприятное замечание ... )

Sea $A=\{0,1,\ldots, 121\}$. Consideremos dos subconjuntos arbitrarios de $A$, definidos como sigue: $X=\{x_1,x_2,\ldots, x_k\}$ y $Y=\{y_1,y_2,\ldots, y_k\}$ (ambos con la misma cantidad de elementos). Consideremos una función biyectiva $f$ de $X$ en $Y$, tal que $f(x_i)=y_i$. Demostrar que, dada una secuencia $a_1, a_2, \ldots, a_n$ de números del conjunto $A$ (no necesariamente distintos), se puede realizar una elección conveniente de los conjuntos $X$ e $Y$ de tal manera que la secuencia $f(a_1), f(a_2), \ldots, f(a_n)$ es tal que la suma de sus términos es múltiplo de $121$. Nota: $f(t)=t$ si $t$ no está en el conjunto $X$ elegido.

[Adjirranirr]

Нельзя (речь идет о заменах одного шага?)

Нет. Имелось ввиду 2 последовательных замены
`1 -> 121, 121 -> 1`
`2 -> 121, 1 -> 2`

То есть, как я понял, после замены из последовательности `{a_n}_{n = 1}^{k}` получается последовательность `{\phi (a_n)}_{n=1}^{k}`, где `\phi` — некоторая перестановка (в смысле — биекция на себя) множества `A`? Тогда зачем в условии сказано про последовательность замен, если композиция перестановок — тоже перестановка? =)

[wpoms]

и все элементы множества уже могут быть использованы как члены последовательности не менее одного раза...

В этом случае возможно только менять элементы последовательности местами.

в смысле — биекция на себя

Точнее, биекция одного подмножества A на другое, которая может рассматриваться как подмножество биекции A на себя.

Тогда зачем в условии сказано про последовательность замен, если композиция перестановок — тоже перестановка?

Можно все поменять за один ход, можно и за несколько. Ни в чем себе не отказывайте.

[Adjirranirr]

Очевидно, если были неравные числа, то равными их сделать нельзя.
Но сумма `2 * m + 119 * n` никогда не делится на 121 при `m != n,\ 1 <= m, n <= 121`. Значит, если последовательность имеет вид, например, `1,\ 1,\ 2,\ 2,\ ...,\ 2` и длину 121, то она не удовлетворяет условию задачи (цель недостижима =)

Рассмотрим уравнение `2*m + 119*n = 121*p`.
Если `m > n`, то `m = n + k,\ 0 < k <= 120`, и `121n + 2k = 121p => 2k = 121 (p - n)`. Так как `gcd (121,\ 2) = 1`, `k` делится на `121`, что невозможно.
Если `m < n`, то `n = m + k,\ 0 < k <= 120`. Тогда `121m + 119 k = 121 p => 119 k = 121 (p - m)`. Так как `gcd (121,\ 119) = 1`, `k` делится на `121`, что невозможно.

Или в последовательности все числа из `A` встречаются хотя бы по разу?

[Adjirranirr]

Если хотя бы по разу.
Пусть `n_1` — количество единиц, `n_2` — количество двоек, ..., `n_121` — количество чисел `121`. Тогда при `n_1 = 2,\ n_2 = 119,\ n_3 = n_4 = ... = n_121 = 121` последовательность, по тем же соображениям, условиям задачи не удовлетворяет.

[wpoms]

`1,\ 1,\ 2,\ 2,\ ...,\ 2`
Поменяйте 1->0, 2->121

[Adjirranirr]

А ноль-то там откуда? Или есть?)

[Гость]

А ноль-то там откуда? Или есть?)

Хммм . В оригинале есть. У нас он потерялся