Тема 8. Количество информации и комбинаторика

8.04 Прочие прототипы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела количество информации и комбинаторика

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#23076Максимум баллов за задание: 1

Ваня переходит в $11$ класс. Он задумался о выборе предметов для сдачи ЕГЭ. Русский язык и Математику ему нужно сдать обязательно. Ваня решил, что хочет сдать два дополнительных предмета. Он выбирает из перечня: Английский, Физика, Химия. Сколько у Вани вариантов для выбора дополнительных предметов?

Показать ответ и решение

Попробуем перечислить все варианты пар выбранных дополнительных предметов. Если Ваня выбрал Английский в качестве первого предмета, то в качестве второго он может выбрать Физику или Химию. Получатся пары:

Английский $+$ Химия

Английский $+$ Физика

Если Ваня выбрал Физику в качестве первого предмета, то в качестве второго он может выбрать Английский или Химию. Получатся пары:

Физика $+$ Химия

Физика $+$ Английский

Если Ваня выбрал Химию в качестве первого предмета, то в качестве второго он может выбрать Английский или Физику. Получатся пары:

Химия $+$ Физика

Химия $+$ Английский

Заметим, что пары "Английский $+$ Химия"и "Химия $+$ Английский"являются одинаковыми, так как в данном случае не имеет значения, в каком порядке выбраны предметы. Есть ещё две пары, которые отличаются только порядком предметов. Таким образом, получим только $3$ уникальные пары:

1. Английский $+$ Химия

2. Физика $+$ Английский

3. Химия $+$ Физика

Ответ: 3

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#23078Максимум баллов за задание: 1

На этой неделе в классе дежурят следующие ученики: Мане О., Александр В., Илья А., Игорь В. и Вадим С., Саша. Р. Каждый день одного из учеников выбирают для уборки класса. Им нужно составить график дежурства на $6$ дней. Сколько можно составить графиков, в которых никто не будет убирать класс дважды?

Показать ответ и решение

Пронумеруем дни и по очереди выберем патрулирующего территорию. В первый день можно выбрать любого из шестерых. Во второй день уже любого из пятерых, так как нельзя выбирать того, кто был выбран в первый день. В третий день остается выбор из четверых, в четвертый — из трех учеников и так далее. Полученные способы необходимо перемножить, так как выбор последовательный, и количество вариантов выбрать очередного дежурного не зависит от того, кого мы выбрали ранее. Получается $6⋅5 ⋅4⋅3⋅2 ⋅1 = 6! = 720$ .

Число $n!$ (читается факториал) обозначает произведение чисел от 1 до $n$

Ответ: 720

Ошибка.
Попробуйте повторить позже

Задача 43#23080Максимум баллов за задание: 1

В шахматном турнире участвует $n$ человек и каждый с каждым играет по одной партии. Сколько всего партий сыграно в турнире? Ответ напишите для $n = 10$ .

Показать ответ и решение

У нас $n$ способов, чтобы выбрать первого человека. Затем у нас $n − 1$ способ, чтобы выбрать второго. Получается, что существует $n⋅(n− 1)$ способов выбрать любых два различных человека. Но поскольку таким образом мы каждую пару выберем дважды (условно Петя и Ваня это тоже самое что Ваня и Петя), то весь ответ нужно поделить на $2!$ . Окончательная формула для всех $n$ : $n⋅(n−1) --2!---$

Ответ: 45

Ошибка.
Попробуйте повторить позже

Задача 44#23081Максимум баллов за задание: 1

В колоде $36$ карт. Раздаются $5$ карт. Сколько может быть случаев появления тройки королей и одного туза среди розданных карт?

Показать ответ и решение

Найдем количество способов выбрать трёх королей из четырех:

3 C4 = 4.

Очевидно, количество случаев выбора одного туза из четырех тоже равно $4$ .

Четыре карты у нас уже собраны, осталось найти количество способов выбора одной карты из колоды, в которой уже нет королей и тузов, так как этих карт должно быть ровно 3 и 1. Такая колода будет состоять из $36− 4 − 4 = 28$ карт. Очевидно, у нас есть $28$ способов выбрать одну карту из $28$ -ми.

