Решение задач «Индукция»,
Тематика в Новосибирске

  Занятие 27. Математическая индукция 27.1. Докажите, что любое натуральное число можно представить в виде суммы степеней двойки. 27.2. Докажите, что любую сумму из целого числа рублей, большего семи, можно уплатить без сдачи денежными купюрами в 3 и 5 руб.   27.3. Листок бумаги можно рвать на 4 части или на 6 частей. На какое количество частей его можно порвать? 27.4. На сколько квадратов можно разрезать квадрат? 27.5. На какое число равносторонних треугольников можно разрезать равносторонний треугольник? 27.6. Докажите, что число подмножеств с числом элементов конечного множества равно . 27.7. Несколько человек хотят разделить пирог, но при этом они не доверяют друг другу. Докажите, что они могут разделить его так, чтобы все остались довольны. 27.8. В разных местах кольцевой дороги стоят несколько одинаковых автомашин. Если бы весь бензин, имеющийся в этих автомашинах слить в одну, то эта автомашина смогла бы проехать круг по всей кольцевой дороге.  Докажите, что по крайней мере одна из машин может проехать полный круг, забирая по пути бензин у остальных машин. 27.9. При каком количестве участников в турнире без ничьих возможна ситуация, когда участники набрали одинаковое количество очков? 27.10. Докажите, что по окончании кругового турнира его участников можно перенумеровать так, чтобы ни один из участников не проиграл непосредственно следующему за ним. 27.11. В некотором царстве любые два города соединены каналом или шоссе. Докажите, что из любого города в любой можно доплыть на лодке или приехать в автомобиле. 27.12. Несколько прямых  делят  плоскость  на  части.  Докажите, что эти части всегда можно раскрасить в шахматном порядке так, чтобы части, имеющие общую границу были окрашены в разные цвета. 27.13. Из квадрата 1024´1024, нарисованного на клетчатой бумаге, вырезали одну клетку. Всегда ли можно разрезать его на уголки из трёх клеток? 27.14. Несколько прямых  делят  плоскость  на  части.  Каждая  прямая заштрихована с одной стороны. Докажите, что все границы  одной  из частей заштрихованы изнутри. 27.15. Докажите, что число (3n единиц) кратно 3n. 27.16. На острове все страны треугольной формы (границы прямые). Если две страны граничат, то по целой стороне. Докажите, что страны можно раскрасить в 3 цвета так, что соседние по стороне страны будут покрашены в разные цвета. 27.17. В гостиницу приехал путешественник. Денег он не имел, а обладал лишь серебряной цепочкой, состоящей из n звеньев. За каждый день пребывания в гостинице он расплачивался одним звеном цепочки, при этом хозяин предупредил, что согласен взять не более одного распиленного звена. Как путешественнику распилить цепочку, чтобы иметь возможность ежедневно расплачиваться с хозяином? 27.18. Двум математикам сообщили по натуральному числу и сказали, что разность этих чисел равна 1. После этого они по очереди задают друг вопрос: «Знаешь ли ты моё число?». Докажите, что рано или поздно кто-то из них ответит утвердительно.