Тема:
Все темы
>>
Логика и теория множеств
>>
Теория множеств
>>
Объединение, пересечение и разность множеств
Фильтр
Выбрана 1 задача Убрать все задачи
Тождество Кассини. Докажите равенство
Будет ли тождество Кассини справедливо для всех целых n?
Задачи
Задача 79512 |
|
|
В классе организуется турнир по перетягиванию каната. В турнире ровно по одному разу должны участвовать всевозможные команды, которые можно составить из учащихся этого класса (кроме команды всего класса). Доказать, что каждая команда учащихся будет соревноваться с командой всех остальных учащихся класса.
Решение
Назовём две команды дополнительными, если одна из них состоит из всех учеников, не вошедших в другую. Каждый ученик класса входит только в одну из двух дополнительных команд, следовательно, он входит ровно в половину всех команд. Но половина числа всех команд равна числу всех предстоящих соревнований. Таким образом, число соревнований совпадает с числом выступлений каждого ученика, а значит, в каждом соревновании будут выступать все ученики, то есть две дополнительные команды.
|
|
Задача 109595 |
|
В классе 16 учеников. Каждый месяц учитель делит класс на две группы.
Какое наименьшее количество месяцев должно пройти, чтобы каждые два ученика в какой-то из месяцев оказались в разных группах?
Решение
Пример. На рисунке показано, как нужно разбивать класс на две группы так, чтобы каждые два ученика в какой-то из четырёх месяцев оказались в разных группах. Каждому ученику соответствует столбец таблицы, а каждому месяцу – её строка. Нуль, стоящий в клетке таблицы, означает, что данный ученик входит в первую группу, а единица означает, что данный ученик входит во вторую группу. Поскольку совпадающих столбцов нет, каждые два ученика хотя бы одни месяц из четырёх находятся в разных группах.
Оценка. Докажем, что за три месяца выполнить условие нельзя. Составим аналогичную таблицу 3×16. В столбце можно расставить нули и единицы только 8 способами, поэтому найдутся два одинаковых столбца. Соответствующие этим столбцам ученики все три месяца попадают в одну группу.
Ответ
4 месяца.
|
|
|
Задача 117008 |
|
|
Каждый из учеников класса занимается не более чем в двух кружках, причём для любой пары учеников существует кружок, в котором они занимаются вместе. Докажите, что найдётся кружок, в котором занимается не менее ⅔ всего класса.
Решение
Если в некоторый кружок ходит весь класс, то всё в порядке. Далее мы считаем, что такого кружка нет.
Пусть самый многочисленный кружок – математический; его участников мы будем называть математиками. Есть ученик Вася, который в него не ходит. Рассмотрим его и одного из математиков. Они вместе ходят в другой кружок, допустим, в фото. Вася не может ходить в этот кружок вместе со всеми математиками, иначе математический кружок не будет самым многочисленным. Значит, с кем-то из математиков он ходит ещё в один кружок, например, в танцевальный.
Итак, каждый математик ещё является либо фотографом, либо танцором (и никем другим).
То, что было выше сказано про Васю, можно сказать и про любого ученика, который не является математиком: каждый из таких учеников – фотограф и танцор одновременно (и больше ни в какие кружки не ходит).
Таким образом, кружков всего три, и каждый ученик ходит ровно в два кружка. Пусть в классе n учеников, тогда на три кружка в общей сложности приходится 2n их участников. Поэтому в математический кружок (самый многочисленный) ходит не менее, чем 2n/3 учеников.
|
|
|
Задача 117017 |
|
|
В классе 27 учеников. Каждый из учеников класса занимается не более чем в двух кружках, причём для каждых двух учеников существует кружок, в котором они занимаются вместе. Докажите, что найдётся кружок, в котором занимаются не менее 18 учеников.
Решение
См. задачу 117008.
|
|
|
Задача 79483 |
|
|
Даны 1985 множеств, каждое из которых состоит из 45 элементов, причём
объединение любых двух множеств содержит ровно 89 элементов.
Сколько элементов содержит объединение всех этих 1985 множеств?
Решение
По условию каждые два множества пересекаются по одному элементу. Докажем, что все множества пересекаются по одному элементу. Предположим противное. Возьмём множество M1. В нем найдётся элемент A, который принадлежит по крайней мере еще 45 множествам – M2, M3, ..., M46 (в противном случае общее число множеств не превосходило бы 44·45 + 1 = 1981). По предположению, имеется множество, не содержащее элемента A. Оно пересекается по одному элементу с множествами M1, M2, ..., M46 и поэтому содержит 46, а не 45 элементов. Противоречие.
Ответ
44·1985 + 1 = 87341 элементов.|
|
|
Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 50]
