В доску вбито 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, можно разрезать, чтобы сетка не распалась на отдельные куски?