Конкурсная задача ММ175 (А-5) (8 баллов)

Натуральное число n назовем g-2-числом, если число 2n, записанное в системе счисления c основанием g получается из n перестановкой цифр. Какие основания встречаются (в натуральном ряду) чаще: те, для которых существуют трехзначные g-2-числа, или те, в которых нет трехзначных g-2-чисел?

Примечание: Расcматриваются позиционные системы счисления с натуральными основаниями g>1.

Решение

Приведу решение Олега Полубасова. В первой части оно по сути не отличается от других правильных решений. Интерес представляет вторая часть, обобщающая задачу.

Обсуждение

Задача ММ175 допускает обобщения по разным направлениям. Наиболее естественны два пути: изучение g-2-чисел произвольной значности; Изучение g-k-чисел для произвольного натурального k.

Конечно же я думал над задачами, сформулированными в последнем пункте решения Олега. И задал бы вместо ММ175…, если бы решил. Сначала у меня была идея закрыть все классы вычетов по какому-нибудь модулю. Так, например, по модулю 9 мне довольно быстро удалось закрыть почти все классы. В самом деле, классы двойки, пятерки и восьмерки закрываются уже двузначными числами: число записанное цифрами m и 2m+1 будет g-2-числом при g = 3m+2. Основания, кратные трем (т.е. классы нуля, тройки и шестерки), закрываются четырехзначными числами: m(m-1)(2m-1)(2m)_g, где g = 3m. При g = 9m+4 g-2-числом будет m(2m)(5m+2)(4m+1)(8m+3)(7m+3)_g. При g = 9m+7 g-2-числом будет (2m+1)(8m+6)m(5m+3)(7m+5)(4m+3)_g. Оставался только класс единицы. Но его закрыть так и не удалось. Я попробовал сменить модуль (разумеется, выбирая модули, являющиеся делителями чисел 2^s-1 с небольшими s. Однако, класс единицы не удалось закрыть ни по одному из модулей. Говоря о конкретных g, отмечу что в первой сотне осталось непокоренным единственное основание g = 91 (разумеется, g = 2 не в счет), коварным образом сравнимое с единицей одновременно по модулям 2, 5 и 9.

Алексей Волошин подсчитал, что доля оснований, для которых существуют трехзначные g-3-числа равна 49/104. Этот вывод совпал с результатами Сергея Половинкина. Сергей Половинкин не ограничился g-3-числами и оценил долю оснований для которых существуют трехзначные g-k-числа для достаточно многих k (для одних теоретически, для других статистически, компьютерным перебором). Оказалось, что чаще всего встречаются основания, в которых есть трехзначные g-4 числа (частота - 0.75). Второе место занимает k, равное 4.

Отмечу, числа, образованные цифрами от единицы до «девятки» (т.е. g-1) в порядке возрастания являются g-2-числами для всех четных оснований $g>2$. Эти же числа будут одновременно g-k-числами для всех k, взаимно простых с g и меньших g-1.

Награды

Дополнительные баллы ставились за всевозможные обобщения, углубления и дополнения, к которым располагает ММ175. Я не стал карать тех участников, которые утверждали что «оснований, для которых существуют трехзначные g-2-числа больше», посчитав это выражение фигурой речи, а не математическим утверждением. За решение задачи ММ175 Олег Полубасов получает 14 призовых баллов, Сергей Половинкин - 12 призовых баллов, Алексей Волошин и Николай Дерюгин - по 9 призовых баллов, Виктор Филимоненков, Алексей Извалов, Анатолий Казмерчук, Евгений Гужавин и Кирилл Веденский - по 8 призовых баллов.

Эстетическая оценка задачи - 4.9 балла

---