Задача #2734

Системы счисления

Сложнее ЕГЭ

(О. Лысенков) Известно что число $X = {* * * * A * *}_{16} = {* * * * 2 * * * 3}_{8}$ . На месте "*" может быть любая из цифр соответствующей системы счисления, причём каждая из звёздочек является значащей цифрой. Найдите количество вариантов числа X

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

114688

Программное решение (автор: В. Лукьянчиков)

k = 0
for n in range(16_785_411,134_217_727+1):
    if n%8==3 and n//4096%8==2 and n//256%16==10:
        k = k+1
print(k)

Аналитическое решение (автор: О. Лысенков)

Пояснение для тех, кто не знает или не помнит о прямом переводе из 16-чной и 8-чной в двоичную.
Так как 8 и 16 являются степенями 2-ки. То перевод из восьмеричной и шестнадцатеричной возможен с помощью метода триад и тетрад соответственно. То есть одной цифре в 8-чной будет ставится в соответствие три цифры в двоичной, а одной цифре в 16-чной будет ставится в соответствие четыре цифры в двоичной. То есть мы будем переводить вначале первую справа цифру 16-чной или 8-чной записи в двоичную и после дописывать незначащее количество нулей так, чтобы получилось 4 цифры, если мы изначально были в 16-чной и 3, если изначально были в двоичной. Так, например, $32_{8}$ будет переводится, как $011010_{2}$ , где 011 это перевод 3 в двоичную, а 010 перевод 2 в двоичную, так как 3 и 2 переводятся в двоичную не двумя цифрами, то для того, чтобы получилась тройка цифр к их записи дописываются незначащие нули, из конечной записи незначащие нули можно удалить и тогда получится $11010_{2}$ .

Решение

Использование шестнадцатеричной записи для представления в двоичной

Исходя из выше описанного записи ${* * * * A * *}_{16}$ соответствует 28 разрядов в двоичной(возможно среди них будут незначащие, но к этому вопросу вернёмся позже). Для удобства пронумеруем разряды справа налево, начиная с единицы, тогда, так как нам известно, что после двух звездочек справа идёт A в 16-чной записи числа, а $A_{16} = 10_{10} = 1010_{2}$ , то разряды с номерами 1-8 будут пока что звездочками, а разрядам 12-9 будет соответствовать 1010, то есть получаем следующую запись: ${* * * * * * * * * * * * * * * * 1010 * * * * * * * *}_{2}$ , то есть 16 звездочек, 1010 и ещё 8 звездочек.

Использование восьмеричной записи для представления в двоичной

Теперь перейдём к 8-чной записи X, как нам известно из условия 8-чная запись числа X представляется в виде ${* * * * 2 * * * 3}_{8}$ , в ней 9 разрядов, значит ей соответствует 27 разрядов в двоичной(опять же возможно среди них будут незначащие, но к этому вопросу вернёмся ещё чуть позже). Так как $2_{8} = 10_{2}$ , то с учётом того, что каждая цифра в 8-чной должна представляться в двоичной как 3 разряда, то получаем, что $2_{8}$ будет соответстовать $010_{2}$ , по аналогии $3_{8}$ будет соответствовать $011_{2}$ . Так как в 8-чной первая цифра справа это 3, то придерживаясь нумерации справа налево, начиная с единицы, получаем, что разрядам 3-1 будет соответствовать 011, так как дальше в 8-чной записи идут 3 звездочки, то разряды 12-4 будут на данный момент звездочками, так как после 3-х звездочек в 8-чной записи идёт цифра 2, то в двоичной разряды 15-13 будут соответственно равны 010 , дальше идут 4 звездочки в 8-чной, значит в 2-чной разряды 27-16 будут звездочками. По итогу получаем, что ${* * * * 2 * * * 3}_{8}$ соответствует запись ${* * * * * * * * * * * * 010 * * * * * * * * * 011}_{2}$ иначе говоря 12 звездочек 010 после 9 звездочек и 011.

Использование обоих представлений в двоичной.