Собираем все пять карт вместе, объединяя их количества способов выпадения, и получаем $4⋅4⋅28 = 448$ .

Ответ: 448

Ошибка.
Попробуйте повторить позже

Задача 45#23083Максимум баллов за задание: 1

В колоде $52$ карты. Раздаются $3$ карты. Сколько может быть случаев появления червового туза среди розданных карт?

Показать ответ и решение

Так как туз может быть только $1$ (червовый), значит, для одной карты есть лишь один вариант — сам червовый туз. В таком случае посчитаем количество вариантов раздачи двух карт из оставшейся колоды (в условии не сказано, что туз должен быть $1$ , следовательно, $2$ оставшиеся карты выбираем из $51$ карты):

C251 = 51⋅25 = 1275.

Как уже было сказано, третьей картой может быть только одна карта — червовый туз, следовательно, случаев появления червового туза среди розданных карт может быть ровно $1275$ .

Ответ: 1275

Ошибка.
Попробуйте повторить позже

Задача 46#23084Максимум баллов за задание: 1

Сколько всего диагоналей в правильном $n$ -угольнике? Использовать можно знаки «*», «/», «+» и «-». Пробелы ставить не нужно.

Показать ответ и решение

Чтобы провести диагональ, нам нужно выбрать одну любую вершину, а потом ту, к которой мы будем проводить диагональ — это должна быть явно не та, которую мы выбрали в первый раз, и не соседняя к ней, то есть у нас уже на $3$ варианта выбора меньше. Ну и каждая диагональ будет таким образом выбрана по два раза, поэтому $n(n− 3)$ нужно будет еще разделить на $2$ .

Варианты правильных ответов:

n*(n-3)/2
(n-3)*n/2
(n-3)/2*n
n/2*(n-3)

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 47#25606Максимум баллов за задание: 1

Каждая ячейка памяти компьютера может принимать 20 различных значений. Для хранения некоторой информации использовали 4 ячейки памяти. Сколько различных значений может быть записано на месте этой информации?

Показать ответ и решение

В каждой из 4 ячеек можно хранить 20 значений, значит, по принципу умножения получаем: 20*20*20*20.

Ответ: 160000

Ошибка.
Попробуйте повторить позже

Задача 48#26195Максимум баллов за задание: 1

Чтобы скрыть свои тайны от чужих глаз, ТС решил кодировать свой GTD не на родном языке, а на собственном придуманном. Собрав алфавит из 100 разных символов, он захотел добавить его на собственный телефон, но обнаружил ограничение по памяти на нём - максимум 4 Мбайт загружаемой информации. Найдите, какое минимальное количество символов ТС придётся выкинуть из собственного алфавита(тем самым подставив под угрозу безопасность своего GTD), если известно, что кроме алфавита, ему нужно загрузить дополнительную информацию, которая составляет 1 бит для первого символа, 2 бита для второго символа, то есть для каждого следующего символа требуется в 2 раза больше дополнительной информации, чем для предыдущего. Чтобы закодировать алфавит, ТС нужно сложить количество бит, отведенных на кодирование самих символов, и количество бит, отведенных на загрузку дополнительной информации.

Показать ответ и решение

Возьмём, что ТС использует $N$ символов и $x$ бит на символ. Тогда можем составить неравенство:

$N ∗ x+ 20 + 21 + ...+ 2N −1 ≤ 225$

Свернём по формуле арифмитической прогрессии:

$N 25 N ∗ x+ 2 − 1 ≤ 2$

N не может быть равно 25, так как слева будет слишком много.

Возьмём $N = 24$ .

$5 24 ≤ 2$ , значит, 5 бит на символ, $x = 5$ .

Неравенство выполняется.

Получается, ТС нужно оставить 100 - 24 = 76 символов.

Ответ: 76

Ошибка.
Попробуйте повторить позже

Задача 49#26215Максимум баллов за задание: 1

