МАЛЫЙ МЕХМАТ МГУ

В доску вбито 20 гвоздиков. Расстояние между соседними равно 1 см. Натяните нитку длиной 19 см от A до B так, чтобы она прошла через все гвоздики.

Ответ

Ответ.

Сколько было бревен, если пятьюдесятью двум распилами из них получили 72 полена?

Решение

Решение. Поскольку после каждого распила число бревен увеличивается на 1, было 72 - 52 = 20 бревен.

а) Имеется лист бумаги. Его можно разорвать на 5 частей. Каждый новый кусок можно разорвать на 5 частей или оставить целым, и так далее. Можно ли получить таким образом 50 кусков?
б) Если всякий раз лист можно рвать на 8 или на 12 частей, выясните, можно ли из одного листа получить 60 кусков; докажите, что любое число кусков, большее 60, получить можно.
 

N точек соединены непересекающимися отрезками так, что из каждой можно пройти в каждую из остальных по отрезкам, причем единственным путем. Сколько отрезков?

Ответ   Решение

Ответ. N - 1.

Решение. Назовем одну из точек корнем. Сопоставим каждой из остальных вершин последний отрезок (единственного по условию) пути, ведущего в эту точку из корня. Это соответствие между N - 1 вершинами и отрезками взаимно-однозначное. Чтобы сделать это очевидным, удобно расставить на отрезках стрелки, ведущие от корня: в каждую точку, кроме вершины, ведет одна стрелка. Задачу можно решить также по индукции: удаляя любой лист (лист - это вершина, из которой исходит единственное ребро) дерева, мы одновременно удаляем одно ребро. Для Придиры. Чтобы доказать, что деревьев без листьев не бывает, рассмотрим граф, в котором из каждой вершины исходит не менее двух ребер. Из некоторой его вершины A1 пройдем по ребру в некоторую вершину A2. Из A2 выходит более одного ребра, поэтому можно пройти в вершину A3, отличную от A1, из нее - в A4, ... . Поскольку число вершин графа конечно, рано или поздно образуется цикл.

На столе лежат две кучки: в одной 7 спичек, а в другой 8. Начинающий делит кучку на две кучки, затем второй делит одну из кучек на две, и так далее. Проигрывает тот, кто не сможет сделать очередного хода. Зависит ли результат этой игры от того, кто как играет, или важно лишь, кто ходит первым?

Ответ   Решение

Ответ. Не зависит.

Решение. В начале количество кучек равно 2. Каждый ход увеличивает количество кучек на 1. Поэтому для получения 7 + 8 кучек (каждая из которых состоит из 1 спички) нужно 15 - 2 = 13 ходов.

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

Ответ   Указание

Ответ. 63 спички.

Указание. Если прочертим все пути, которыми может ходить ладья, то (при условии, что не снимали лишних спичек) получим дерево (дерево - это связный граф без циклов, то есть граф, в котором от любой вершины можно дойти, двигаясь по ребрам, до любой другой вершины, причем единственным способом, если ни разу не возвращаться назад). А по задаче 248 число ребер у дерева на 1 меньше числа его вершин.

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

Ответ   Решение

Ответ. Начинающий.

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

Какое наибольшее число веревочек, соединяющих соседние узлы сетки размера 4×6, можно разрезать, чтобы сетка не распалась на отдельные куски?