Лекции и упражнения
жүктеу/скачать 1,95 Mb. Pdf көрінісі
|
Matan Lectures 2013
ГЛАВА 1. ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ. которые есть и у Юры, и у Лјши. Точно так же, число Лјшиных марок, которых нет у Миши, меньше, чем число марок, которые есть и у Лјши и у Миши. А число Мишиных марок, которых нет у Юры, меньше, чем число марок, которые есть и у Юры и у Миши. Докажите, что какая-то марка есть у каждого из трех мальчиков. Упражнение 30. * Докажите, что если какое-то равенство, содержащее переменные для множеств и операции ? , ? , \ , неверно, то можно найти контрпример к нему, в котором множества пусты или содержат по одно- му элементу. Упражнение 31. * а) Сколько различных выражений для множеств A и B можно составить из переменных и с помощью операций ? , ? , \ ? Два выражения считаются одинаковыми, если они верны при всех значениях переменных; б) тот же вопрос для трех множеств A, B и C ; в) тот же вопрос для n множеств A 1 , . . . , A n . Упражнение 32. ** а) Сколько различных выражений для множеств A и B можно составить из переменных и с помощью операций ? , ? ? Два вы- ражения считаются одинаковыми, если они верны при всех значениях пе- ременных; б) тот же вопрос для трех множеств A, B и C . Замечание: Эта задача (немного в другой формулировке) называется ѕпроблема Дедекин- даї. До сих пор не известен точный ответ для случая > 9 множеств. Ответы и указания 1) Философов. 2) 3. 3) 25. 4) Да, верно. 5) 3. 6) 8. 7) 26. 8) 10. 9) 10. 10) а) III список. b) Могут совпасть I и II, II и III, I и III или III и IV. 11) 8. 12) 24 в обоих пунктах. 13) Управдом врет, т.к. 25 + 30 + 28 ? 18 ? 17 ? ? 16 + 15 = 47 > 45 . 14) 811 + 752 + 418 ? 570 ? 356 ? 348 + 297 = 1004 > > 1000 . 15) Трудных задач на 20 больше, чем легких. 16) Могло. 17) Доля голубоглазых среди блондинов. 18) Не могло. 19) a) 100. b) 60. c) 20. d) 160. 20) 1600. 21) Пусть A множество точных квадратов, B кубов, M всех чисел от 1 до 1000000. Тогда | A ? B | = 1000 + 100 ? 10 = 1090 и | M \ ( A ? B ) | = 998910 . 22) Использовать формулу включений-исключений. 23) 7 3 ? 3 · 7 2 + 3 · 7 ? 1 = 216 . 24) См. решение примера 4. 25) 10%. 26) 356. 27) Рассмотреть индикаторные функции. 28) Если n кратно p , то n · (1 ? 1 p ) чисел, меньших n , не кратны p . 29) Использовать формулу включений- исключений. 30) Рассмотреть элемент, на котором нарушается тождество и отбросить все остальные. 31) a) 4. b) 8. c) 2 n . 32) a) 4. b) 18. |