Дано $5$ чисел. Сколько всевозможных пар можно из них составить?

Показать ответ и решение

Самое первое, что приходит в голову, — это начать перебирать всевозможные пары. Начнем последовательный перебор:

1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
3 1
...

Нетрудно проследить закономерность, что, если зафиксировать в паре первое число, то вторым к нему можно поставить ровно $5$ чисел. Но, так как первое число в паре не фиксировано, а может быть любыми из пяти, мы получаем $5$ чисел на первом месте $⋅$ $5$ чисел на втором месте. Значит, ответ будет равен $25$ .

Ответ: 25

Ошибка.
Попробуйте повторить позже

Задача 50#26217Максимум баллов за задание: 1

Дано две группы чисел. В первой группе содержится $5$ чисел, а во второй $7$ чисел. Сколько различных пар чисел из разных групп можно составить?

Показать ответ и решение

Изобразим две группы чисел.

$PIC$

Получаем, что для первого числа в пару можно поставить $7$ чисел из второй группы. А для второго сколько? Тоже $7$ . А для третьей? Тоже $7$ ! Получаем, что всего для каждой из пяти вершин первой группы есть $7$ вершин из второй группы, с которыми можно образовать пару. Таким образом, ответ равен $5⋅7 = 35$

Ответ: 35

Ошибка.
Попробуйте повторить позже

Задача 51#26218Максимум баллов за задание: 1

Дано 3 группы чисел. В одной $N1$ чисел, во второй $N2$ чисел, в третьей $N3$ . Сколько различных пар чисел из разных групп можно составить при $N1 = 4$ , $N2 = 8$ , $N3 = 6?$

Показать ответ и решение

Сколько способов есть выбрать одно число и первой группы - $N1$ . Сколько способов есть выбрать одно число из второй и третьей группы - $N2 +N3$ , Тогда всего пар с чисалми из первой группы = $N1 ⋅(N2 + N3)$ Все пары, где есть числа из 1 группы, перебрали, теперь нужно составить пары из двух груп - второй и третьей. Это будет $N ⋅N 2 3$ штук(см. предыдущую задачу).

Итоговое количество пар это сумма $N1 ⋅(N2 + N3 )+ N2 ⋅N3$ .

Вставляем наши циферки в формулу и пишем ответ.

Ответ: 104

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 52#26219Максимум баллов за задание: 1

Дано $4$ группы чисел. В одной $N1$ чисел, во второй $N2$ чисел, и так далее. Сколько различных пар чисел можно составить при условии что под парами подразумеваются числа внутри одной группы при $N1 = 3$ , $N2 = 5$ , $N3 = 7$ , $N = 9 4$ ?

Показать ответ и решение

Сколько можно составить различных пар в первой группе?

(N − 1)⋅N --1-------1 2

(см. Задача №2)

А сколько можно составить различных пар во второй группе?

(N2-−-1)⋅N2- 2

Тогда по индукции получаем формулу:

(N1-−-1)⋅N1 + (N2 −-1)⋅N2-+ (N3-−-1)⋅N3-+ (N4-−-1)⋅N4 2 2 2 2

Вставляем наши циферки в формулу и пишем ответ.

Ответ: 70

Ошибка.
Попробуйте повторить позже

Задача 53#35390Максимум баллов за задание: 1

Сколько существует целых чисел на отрезке от $2$ до $100$ ?

Показать ответ и решение

Можно подумать, что количество чисел равно $100 − 2 = 98$ . Однако это неверно. $98$ — количество промежутков между числами $2$ и $100$ , самих же чисел на $1$ больше. Таким образом, ответ равен $98+ 1 = 99$ .

Ответ: 99

Ошибка.
Попробуйте повторить позже

Задача 54#35391Максимум баллов за задание: 1

Сколько существует целых чисел на отрезке от $2$ до $100$ ?

Показать ответ и решение

Ответ: 99

Ошибка.
Попробуйте повторить позже

Задача 55#35396Максимум баллов за задание: 1

