Перестановки диагоналей

У куба четыре большие диагонали. Сколько разных перестановок этих четырёх отрезков осуществляют все вращения куба?

Подсчёт деревьев

Соедините n точек 1, 2, 3, …, n отрезками так, чтобы получилось дерево (т.е. граф, в котором есть путь из любой вершины в любую, но нет циклов – замкнутых путей; отрезков должно быть n -1). Сколько разных деревьев можно получить?

Ломаные

Задача состоит в том, чтобы описать все замкнутые ломаные, пересекающие каждое свое звено ровно один раз и имеющие заданное число звеньев. Например, для 6 звеньев существует ровно одна такая ломаная.

Темы по комбинаторике см. также в [Ст 8, 11, 12].

АЛГОРИТМЫ

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

Монетки

Имеется несколько настоящих монет – все одного веса, и одна фальшивая – она легче. Какое наименьшее число взвешиваний на чашечных весах понадобится, чтобы определить фальшивую монету? Как надо взвешивать? Сначала решите задачу для 3, 9, 27 монет. Та же задача, если фальшивая монета отличается по весу от настоящих, но неизвестно, в какую сторону.

Игра в полоску

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

Не больше половины

Дана кучка камней. Играющие (их двое) по очереди берут камни, причём игрок не может пропускать ход (не брать камни), и может взять не больше половины камней. Проигрывает тот, кто не может сделать ход.

Ладья – ферзь

1. Ладья. Двое играют в следующую игру: на поле, ограниченном снизу и слева, они двигают ладью по очереди вниз или влево. Выигрывает тот, кто ставит ладью в угол доски (клетка 1,1). Требуется найти правильную стратегию игры и определить, кто будет выигрывать, начиная с данной точки поля.

2. Ферзь. Двое играют в следующую игру: на поле, ограниченном снизу и слева, они двигают ферзя вниз, влево или по диагонали вниз и влево. Выигрывает тот, кто ставит ферзя в угол доски (клетка 1,1). Требуется найти правильную стратегию игры и определить, кто будет выигрывать, начиная с данной точки поля.

Угадайка

Один из игроков загадал число, меньшее 100. Другой задает ему вопросы, на которые первый может отвечать только «да» или «нет». Как правильно задавать вопросы, чтобы как можно быстрее отгадать число?

Угадайка с враньём. Тот же вопрос, если отвечающий может соврать один раз.

Угадайка с платой. За каждый ответ «да» спрашивающий платит 1 рубль, за каждый ответ «нет» – 2 рубля. Как правильно задавать вопросы, чтобы отгадать число, заплатив как можно меньшую сумму?

Эволюция клеток

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

Мудрецы у людоедов

Мудрецы попали в плен к людоедам. У людоедов есть такой обычай. Пойманных пленников выстраивают в колонну и надевают им на головы колпаки – кому белый, кому черный – наугад. Каждый пленник видит, какого цвета колпаки у всех, кто стоит перед ним, но не знает, какой колпак у него самого и у всех, кто стоит за ним. Каждый пленник, начиная с последнего, должен сказать, какого цвета у него колпак (остальные слышат его ответ). Тех, кто ответил правильно, – отпускают. Остальных – съедают. Мудрецы знают про обычай и могут между собой договориться. Как мудрецам спасти побольше человек? Какое наибольшее число человек можно спасти в самом худшем случае?

Сумма кубов цифр

С десятичной записью натурального числа проделывают следующую операцию: находят

сумму кубов его цифр, для полученного числа снова находят сумму кубов его цифр и т.д.

Какие последовательности чисел могут получаться?

Задача Иосифа Флавия

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

Обезьяна и кокосы

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

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

Игра Ним

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