alt text

задан 25 Сен '14 23:45

изменен 25 Сен '14 23:46

10|600 символов нужно символов осталось
1

Здесь рассматривается остаток от деления не самого многочлена, а его значения в точке $%x$%.

Числа $%a$% и $%b$% можно заменить их остатками от деления на 10. Легко видеть, что если $%a$% чётно, то значениями функции будут только чётные остатки. Они для однозначной расшифровки не годятся. Также не годится число $%a=5$%. Остаются четыре варианта: $%a=1,3,7,9$%. Рассмотрим случай $%a=1$%, $%b=0$%. Подставляя в качестве $%x$% по порядку все цифры от 0 до 9 и беря остаток, можно убедиться в том, что получается следующий набор: 0, 1, 2, 9, 8, 5, 6, 7, 4, 3. Это перестановка цифр, что означает возможность однозначной расшифровки (просто по таблице).

Если теперь $%a=1$%, а $%b$% произвольно, то прибавление $%b$% к всем остаткам даёт их циклическую перестановку. Это значит, что любое $%b$% здесь подходит, и для расшифровки достаточно вычесть $%b$%.

Наконец, для чисел $%a=3,7,9$% легко проверить по таблице умножения, беря последнюю цифру, что домножение на $%a$% чисел списка от 0 до 9 даёт некоторую их перестановку. Это говорит о возможности однозначной расшифровки. Выглядит она просто: если домножали на 3, то для восстановления прообраза достаточно домножить на 7, так как $%3\cdot7$% оканчивается единицей. Домножение на 9 равноценно переходу от $%y$% к $%-y$%, то есть, например, цифра 6 перейдёт в -6, что эквивалентно 10-6=4.

Таким образом, для наличия однозначной расшифровки натуральное число $%a$% должно оканчиваться одной из цифр списка 1, 3, 7, 9, а $%b$% при этом может быть каким угодно.

ссылка

отвечен 26 Сен '14 0:05

@falcao, почему не годится число a=5?

(27 Сен '14 0:49) Alena

@Alena: по той же причине, по которой не годятся чётные числа: там все остатки будут делиться на 2, а здесь на 5. Ясно, что если мы положим a=5, то в качестве f(x) ничего кроме 0 и 5 не получим.

(27 Сен '14 0:52) falcao

@falcao, спасибо! Стало понятней. Еще раз разберу эту задачу, чтобы до конца все понять.

(27 Сен '14 1:15) Alena
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×291

задан
25 Сен '14 23:45

показан
295 раз

обновлен
27 Сен '14 1:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru