ГДЗ: Упражнение 233 - Параграф § 12 (Сочетания и их свойства) - (Вероятность и статистика 10 класс, Бунимович Евгений Абрамович, Булычев Владимир Александрович)

233 упражнение: ^*

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

Найдите минимальное число замков и распределение ключей.

Ответ

Большинство из 7 человек — не меньше 4, меньшинство — не больше 3. Достаточно рассматривать тройки: если ни одна тройка не может открыть сейф, то и меньшая группа не сможет; если любая четвёрка открывает, то и большая группа откроет.

Оценка снизу. Для каждой тройки членов правления должен существовать замок, ключа от которого нет ни у кого из троих (иначе тройка открыла бы сейф). Двум разным тройкам один и тот же замок служить не может: если у обеих троек нет ключа от замка \( L \), то у объединения троек (в нём не меньше 4 человек, а это уже большинство) ключа от \( L \) тоже нет — противоречие. Значит, замков не меньше, чем троек: \( C_7^3 = 35 \).

Распределение. Занумеруем 35 замков тройками членов правления и ключи от замка с номером \( \{a, b, c\} \) выдадим четырём людям, не входящим в эту тройку. Тогда любая тройка не откроет «свой» замок, а любая четвёрка откроет все замки: для каждого замка среди четверых есть хотя бы один, не входящий в его тройку (в тройке только 3 человека). Каждый член правления получает ключи от замков, тройки которых его не содержат: \( C_6^3 = 20 \) ключей.

Ответ: 35 замков; ключи от замка, соответствующего тройке членов правления, выдают четырём остальным (у каждого по 20 ключей).

Что применять при решении

Правило деления и сочетания

Если при подсчёте по правилу умножения каждая комбинация оказалась посчитанной \( m \) раз, результат нужно разделить на \( m \) (правило деления). Сочетание из \( N \) элементов по \( k \) — комбинация из любых \( k \) различных элементов без учёта их порядка; сочетания различаются только составом. С точки зрения теории множеств сочетание — это \( k \)-элементное подмножество \( N \)-элементного множества. При перечислении сочетаний выписывают только комбинации, в которых элементы идут по возрастанию: из 1, 2, 3, 4 по три — 123, 124, 134, 234.

Число сочетаний

Размещение получается из сочетания упорядочиванием его \( k \) элементов (\( k! \) способов), поэтому сочетаний в \( k! \) раз меньше, чем размещений: \( C_N^k = \dfrac{A_N^k}{k!} \). Обозначение читается «цэ из эн по ка». При вычислении дробь сокращают, не вычисляя факториалы целиком: \( C_7^4 = \dfrac{5 \cdot 6 \cdot 7}{3!} = 35 \). Число неупорядоченных пар \( C_N^2 = \dfrac{N(N-1)}{2} \). В ЭТ — функция ЧИСЛКОМБ(N; k). Если команда набирается из нескольких групп (2 мальчика из 13 и 2 девочки из 17), числа сочетаний перемножают: \( C_{13}^2 C_{17}^2 = 78 \cdot 136 = 10\,608 \).

\( C_N^k = \dfrac{N!}{k!\,(N-k)!} = \dfrac{N(N-1)\ldots(N-k+1)}{k!} \)

Свойства чисел сочетаний

1) \( C_N^0 = C_N^N = 1 \). 2) \( C_N^1 = C_N^{N-1} = N \). 3) Симметричность: \( C_N^k = C_N^{N-k} \) — выбрать \( k \) элементов всё равно что указать \( N - k \) невыбранных. 4) \( C_N^0 + C_N^1 + \ldots + C_N^N = 2^N \) — общее число подмножеств \( N \)-элементного множества (каждый элемент либо входит, либо нет). 5) Рекуррентное соотношение: подмножества делятся на содержащие фиксированный элемент \( x \) и не содержащие его. 6) Знакопеременная сумма \( C_N^0 - C_N^1 + C_N^2 - \ldots + (-1)^N C_N^N = 0 \) (бином Ньютона при \( a = -1, b = 1 \)). Приём доказательства тождеств: посчитать число комбинаций двумя способами.

\( C_N^k = C_{N-1}^{k-1} + C_{N-1}^k, \qquad \sum_{k=0}^{N} C_N^k = 2^N \)

Треугольник Паскаля

Таблица чисел \( C_N^k \): в вершине и по краям стоят единицы, каждое другое число равно сумме двух чисел, стоящих над ним (свойство 5). Строки: 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1; 1 6 15 20 15 6 1; 1 7 21 35 35 21 7 1; 1 8 28 56 70 56 28 8 1. Строка с номером \( N \) содержит \( N + 1 \) число, симметрична (свойство 3), сумма её чисел равна \( 2^N \), знакопеременная сумма — 0. Треугольник позволяет находить \( C_N^k \) без факториалов; Блез Паскаль посвятил ему «Трактат об арифметическом треугольнике».

Бином Ньютона

Биномом Ньютона называется выражение \( (a + b)^N \), а формулой бинома — тождество для раскрытия скобок: коэффициенты разложения — числа \( C_N^k \), то есть строка треугольника Паскаля с номером \( N \). Частные случаи: \( (a+b)^2 = a^2 + 2ab + b^2 \), \( (a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 \), \( (a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4 \). При раскрытии \( (x - 4y)^5 \) второе слагаемое берут со своим знаком и степенью: \( b = -4y \).

\( (a+b)^N = C_N^0 a^0 b^N + C_N^1 a^1 b^{N-1} + C_N^2 a^2 b^{N-2} + \ldots + C_N^{N-1} a^{N-1} b + C_N^N a^N b^0 \)

Другие упражнения из параграфа § 12

221 222 223 224 225 226 227^* 228^* 229^* 230^* 231^* 232^* 233^* 234^* 235

Данные параграфа

К параграфу →

Глава: Глава 5. Элементы комбинаторики
Параграф: § 12 — Сочетания и их свойства
Учебник: Вероятность и статистика 10 класс — Математика. Базовый уровень
Автор: Бунимович Евгений Абрамович, Булычев Владимир Александрович
Год: 2023

Уведомление об авторском праве и цитировании

ВНИМАНИЕ: Представленные фрагменты из учебных материалов используются исключительно в научно-образовательных целях в объеме, оправданном поставленной целью.

Данное использование осуществляется в рамках, установленных законодательством об авторском праве (в частности, нормами о свободном использовании произведения для образовательных целей).

В соответствии с законодательством, автор и источник заимствования указаны для каждого используемого фрагмента.