Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела функции
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#90278

a) перестановка f  чисел {0,1,...,6} задана таблицей:

x  0 1 2 3 4 5 6
f(x)  3 2 4 0 5 6 1

Например, f(2)= 4  . Найдите две различные перестановки g  и h  такие, что для всех x ∈{0,1,...,6} выполняется

f(x)≡ (g(x)+h(x))(mod7)

b) перестановка f  задана на чётном количестве чисел {0,1,...,2n− 1} таблицей:

x  0 1 2 .. 2n− 2  2n− 1
f(x)  i0  i1  i2  .. i2n−2  i2n−1

Здесь (i0,i1,...,i2n−1)  - перестановка чисел {0,1,...,2n− 1} .

Докажите, что не существует перестановок g  и h  таких, что для всех x∈ {0,1,...,2n− 1} выполняется f(x)≡(g(x)+ h(x))(mod (2n))?

Источники: Верченко - 2024, 11.3 (см. ikb.mtuci.ru)

Показать доказательство

а) Так как НОД (2,7) =НО Д(6,7)=1,  то g(x)≡ 2f(x)(mod7)  и h(x)≡ 6f(x)(mod7)  являются перестановками. Но тогда, например, g(x)=2f(x),h(x)=6f(x)  и выполняется

g(x)+ h(x)=2f(x)+6f(x)≡f(x)(mod7)

b) Из условия получим

2∑n− 1     2n∑−1
    f(x)=    x = (2n+ 1)n =n(mod(2n))
i=0      i=0

С другой стороны, если указанное условии пункта b) представление существует, то

2∑n−1     2∑n− 1    2n∑−1
    f(x)=    g(x)+    h(x)=2(2n+ 1)n≡ 0(mod(2n)),
i=0      i=0      i=0

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

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

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

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!