1 тур Вариант 2 Задача №1

Вариант 2

Задача 1

Сколько существует натуральных чисел, для которых выполняются следующие условия:

1. Запись числа в шестнадцатеричной системе счисления состоит ровно из семи цифр, причем в качестве цифр могут использоваться только 1, 3, 8, С и F.
2. После перевода в двоичную систему счисления число будет содержать хотя бы одну последовательность из одиннадцати идущих подряд единиц, но не содержит ни одной последовательности из двенадцати или более идущих подряд единиц.

В ответе укажите целое число.

Решение

1)     Общий вид натурального числа: Х₁Х₂Х₃Х₄Х₅Х₆Х₇

2)     1₁₆=0001₂, 3₁₆=0011₂, 8₁₆=1000₂, С₁₆=1100₂, F₁₆=1111₂

3)     Два набора из четырех цифр после перехода в двоичную систему счисления дают последовательности из одиннадцати идущих  подряд единиц: 1FFС и 3FF8.

Набор 1: 1FFС₁₆ = 0001 1111 1111 1100₂

Набор 2:  3FF8₁₆ = 0011 1111 1111 1000₂

Варианты положения Набора 1  в натуральном семизначном числе:

1FFС Х₅Х₆Х₇       Х₁1FFС Х₆Х₇    Х₁Х₂1FFС Х₇    Х₁Х₂Х₃1FFС

При первом варианте существует 5³ = 125 различных чисел, содержащих Набор 1 в начале записи числа. Но, по второму условию задачи, необходимо исключить число 1FFСFFF₁₆, т.к. после перехода в двоичную систему счисления три последние цифры дают последовательность из двенадцати идущих подряд единиц: 125 ─ 1 = 124. Рассмотрим второй и третий вариант расположения Набора 1:  при любых комбинациях цифр 1, 3, 8, С и F после перехода в двоичную систему счисления не получается последовательности из двенадцати идущих подряд единиц, т.е. количество различных чисел соответственно 125 и 125 для второго и третьего варианта расположения. Вариант расположения Набора 1 в конце числа даёт 125 – 1 = 124 различных чисел, т.к. необходимо исключить число FFF1FFС₁₆.

124 + 125 + 125 + 124 = 498 различных чисел

Для Набора 2 находим количество различных чисел в зависимости от его местоположения в числе аналогично как для Набора 1.

3FF8 Х₅Х₆Х₇        Х₁3FF8Х₆Х₇      Х₁Х₂3FF8 Х₇     Х₁Х₂Х₃3FF8

124 + 125 + 125 + 124 = 498 различных чисел

4)     498 + 498 = 996

Ответ 996