Задача к ЕГЭ по информатике на тему «подсчет количества слов/чисел» №1

Просмотров 4 Комментарии 0

Определите количество пятизначных чисел, записанных в девятеричной системе счисления, в записи которых цифра $3$ встречается не более одного раза, на первом месте не может стоять нечетная цифра, а на последнем не могут стоять цифры $1$ и $8$ .

Решение ручками

Алфавит $9CC$ — $0,1,2,3,4,5,6,7,8$

Нечетные — $1,3,5,7$ , четные — $0,2,4,6,8$

На первом месте в пятибуквенном слове могут стоять только четные числа их всего $5$ штук, но число не может начинаться с $0$ , следовательно, нам доступно только 4 числа.

На последнем месте могут использоваться все числа кроме $1$ и $8$ .

Цифра $3$ может встречаться не более одного раза. Найдем сначала числа без $3$ , а потом с $3$

Без $3$ : получаем $4$ варианта на первом месте, $8$ вариантов на $2$ -ом, $3$ -ем и $4$ -ом месте и $6$ вариантов на $5$ -ом месте.

С $3$ :

Случай, когда $3$ на $2$ -ом месте: получаем $4$ варианта на первом месте, $1$ вариант на втором месте (сама $3$ -ка), $8$ вариантов на $3$ -ем и $4$ -ом месте и $6$ вариантов на $5$ -ом месте. Так как $2$ -ое, $3$ -ье и $4$ -ое место ничем не отличаются, мы можем смело умножить результат для данного случая на $3$ (тройка может быть на любом из трех мест).

Случай, когда $3$ на $5$ -ом месте: получаем $4$ варианта на первом месте, $8$ вариантов на $2$ -ом, $3$ -ем и $4$ -ом месте и $1$ вариант (сама $3$ -ка) на $5$ -ом месте.

Ответ: $4 ⋅8⋅8⋅8 ⋅6+ 4⋅1 ⋅8⋅8⋅6 ⋅3+ 4⋅8 ⋅8⋅8⋅1 = 18944$

Решение программой (циклы):

ans = set()
alf = ’012345678’

for x1 in alf:
    for x2 in alf:
        for x3 in alf:
            for x4 in alf:
                for x5 in alf:
                    w = x1 + x2 + x3 + x4 + x5
                    if w[0] not in ’01357’ and w[-1] not in ’18’ and w.count(’3’) <= 1:
                        ans.add(w)
print(len(ans))

Решение программой (itertools):

from itertools import product

ans = set()
alf = ’012345678’

for w in product(alf, repeat=5):
    w = ’’.join(w)
    if w[0] not in ’01357’ and w[-1] not in ’18’ and w.count(’3’) <= 1:
        ans.add(w)

print(len(ans))

Ответ: 18944