На улице длиной $100$ метров надо установить фонари на расстоянии $1$ метр друг от друга. Сколько потребуется фонарей? (На концах улицы также надо установить фонари)

Показать ответ и решение

Пусть длина улицы $1$ метр. В таком случае нужно установить всего $2$ фонаря на концах улицы. Пусть длина улицы равна $2$ метра. Тогда нужно установить $3$ фонаря – $2$ на концах и ещё один по центру. Пусть длина улицы равна $3$ метра. Тогда нужно установить $2$ фонаря на концах и ещё $2$ между ними – всего четыре. Можем заметить, что с увеличением улицы на $1$ метр вы увеличиваем количество фонарей на 1. Значит, для улицы длиной $100$ метров понадобится $101$ фонарь.

Ответ: 101

Ошибка.
Попробуйте повторить позже

Задача 56#35399Максимум баллов за задание: 1

$20$ мартышек пожали руку $60$ шимпанзе. Сколько было рукопожатий? А сколько было обезьян? Ответы запишите в порядке возрастания без пробелов.

Показать ответ и решение

Первая мартышка пожала руку шестидесяти шимпанзе. Скольким шимпанзе пожала руку вторая мартышка? Тоже $60$ . А третья? Тоже $60$ ! Таким образом, всего произошло $20 ⋅60 = 1200$ рукопожатий. А обезьян всего было $20 +60 = 80$ .

Ответ: 801200

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 57#36830Максимум баллов за задание: 1

Сколько рёбер в полном графе на $5$ вершинах?

Показать ответ и решение

Всего в графе $5$ вершин. Из каждой вершины выходит по $4$ ребра. Хотелось бы сказать, что ответ равен $5 ⋅4 = 20$ , но есть проблема: мы посчитали каждое ребро с двух концов, то есть два раза. Значит, полученное число нужно разделить пополам. Тогда ответ будет равен $5⋅4-= 10 2$ .

Ответ: 10

Ошибка.
Попробуйте повторить позже

Задача 58#36856Максимум баллов за задание: 1

На уроке физкультуры учитель попросил $7$ мальчиков построиться в шеренгу. Сколькими способами ребята могут это сделать?

Показать ответ и решение

Семь мальчиков нужно расположить в линию на семь мест. Для удобства пронумеруем места от одного до семи. На первое место можно поставить любого из семи мальчиков. На второе место — любого из шести мальчиков, поскольку один мальчие уже стоит на первом месте. На третье — любого из пяти мальчиков, поскольку два уже стоят. И так далее. Получается, всего есть $7⋅6 ⋅5⋅4⋅3 ⋅2⋅1 = 5040$ способов переставить $7$ мальчиков, или же $7! = 5040$ способов.

Ответ: 5040

Ошибка.
Попробуйте повторить позже

Задача 59#36926Максимум баллов за задание: 1

Сколькими способами можно из десяти пальцев выбрать три для откусывания?

Показать ответ и решение

Нужно выбрать $3$ пальца из $10$ . Это

3 -10!- 8⋅9⋅10- C10 = 3!⋅7! = 2 ⋅3 = 120

Ответ: 120

Ошибка.
Попробуйте повторить позже

Задача 60#37816Максимум баллов за задание: 1

Сколькими способами можно расставить на шахматной доске восемь ферзей так, чтобы они не угрожали друг другу, т. е. никакие два не стояли на одной вертикали, горизонтали и диагонали?

Примечение: Ферзь ходит на любое количество клеток по диагоналям, по вертикали и по горизонтали.

Показать ответ и решение

from itertools import permutations
n = 8
# Зафиксируем все позиции по x,
# т.к. в одном столбце стоять не могут
x = [1, 2, 3, 4, 5, 6, 7, 8]
count = 0
for i in permutations(’12345678’, 8):
    y = [int(_) for _ in i]  # перебор различных позиций по y
    flag = True
    for k in range(n):
        for j in range(k + 1, n):
            if abs(x[k] - x[j]) == abs(y[k] - y[j]):
                flag = False
                break
        if not flag:
            break
    if flag:
        count += 1
print(count)

Ответ: 92