Число с наибольшими двоими

Question

Знаком «?» будем обозначать одну любую цифру от 0 до B (числа рассматриваем в двенадцатеричной записи).

Найдите среди всех чисел, которые подходят под шаблон 6??9???12 и у которых все цифры в записи различные, такое число, которое при разложении на простые числа имеет наибольше количество двоек в разложении. Если таких чисел несколько, напишите в ответ наибольшее. В ответ впишите число в десятеричной системе счисления

Answer 1

Разберём задачу по шагам.

1. Разбор формата числа

Все числа даны в двенадцатеричной системе счисления (base 12). Цифры в base 12 – это:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (десять в десятичной), B (одиннадцать в десятичной).

Дано шаблонное (масочное) число:

6 ?? 9 ??? 1 2

Где каждое «?» – это одна любая разрешённая в base 12 цифра, причём во всём числе все цифры должны быть различны.

Важно: последний «12» в записи – это две отдельные цифры 1 и 2 (а не «двенадцать» как одно целое).

Таким образом, всего цифр девять:

6
?
?
9
?
?
?
1
2

Причём цифры 6, 9, 1, 2 уже заняты, а пять символов «?» нужно заполнить другими различными цифрами, не совпадающими с уже имеющимися.

2. Требование к простому разложению (максимум двоек)

Задача говорит: среди всех подходящих (по маске и «различности» цифр) чисел выбрать то, у которого в разложении на простые множители (уже в десятичном виде) показатель степени простого числа 2 (то есть $v_2$ от числа) будет наибольшим. Если таких несколько, надо взять наибольшее в десятичной системе и вывести именно это десятичное число.

Проверка на степень двойки (наблюдение)

Оказывается (и это ключевой «трюк» задачи), что какое бы сочетание цифр мы ни подставляли в «?», последняя пара цифр 12 в base 12 делает всё число при переводе в десятичную систему оканчивающимся на 2 в модуле 4, а точнее:

В двенадцатеричной системе $12 \equiv 0 \pmod{4}$ , следовательно все старшие разряды (начиная с $12^2$ ) дают вклад, кратный 4.
Остаются лишь последние два разряда в base 12:
$\dots + 1 \times 12^1 + 2 \times 12^0$ .
Но $12^1 \equiv 0 \pmod{4}$ и $12^0 = 1$ .
Значит сумма последних двух разрядов по модулю 4 есть
$1 \cdot 0 + 2 \cdot 1 \;=\; 2 \pmod{4}.$

Иными словами, вне зависимости от того, что мы подставим вместо «?», число в десятичной системе даёт остаток 2 по модулю 4, то есть оно делится на 2 (чётное), но не делится на 4.

Следовательно, для любого подходящего числа $v_2(\text{число}) = 1$ . То есть все кандидаты имеют в точности одну двойку в факторизации (одну степень 2).

Вывод: по количеству двоек в разложении все «допустимые» числа одинаковы (каждое имеет ровно одну 2). Значит надо просто выбрать максимальное число (в десятичном смысле) из всех, которые удовлетворяют шаблону и условию «все цифры различны».

3. Поиск самого большого подходящего числа в base 12

Шаблон в base 12:

6 ? ? 9 ? ? ? 1 2

Запрещено повторять уже зафиксированные: 6, 9, 1, 2.

Оставшиеся свободные пять «?» мы хотим сделать как можно больше (идя слева направо), используя при этом самые крупные из доступных цифр $\{0,3,4,5,7,8,A,B\}$ , где

$A = 10_{(10)}$ ,
$B = 11_{(10)}$ .

Слева направо максимизация даёт:

Первая «?» (вторая цифра числа) = B (11)
Вторая «?» (третья цифра) = A (10)
Третья «?» (пятая цифра) = 8
Четвёртая «?» (шестая цифра) = 7
Пятая «?» (седьмая цифра) = 5

(Цифры 0, 3, 4 остались неиспользованными, но они меньше 5–7–8–A–B.)

Таким образом, самое большое число в двенадцатеричной записи есть:

6  B  A  9  8  7  5  1  2

где

$B = 11$ ,
$A = 10$ .

4. Перевод этого числа из base 12 в десятичную

Позиции (считаем слева направо, начиная с старшей степени):

\underbrace{6}_{12^8} \quad \underbrace{B=11}_{12^7} \quad \underbrace{A=10}_{12^6} \quad \underbrace{9}_{12^5} \quad \underbrace{8}_{12^4} \quad \underbrace{7}_{12^3} \quad \underbrace{5}_{12^2} \quad \underbrace{1}_{12^1} \quad \underbrace{2}_{12^0}

Обозначим это число за $N$ . Тогда

N = 6 \times 12^8 + 11 \times 12^7 + 10 \times 12^6 + 9 \times 12^5 + 8 \times 12^4 + 7 \times 12^3 + 5 \times 12^2 + 1 \times 12^1 + 2 \times 12^0.

Чтобы перевести, выпишем степени 12:

$12^0 = 1$
$12^1 = 12$
$12^2 = 144$
$12^3 = 1728$
$12^4 = 20736$
$12^5 = 248832$
$12^6 = 2985984$
$12^7 = 35831808$
$12^8 = 429981696$

Теперь умножаем и складываем:

$6 \times 12^8 = 6 \times 429981696 = 2579890176.$
$11 \times 12^7 = 11 \times 35831808 = 394149888.$
Сумма после 2‑го шага: $2579890176 + 394149888 = 2974040064$ (проверим аккуратно, получается $2{,}974{,}040{,}064$ ).
$10 \times 12^6 = 10 \times 2985984 = 29859840.$
Сумма: $2974040064 + 29859840 = 3003899904.$
$9 \times 12^5 = 9 \times 248832 = 2239488.$
Сумма: $3003899904 + 2239488 = 3006139392.$
$8 \times 12^4 = 8 \times 20736 = 165888.$
Сумма: $3006139392 + 165888 = 3006305280.$
$7 \times 12^3 = 7 \times 1728 = 12096.$
Сумма: $3006305280 + 12096 = 3006317376.$
$5 \times 12^2 = 5 \times 144 = 720.$
Сумма: $3006317376 + 720 = 3006318096.$
$1 \times 12^1 = 12.$
Сумма: $3006318096 + 12 = 3006318108.$
$2 \times 12^0 = 2.$
Итоговая сумма: $3006318110.$

Итак, искомое максимальное десятичное значение:

\boxed{3006318110}.

5. Ответ на задачу

Все числа по шаблону имеют ровно одну двойку в своём простом разложении ( $v_2(N)=1$ ).
Следовательно, выбираем наибольшее из допустимых.
В двенадцатеричной системе это $6\,B\,A\,9\,8\,7\,5\,1\,2$ .
При переводе в десятичную систему оно равно $3006318110$ .

Ответ (в десятеричной системе):

3006318110

Число с наибольшими двоими

Domanda

Pensiero

Risposta