Что значит «каждая цифра встречается»?

Что в записи есть хотя бы одна единица и хотя бы одна двойка. Поровну их быть не обязано: число 111112 условию удовлетворяет, в нём пять единиц и одна двойка.

Почему всех записей ровно 64?

На каждой из шести позиций выбор из двух цифр, и выборы независимы. По правилу умножения записей 2 · 2 · 2 · 2 · 2 · 2 = 2⁶ = 64. Все они шестизначные, потому что ни 1, ни 2 не равны нулю и первая цифра не может оказаться нулём.

Почему исключений ровно два?

Не подходят только записи из одинаковых цифр: 111111 без двойки и 222222 без единицы. В любой другой записи из единиц и двоек встречаются обе цифры. Эти два случая не пересекаются, поэтому вычитаем ровно два.

Шестизначные числа из единиц и двоек: дерево вариантов и дополнение

Условие «каждая цифра встречается» мешает просто перечислить подходящие числа. Ниже — как посчитать все записи по дереву вариантов, а потом вычесть те, которые условию не отвечают.

видеоразбор · 2 мин 10 с

Тот же разбор за две минуты

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

Ролик лежит на нашем сервере: без сторонних проигрывателей и рекламы. Звук включается в плеере.

Задача

Сколько существует шестизначных чисел, состоящих только из цифр 1 и 2, если известно, что каждая из них встречается?

Задача школьного этапа ВсОШ — Всероссийской олимпиады школьников — на платформе «Сириус»: математика, 8 класс, 2021 год, группа 2, задание 5.1. Условие и авторство принадлежат организаторам; ниже — наш учебный разбор. Рисунка в оригинале нет, схемы сделаны нами.

Выпишите для начала несколько подходящих чисел. Например, 111112 и 121212: в каждом есть и единица, и двойка. Поровну их быть не обязано.

Догадка

«Каждая цифра встречается» — значит, единиц и двоек должно быть поровну: по три. Считаем, сколькими способами расставить три единицы среди шести мест.

Так думает почти каждый, кто читает условие быстро. Но «встречается» означает «есть хотя бы одна», а не «столько же, сколько других». Число 111112 условию отвечает, а при таком подсчёте потеряется. Значит, считать надо иначе.

Рассуждение

Что мешает считать напрямую. Подходящих чисел много, и они устроены по-разному: где-то одна двойка, где-то четыре. Перебирать по количеству двоек — значит разбирать пять случаев.

Зато легко описать те числа, которые условию не отвечают. Если двойки нет, все шесть цифр — единицы: это 111111. Если нет единицы, остаётся 222222. Больше исключений нет: в любой другой записи из единиц и двоек встретятся обе цифры.

Два исключения: 111111 — нет цифры 2; 222222 — нет цифры 1. — Неподходящих чисел ровно два. Осталось узнать, сколько записей всего.

Поэтому план такой: посчитать все записи из единиц и двоек, а потом вычесть эти две. Такой ход называют подсчётом через дополнение.

Как посчитать все записи. Первая цифра — либо 1, либо 2. Нарисуем два дерева: в корне левого единица, в корне правого двойка. Для каждой следующей цифры снова два варианта.

Точки с цифрами — вершины, соединяющие их линии — ветви, начальная вершина — корень. Вершину без продолжений называют листом; когда из листа вырастают две новые ветви, листом он быть перестаёт. Путь идёт от корня по ветвям, и цифры вершин по порядку складываются в запись числа. Пока остановимся на трёх цифрах.

Дерево с корнем 1: записи 111, 112, 121, 122. Выделенный сплошной путь даёт 121. — Одно дерево даёт разные числа: 121 и 122 отличаются последней ветвью.

Дерево с корнем 2: записи 211, 212, 221, 222. Выделенный пунктирный путь даёт 211. — Второе дерево отвечает за записи, которые начинаются с двойки. Путь отмечен и цветом, и типом линии.

Доказательство

Почему листья можно считать вместо чисел. К каждому листу ведёт ровно один путь от корня: у любой вершины, кроме корня, только один предшественник. Значит, лист задаёт одну запись.

Разные листья дают разные записи: их пути где-то расходятся, и на этой позиции стоят разные цифры. И ни одна запись не пропущена: какую бы последовательность единиц и двоек мы ни задумали, на каждом шаге нужная ветвь есть. Поэтому на последнем уровне совпадают три количества: листьев, путей и записей.

Сколько листьев на шестом уровне. Первым уровнем считаем сами корни, они задают первую цифру. На нём в двух деревьях вместе два листа. Для следующей цифры из каждого листа вырастают два новых, поэтому на каждом шаге их число удваивается.

Цифр в записи	Листьев в двух деревьях вместе
1	2
2	$2 \cdot 2 = 2^2 = 4$
3	$2 \cdot 2 \cdot 2 = 2^3 = 8$
4	$2^4 = 16$
5	$2^5 = 32$
6	$2^6 = 64$

Показатель 6 означает, что перемножены шесть двоек: по два выбора на каждую из шести позиций. Это правило умножения. Рисовать все 64 листа не нужно, правило роста уже установлено.

Вычитаем исключения. Все 64 записи — действительно шестизначные числа: ни 1, ни 2 не равны нулю, поэтому первая цифра нулём быть не может. Две записи условию не отвечают:

$64 - 2 = 62.$

Ответ: 62 числа.

Проверим границы. Случаи «нет единицы» и «нет двойки» не пересекаются: записи, где не встречается ни одна из двух разрешённых цифр, не существует. Значит, каждое из двух исключений вычтено ровно один раз, а любое другое число учтено ровно один раз.

Что и требовалось — понять

Считать только записи с тремя единицами и тремя двойками, то есть требовать поровну. Условие говорит «каждая встречается», а это значит «хотя бы одна». Число 111112 подходит, но при таком подсчёте теряется.

Исправление: разрешить любые количества обеих цифр и убрать только две записи из одинаковых цифр.

Дерево вариантов помогает, когда объект строится по шагам: цифра за цифрой, ход за ходом. Оно организует перебор и показывает, что ничего не пропущено.

Подсчёт через дополнение выручает, когда все варианты посчитать проще, чем подходящие, а нарушения условия можно перечислить. Здесь их всего два.

Только не переносите ответ $2^n - 2$ на любую задачу про две цифры. Он верен для записей длины $n$ из двух различных ненулевых цифр, когда нужны обе. Если среди цифр есть ноль, первую позицию придётся разбирать отдельно. А если одно исключение попадает сразу в несколько групп, вычитать его несколько раз нельзя.

Попробуйте сами

Авторская задача на тот же приём, не олимпиадная. Сколько четырёхзначных чисел можно составить только из цифр 3 и 7, если каждая из них должна встретиться?

Подсказка

На каждой из четырёх позиций два выбора. Какие записи не содержат обеих цифр?

Показать ответ

Всего записей $2^4 = 16$ . Не подходят 3333 и 7777, поэтому ответ $16 - 2 = 14$ .

Проверка перечислением: 3337, 3373, 3377, 3733, 3737, 3773, 3777, 7333, 7337, 7373, 7377, 7733, 7737, 7773. Все числа различны, в каждом есть обе цифры.

Следующий шаг

Ещё одна задача, где считать всё подряд не нужно: высота стола и сложение трёх равенств. Там лишние неизвестные исчезают при сложении.