Последовательности, функции и их кодирование на Верченко
Ошибка.
Попробуйте повторить позже
a) перестановка 
чисел 
задана таблицей:
 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
 | 3 | 2 | 4 | 0 | 5 | 6 | 1 |
Например, 
. Найдите две различные перестановки 
и 
такие, что для всех 
выполняется
b) перестановка 
задана на чётном количестве чисел 
таблицей:
 | 0 | 1 | 2 | .. |  |  |
 |  |  |  | .. |  |  |
Здесь 
- перестановка чисел 
.
Докажите, что не существует перестановок 
и 
таких, что для всех 
выполняется 
Источники:
Пункт а, подсказка 1
Просто пытаться найти перестановки функции перебором очень тяжело. Однако можно заметить, что если мы домножим каждое значение перестановки f(x) на число взаимно простое с 7 и возьмём от получившихся чисел остатки при делении на 7, то мы получим перестановку. Попробуйте найти такие перестановки, подходящие под условие.
Пункт а, подсказка 2
Нужно взять два числа, взаимно простых с 7, чтобы их сумма имела остаток 1 при делении на 7. Тогда, умножив f(x) на эти числа, мы получим перестановки g(x) и h(x). Они подходят под условие.
Пункт b, подсказка 1
Мы почти ничего не знаем про расположение элементов перестановки. Однако точно знаем, чему равна сумма значений перестановки. Ведь её значения - 0,1,...,2n-1. То же самое можно сказать про перестановки g(x) и h(x). Попробуйте доказать требуемое от противного, записав условие через сумму перестановки.
Пункт b, подсказка 2
Суммы значений всех трёх перестановок равны (2n+1)*n. Тогда, используя условие пункта b, получаем, что (2n+1)*n = (2n+1)*n+(2n+1)*n(mod 2n). Попробуйте получить противоречие, рассматривая по модулю 2n.
а) Так как 
то 
и 
являются перестановками. Но тогда, например,
и выполняется
b) Из условия получим
С другой стороны, если указанное условии пункта b) представление существует, то
а это доказывает невозможность указанного представления.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