Давайте запишем нашу двоичную запись, основанную на 16-чной и на 8-чной, так как ${* * * * A * *}_{16} = {* * * * 2 * * * 3}_{8}$ , то и эти записи должны быть равны. Для наглядности запишем их друг под другом.

****************1010********₂ - запись, cоответствующая ${* * * * A * *}_{16}$

************010*********011₂ - запись, cоответствующая ${* * * * 2 * * * 3}_{8}$

Исходя из этих 2-х записей можно увидеть, что в нижней записи на 1 разряд меньше. Если мы в нижнюю запись добавим ещё один значащий разряд, то получится, что в двоичной записи 28 значащих разрядов, так как 3-м разрядам в двоичной соответствует 1 в 8-чной, то получается, что в 8-чной будет 10 разрядов(так как для 9 разрядов должно быть не более 27 цифр в двоичной). Но мы из условия знаем, что их 9, значит на деле в записи ****************1010********₂ первая слева звездочка не значащая, то есть на деле имеем ***************1010********₂. Тогда получаем уже

***************1010********₂ - запись, cоответствующая ${* * * * A * *}_{16}$

************010*********011₂ - запись, cоответствующая ${* * * * 2 * * * 3}_{8}$

Так как записи между собой равны, то из нижней записи можно понять, что первые(справа) три цифры в 2-чной записи это 011, а также, что разрядам с номерами 15-13 будет соответствовать 010, в то же время из верхней записи известно, что разрядам с номерами 12-9 соответствует 1010, сочетая данные факты получим запись, где число звездочек уже меньше:

************0101010*****011₂,то есть 12 звездочек 0101010 после 5 звездочек и 011.

Переход к подсчёту числа вариантов

Теперь, когда мы нашли всё что было можно найти из условия, давайте разберёмся со звездочками. На месте звездочки в двоичной записи может быть 0 или 1, то есть для каждой звездочки имеем ровно 2 варианта, так как этих звездочек у нас 17, то хочется сказать, что ответ равен 2¹⁷,так как каждому из 2-х вариантов для первой звездочки может соответствовать любой из 2-х вариантов для 2-й звездочки, то есть имеем 2*2, этим 4-м вариантам может соответствовать любой из 2-х вариантов для 3-й звездочки, то есть имеем 8 вариантов,продолжая это до 17, получаем как раз 2¹⁷ вариантов.

Важный нюанс и его учёт в решении

Заметим, что в такой ситуации возможно, что все 17 звездочек равны 0, тогда наша запись превратится в 010101000000011₂, что будет соответствовать далеко не 8-ми значащим разрядам в 16-чной и 9 значащим разрядам в 9-чной. Чтобы в 16-чной было 8 разрядов необходимо, чтобы первая звездочка была значащей, то есть её значение не было равно 0, так как этой звездочке в двоичной записи соответствуют звездочки с номерами 28,27,26,25 и звездочка с номером 28 точно равна 0, то остаются звездочки с номерами 27, 26, 25, ***₂ = 0₁₆ только в ситуации, когда все 3 звездочки 0, значит не допустима лишь ситуация, когда все 3 разряда 0. По аналогии для 8-чной получаем ровно тоже самое, то есть имеем ситуацию, в которой звездочки с номерами 27,26,25 не должны быть одновременно равны 0, всего для 3-х звездочек имеем 2³=8, так как не подходит ситуация 000, а такая ситуация ровно одна, то получаем 7 вариантов, с этими 3-мя звездочками определились, осталось ещё 17 - 3 = 14 звездочек, так как хотя бы одна из тех 3-х звездочек не равна 0, то значащих разрядов в 16-чной и 8-чной будет 8 и 9 соответственно, причём независимо от значения данных 14 звездочек, так как они находятся правее, значит имеем для них 2¹⁴ вариантов, так как каждому из 2¹⁴ вариантов может соответствовать любой из 7 вариантов, то получаем $7 \times 2^{14} = 114688$ вариантов

Ответ:114688

Номер