"Информатика", Рудченко Т.А., Семёнов А.Л. / Под ред. Семёнова А.Л.
Правило раскрашивания помогает считать, сколько способов назначить цвета нескольким различимым объектам. Если каждый из n объектов независимо можно выбрать один из k цветов, число раскрасок равно kⁿ: варианты для каждого объекта перемножаются. Правило работает и тогда, когда наборы цветов для объектов различаются, но при ограничениях, например запрете одинаковых цветов у соседей, подсчёт нужно изменять.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Раскраска — способ назначить каждому различимому объекту один цвет. Объектами могут быть клетки, карточки или детали, а цвет выбирают из заранее заданного набора. Это понятие нужно, чтобы точно описать каждый получившийся вариант.
Правило раскрашивания: если каждый из n объектов можно независимо покрасить в один из k цветов, всего получится kn раскрасок. Буква n показывает количество объектов, а k — количество доступных цветов для каждого из них. Правило позволяет быстро считать большие наборы вариантов, не выписывая их по одному.
Число раскрасок — количество различных способов назначить цвета всем объектам. Два способа считаются разными, если хотя бы у одного объекта цвет другой. Такое определение помогает не путать одинаковые наборы цветов с одинаковыми назначениями цветов объектам.
Объекты должны быть различимыми, потому что цвет закрепляется не просто за набором предметов, а за каждым предметом отдельно. Например, раскраска «первая карточка красная, вторая синяя» отличается от раскраски «первая карточка синяя, вторая красная». Перестановка цветов меняет назначение, поэтому обычно создаёт новый способ.
Формулу объясняет правило умножения. Для первого объекта можно сделать k выборов, и после каждого такого выбора для второго объекта снова остаётся k вариантов. Продолжая так для всех n объектов, получаем произведение k · k · … · k, то есть kn.
Независимость означает, что выбор цвета одного объекта не сужает набор цветов для другого. Если клетку уже покрасили в красный, следующую всё равно можно покрасить в любой из k цветов. Когда условие запрещает некоторые сочетания, выборы становятся связанными и формулу kn нельзя подставлять без проверки.
Чтобы составить задачу на правило раскрашивания, сначала назовите все объекты и убедитесь, что их можно различить. Затем укажите доступные цвета для каждого объекта и выясните, разрешено ли использовать цвет повторно. Наконец, проверьте, не существуют ли запреты на сочетания цветов, например требование красить соседние объекты по-разному.
Если наборы цветов для объектов неодинаковы, одинаковое число k для всех объектов использовать нельзя. Для первого объекта будет k₁ вариантов, для второго k₂ и так далее. Поэтому общее число способов равно произведению k₁ · k₂ · … · kₙ, если эти выборы также независимы.
| Условие | Число раскрасок |
|---|---|
| n объектов, каждому доступны k цветов | kn |
| n объектов, каждому доступны свои количества цветов k₁, k₂, …, kₙ | k₁ · k₂ · … · kₙ |
Сначала определите, к какой строке относится условие задачи. Если число цветов одинаково, удобно использовать степень; если различается, перемножьте отдельные количества вариантов. Таблица применима только при независимом выборе и разрешённых повторениях цветов.
Задача 1. Каждую из 3 различимых карточек можно покрасить в красный или синий цвет. Нужно найти количество всех раскрасок. Цвет одной карточки не влияет на выбор цвета другой.
Ответ: 8 раскрасок. Например, красная первая карточка и синяя вторая — это не то же самое, что синяя первая и красная вторая.
Задача 2. Четыре клетки в ряд независимо красят в один из 3 цветов. Положение клетки определяет, какая именно это клетка, поэтому все четыре объекта различимы. Ограничений на повторение цветов нет.
Ответ: 81 раскраска. Здесь степень показывает четыре одинаковых по числу вариантов выбора, по одному для каждой клетки.
Задача 3. Три различные детали имеют неодинаковые наборы цветов: первой доступны 2 цвета, второй — 3, третьей — 4. Выборы независимы, но применять одну степень нельзя, поскольку количества вариантов различаются. Поэтому используем общее правило умножения.
Ответ: 24 способа раскраски. Возможность использовать одинаковый цвет у разных деталей не меняет подсчёт, если запрета на это нет.
Ошибка — считать раскраски с переставленными цветами одинаковыми. Её допускают, когда смотрят только на набор цветов и забывают о положении объектов. Проверьте себя: если после обмена цветов хотя бы один объект получил другой цвет, способы различаются.
Ошибка — складывать числа вариантов вместо перемножения. Сложение описывало бы выбор одного варианта из отдельных случаев, а здесь нужно одновременно выбрать цвета для всех объектов. Проверьте решение, записав выбор по шагам: для каждого уже выбранного варианта должны появляться новые варианты следующего объекта.
Ошибка — применять kn, не проверив независимость выборов. Так бывает, когда не замечают запрет на одинаковые цвета или условие о соседних объектах. Перед формулой выпишите, влияет ли цвет одного объекта на доступные цвета другого.
Ошибка — забывать, что цвет можно использовать несколько раз. Иногда ученик считает, будто после выбора цвета он исчезает из набора, хотя такого запрета нет. Сверьте решение с условием: если повторение разрешено, число вариантов для каждого независимого объекта остаётся прежним.
До правила раскрашивания нужно уметь различать объекты и применять правило умножения при последовательном выборе. Эти умения показывают, какие варианты считать разными и почему отдельные количества перемножаются. Без них легко перепутать назначение цветов с выбором одного общего набора.
Правило раскрашивания пригодится при подсчёте наборов признаков, кодов и вариантов назначений. В таких задачах цвет заменяется символом, свойством или значением, но способ подсчёта остаётся тем же. Позже это правило помогает организовывать перебор вариантов и проверять его полноту.
Почему число раскрасок считают умножением, а не сложением?
Раскраска состоит из последовательного выбора цвета для каждого объекта. Если для первого объекта есть k вариантов и для каждого следующего столько же, число полных комбинаций равно произведению k · k · … · k, а не сумме.
Чем раскраски различимых объектов отличаются друг от друга?
Различимые объекты можно узнать или отличить по их положению, номеру или виду. Если цвет хотя бы одного такого объекта изменился, получилась другая раскраска, даже когда остальные цвета остались прежними.
Можно ли красить несколько объектов в один цвет?
Да, если условие задачи не запрещает повторение цветов. Тогда для каждого объекта сохраняется одно и то же число вариантов, и можно применять формулу kⁿ при независимом выборе.
Что делать, если для разных объектов доступны разные цвета?
Для каждого объекта нужно определить своё число вариантов. Затем эти числа перемножают: k₁ · k₂ · … · kₙ.
Можно ли применять правило раскрашивания, если цвета соседних объектов должны отличаться?
Нельзя сразу использовать формулу kⁿ, потому что выбор цвета одного объекта ограничивает выбор для соседнего. Нужно учитывать ограничение на каждом шаге или перечислять только допустимые сочетания.
Правило раскрашивания
