Kat&Pop - Рефераты - Программа ВМШ - семестр 3, занятие 8.

1. Том Сойер красит забор у тетушки Полли, состоящий из 2000 досок. Причем некоторые доски Том может забыть покрасить… Сколькими способами изобретательный маляр может окрасить этот забор?
2. Сколькими способами можно выбрать из n школьников k для участия в олимпиаде? А сколькими способами можно выбрать из этих же n школьников n – k школьников, в этой олимпиаде не участвующих?
3. а) У Вовочки n одноклассников. Для хорошего дела требуется набрать команду из k человек так, чтобы Вовочка в нее не попал. Сколькими способами это можно сделать?

б) А для плохого дела нужна компания из m человек, в которой Вовочка будет атаманом. Сколькими способами можно собрать такую банду (в классе, кроме Вовочки, по-прежнему n человек)?

4. Доказать следующие свойства сочетаний: а) ; б) .

Комментарий: второе свойство позволяет легко вычислить числа для всех k, если мы знаем все числа для некоторого фиксированного m.

Комментарий для преподавателей: здесь необходимо объяснить построение треугольника Паскаля, посчитать с его помощью несколько чисел сочетаний.

5. Даны 5 разноцветных шариков. Сколько существует различных способов разделить эти шарики между Петей и Васей (любому из них может достаться и ноль шариков)?

Комментарий для преподавателей: укажите на то, что задачи №1 и №6 не отличаются и намекните, что сумма чисел в каждой строке вроде равна 2ⁿ.

6. Докажите, что .
7. На рисунке 1 дан план города Энска. На всех улицах введено одностороннее движение: можно ехать только "вправо" или "вверх". Сколько есть разных маршрутов, ведущих от дома Виктора к дому Рустама?
   
8. Хромой король ходит по клетчатой доске на 1 клетку вправо или на 1 клетку вверх. Занумеруем столбцы слева направо, а строки снизу вверх числами 0, 1, 2, 3… Обозначим клетку (m, n), если она находится на пересечении m-го столбца и n-ной строки. Докажите, что количество путей, ведущих из клетки (0, 0) в клетку (m, n), равно .
9. Докажите, что из n семиклассников можно выбрать четное число школьников 2^n–1 способами.
10. Докажите, что .

Комментарий: Диагоналями в треугольнике Паскаля будем называть лучи, параллельные сторонам треугольника. Причем диагонали, параллельные правой стороне, будем называть правыми, а левой – левыми.

11. Докажите, что каждое число А в треугольнике Паскаля равно

а) сумме чисел предыдущей правой диагонали, начиная с самого левого вплоть до стоящего справа над числом А (рис.2);

б) сумме чисел предыдущей левой диагонали, начиная с самого правого вплоть до стоящего слева над числом А (рис.3).



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


13. Докажите, что

1. Парламент состоит из двух одинаковых палат. В голосовании участвовали все депутаты, воздержавшихся не было. Когда объявили, что решение принято с перевесом в 23 голоса, то аппозиция заявила о фальсификации результатов. Справедливы ли их претензии?
2. В квадрате 7х7 на клетке a2 сидит гусеница. Она переползает из одной клетки в другую только по границе. Сможет ли она попасть в центр квадрата, побывав в каждой клетке по одному разу?
3. Город Дивград расположен на 7 островах. Для улучшения сообщения между ними президент города приказал министрам построить мосты между островами так, чтобы из каждого острова выходило по три моста. Смогут ли министры выполнить этот приказ?
4. Гастроном продал в первый день 1/2 всех гусей и еще пол гуся, во второй 1/3 остатка и еще одну треть гуся, на третий-1/4 нового остатка и еще 3/4 гуся, на четвертый – 1/5 остатка и еще одну пятую гуся. На пятый день в гастрономе осталось 19 гусей. Сколько их было первоначально?
5. После представления “Ревизора” состоялся следующий диалог:

Кто первый сказал “Э!”, если из девяти произнесенных фраз-утверждений четное число верных?

1. Вспомнить материал, который мы проходили в первом семестре и доказать теорему о деревьях (ее проходят в университете на третьем курсе): (50 баллов)