Контрольные работы

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

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

18 Покажите, что следующая совокупность ломаных линий делит плоскость на областей, где определено в (1.7): каждая ломаная при имеет излом в точке и проходит через точки

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

20 Примените репертуарный метод решения обобщенной рекуррентности с пятью параметрами

при Указание: попробуйте функции

21 Допустим, что в круг поставлено человек, первые из которых — „славные ребята", а последних — „гадкие парни“. Покажите, что всегда найдется целое (зависящее от такое, что если, двигаясь по кругу, мы наказываем каждого то первыми будут наказаны все гадкие парни. (К примеру, при можно взять , а при взять )

Конкурсные задачи

22 Покажите, что используя выпуклых многоугольников, которые конгруэнтны друг другу и повернуты относительно общего центра, можно построить диаграмму Венна для всевозможных подмножеств заданных множеств.

23 Допустим, что Иосиф занимает конкретное место, но при этом имеет возможность назвать роковой параметр после чего уничтожается каждый человек. Всегда ли он сможет спастись?

Исследовательские проблемы

24 Найдите все рекуррентные соотношения вида

решения которых периодичны.

25 Решите задачу о ханойской башне с четырьмя колышками и в бесконечном числе случаев, доказав, что в соотношении из упр. 17 имеет место равенство.

26 Обобщая упр. 23, будем называть иосифовым подмножеством множества такое множество из к номеров, что при некотором первыми будут уничтожены люди с остальными — к номерами. (На этих к местах находятся „славные ребята" которых хочет спасти Иосиф.) Оказывается, что при три из 29 возможных подмножеств являются неиосифовыми, а именно, подмножества Когда то 13 подмножеств являются неиосифовыми, а при любом другом нет ни одного неиосифова. Редки ли неиосифовы подмножества при больших