Вводя ограничения при поиске примера, помни о них. Если «там, где легко» примера нет, надо будет расширять круг поиска, постепенно отказываясь от ограничений. Трудно, однако, отказаться от того, чего не замечаешь. Это и есть инерция мышления: создание для себя невидимых барьеров.

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

Зацепкой к решению служит та часть конструкции, где свобода выбора – наименьшая. Такие места служат препятствиями к построению конструкции, или кажутся таковыми. Именно их мы и назовем узкими местами.

Пространство вариантов

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

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

Кодировка устанавливается взаимно-однозначное соответствие между объектами (состояниями) из задачи и комбинаторными комбинациями (сочетаниями, размещениями, перестановками). Например, соответствие последовательностям из 0 и 1 называют двоичной кодировкой.

Идеи найдены и применены, круг поиска очерчен, но варианты все ещё остаются. Перебирать надо эффективно, то есть не пропустить случай, но и не утонуть в случаях. Перебор зависит от цели. В задачах с вопросами «Как можно…» или «Может ли …» и «Существует ли…» (с ответом «Да») достаточно найти одно решение. Тогда перебор надо начинать с удобных случаев.

Метод получения простой конструкции может стать вспомогательным средством («строительными лесами»). Конструкция из упрощенной задачи послужит подсказкой к конструкции сложной задачи. Грубо говоря, прежде чем строить большой дом, полезно размяться: потренироваться на строительстве сараев и хижин.

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

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

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

В графе без циклов есть равенство Р=В–С (где Р – рёбра, В – вершины, С – компонеты связности). В произвольном графе это превращается в неравенство Р≥В–С. Увидев подходящий граф, можно доказать или использовать соответствующие равенства и неравенства.

Набор позиций (состояний) и переходы между ними можно рассматривать как граф. Если с каждой позицией можно связать некоторую величину, не меняющуюся при переходах, это – инвариант. Типичные инварианты: четность, общий делитель, сумма.
Значения инварианта разбивают граф на компоненты связности, и так доказывают, что нет маршрута между позициями с разными значениями инварианта. Но можно доказать и существование: если добраться таки удалось, то был шаг со сменой значения.

В задачах на пример+оценку пример и оценка – обычно две отдельные части решения; смешивать их не стоит. В комбинаторных задачах оценка часто получают, выделив подсчитав узкие места. Эти места помогают и пример построить. В задачах на оценку+алгоритм часто строят пример именно при доказательстве оценки.

Граф связен, если между любыми двумя его вершинами есть путь по ребрам (как по дорогам). Любой граф можно разбить на связные куски-компоненты. Если в графе всего две вершины нечетной степени, между ними есть путь по рёбрам.

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

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

Сколько элементов во множестве можно найти, установив его соответствие с другим множеством, которое пересчитать легче. Можно устанавливать соответствие не всего множества, а его частей, и считать с помощью сложения, вычитания, формулы включения-исключения...

Билеты заключительного зачёта.

Билеты заключительного зачёта.