01:52 

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

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



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

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

Комментарии
2013-03-19 в 09:58 

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

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

2013-03-19 в 13:59 

wpoms
Step by step ...
Возможная трактовка условия

Предположим, что наша последовательность состоит из чисел 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` заменяются все единицы, или произвольное число?
Все

2013-03-19 в 16:20 

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

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

2013-03-19 в 16:29 

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

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

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


URL
2013-03-19 в 18:27 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
Нельзя (речь идет о заменах одного шага?)
Нет. Имелось ввиду 2 последовательных замены
`1 -> 121, 121 -> 1`
`2 -> 121, 1 -> 2`

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

2013-03-19 в 19:28 

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

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

Тогда зачем в условии сказано про последовательность замен, если композиция перестановок — тоже перестановка?
Можно все поменять за один ход, можно и за несколько. Ни в чем себе не отказывайте.

2013-03-19 в 23:31 

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` встречаются хотя бы по разу?

2013-03-19 в 23:40 

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

2013-03-20 в 07:50 

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

2013-03-20 в 08:38 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
А ноль-то там откуда? Или есть?)

2013-03-20 в 08:48 

А ноль-то там откуда? Или есть?)
Хммм . В оригинале есть. У нас он потерялся :weep3:

URL
     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная