Тема:
Все темы
>>
Логика и теория множеств
>>
Теория множеств
>>
Мощность множества. Взаимно-однозначные отображения
Фильтр
Задачи
Задача 98241 |
|
|
Полоска 1×10 разбита на единичные квадраты. В квадраты записывают числа 1, 2, ..., 10. Сначала в один какой-нибудь квадрат записывают число 1, затем число 2 записывают в один из соседних квадратов, затем число 3 – в один из соседних с уже занятыми и т. д. (произвольными являются выбор первого квадрата и выбор соседа на каждом шагу). Сколькими способами это можно проделать?
Решение
Очевидно числа слева от 1 стоят в убывающем порядке, а справа – в возрастающем. Поэтому строка однозначно определяется выбором подмножества чисел, которые будут стоять левее единицы. Таких подмножеств в множестве {2, ..., 10} из 9 элементов, как известно, 29.
Ответ
512 способами.
|
|
Задача 64855 |
|
|
Петя подсчитал количество всех возможных m-буквенных слов, в записи которых могут использоваться только четыре буквы T, O, W и N, причём в каждом слове букв T и O поровну. Вася подсчитал количество всех возможных 2m-буквенных слов, в записи которых могут использоваться только две буквы T и O, и в каждом слове этих букв поровну. У кого слов получилось больше? (Слово – это любая последовательность букв.)
Решение
Установим взаимно-однозначное соответствие между словами Пети и Васи.
Разобьём Васино слово из 2m букв на блоки из двух букв. Заменим каждый блок TT на букву T, блок OO – на букву O, блок TO – на букву W, и блок OT – на букву N. Получится слово из m букв, в котором букв T и O поровну (изначально их было поровну, замена блоков TO и OT убирает равное число букв T и O, а значит, и блоков TT будет столько же, сколько блоков OO). Итак, каждому слову Васи мы сопоставили слово Пети.
Наоборот, по каждому m-буквенному слову Пети легко восстановить, из какого слова Васи оно получилось: надо заменить буквы по правилу
T → TT, O → OO, W → TO, N → OT.
Ответ
Слов получилось поровну.
|
|
|
Задача 73735 |
|
|
а) На рисунке слева изображены шесть точек, которые лежат по три на четырёх прямых. Докажите, что можно 24 разными способами отобразить это множество из шести точек на себя так, чтобы каждые три точки, лежащие на одной прямой, отобразились в три точки, лежащие на одной прямой.
б) На рисунке справа девять точек лежат по три на девяти прямых, причём через каждую точку проходит по три таких прямых. Эти девять точек и девять прямых образуют знаменитую конфигурацию Паскаля. Сколькими способами можно множество наших девяти точек отобразить на себя так, чтобы каждая тройка точек, лежащая на одной из девяти наших прямых, отобразилась на тройку точек, которая тоже лежит на некоторой прямой из нашей конфигурации?
в) Тот же вопрос для конфигурации Дезарга (из десяти точек и десяти прямых), изображённой на нижнем рисунке.
Решение
а) Если для каждой из наших четырёх прямых будет указано, на какую прямую она отображается, то тем самым определится и образ каждой точки (каждая точка нашей конфигурации является точкой пересечения определенных двух входящих в конфигурацию прямых). Множество из четырёх прямых можно отобразить на себя 4! = 24 способами.
б) Отметим одну из прямых конфигурации l. Обозначим три лежащие на ней точки конфигурации A, B и C. Через эти точки проходят еще шесть прямых конфигурации. Остаются еще две прямые p и q, которые не проходят ни через одну из точек A, B и C.
Отобразим прямую l на какую-либо из девяти прямых конфигурации – на прямую l1. Выбрать её можно девятью способами. Точки A, B и C придётся отобразить на точки A1, B1 и C1, лежащие на прямой l1. Это можно сделать шестью способами. Прямые p и q должны отобразиться на две прямые p1 и q1, не проходящие через точки A1, B1, C1. Это можно сделать двумя способами. После этого образы остальных точек и прямых конфигурации будут однозначно определены.
Всего, таким образом, получится 9·6·2 = 108 отображений.
в) Выберем одну из десяти прямых l. На ней расположены три точки A, B, C. Отличные от l прямые конфигурации, проходящие через точки A и B, пересекаются попарно еще в двух точках конфигурации X и Y. Отображение конфигурации на себя полностью определится, если задать образ l1 прямой l, образы A1, B1, C1 точек A, B, C, лежащие на прямой l1 и образы X1 и Y1 точек X и Y, которые должны быть точками попарного пересечения отличных от l1 прямых конфигурации, проходящих через точки A1 и B1. Всего получается 10·6·2 = 120 интересующих нас отображений.
Ответ
б) 108; в) 120 способами.
|
|
|
Задача 116142 |
|
|
В стаде, состоящем из лошадей, двугорбых и одногорбых верблюдов, в общей сложности 200 горбов.
Сколько животных в стаде, если количество лошадей равно количеству двугорбых верблюдов? .
Решение
Пусть каждый двугорбый верблюд “поделится” горбом с лошадью. Тогда у каждого животного будет по одному горбу, следовательно, количество горбов равно количеству животных в стаде.
Ответ
200.
|
|
|
Задача 103809 |
|
|
Сколькими способами можно прочитать в таблице слово
а) КРОНА,
б) КОРЕНЬ,
начиная с буквы "K" и двигаясь вправо или вниз?
Подсказка
Запишите каждый путь последовательностью нулей и единиц.
Решение
а) См. задачу 35547.
б) Если читать слово с конца, мы получим задачу, аналогичную а).
Ответ
а) 16; б) 32 способами.
|
|
|
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 38]
