Pangeya

    Description of object 
    Groups of object
    View object
    Name national В классе 32 ученика.
    Name international V klasse 32 uchenika.
    Show all avatar photo(1)
    Source of objectCreated by the viewed user
    Object memory
    305 649  byte
    Inheritance   
    000
    Date of creation05 March 2017 Year 18H:53M:11S
    Date of update   05 March 2017 Year 18H:55M:59S


    SHARE 

    Detailed description of the object
    В классе 32 ученика. V klasse 32 uchenika.
    Dual mode
    Text mode
    Image mode
    Сложность: 4
    Классы: 8,9,10

    В классе 32 ученика. Было организовано 33 кружка, причём каждый кружок состоит из трёх человек и никакие два кружка не совпадают по составу. Доказать, что найдутся такие два кружка, которые пересекаются ровно по одному ученику.

    Решение
    Решим более общую задачу: пусть k учеников занимаются в n кружках (из трех человек), k ≤ n. Предположим противное: каждые два кружка либо не пересекаются, либо пересекаются ровно по двум ученикам. Заметим, что если кружки K и L пересекаются с кружком M, то они пересекаются и между собой (их пересечения с M имеют общий элемент). Значит, кружки разбиваются на группы пересекающихся между собой кружков. Каждой группе кружков соответствует группа учеников – объединение их составов. Эти группы также не пересекаются. Далее можно рассуждать по-разному.
    Первый способ.
    Поскольку кружков больше, чем учеников, в какой-то группе это неравенство также сохраняется. Поставим в соответствие каждой паре кружков этой группы пару учеников, каждый из которых ходит ровно в один из этих кружков. Пар кружков больше, чем пар учеников, поэтому какой-то паре учеников {a, b} соответствует по крайней мере две пары кружков {a, c, d}, {b, c, d} и {a, u, v}, {b, u, v}. Но кружки {a, c, d} и {b, u, v} не могут иметь двух общих учеников, поскольку пары {c, d} и {u, v} не совпадают. Противоречие.
    Второй способ.
    Если в группе, содержащей некоторый кружок {a, b, c}, есть кружки, содержащие хотя бы две из трех пар {a, b}, {a, c}, {b, c}, скажем кружок {a, b, d} и кружок {a, c, e}, то d = e (два последних кружка должны иметь двух общих членов). Единственный возможный кружок, пересекающийся с каждым из этих трех по двум элементам, – это {b, c, d}. Таким образом, в такой группе не более 4 кружков, куда ходят не менее 4 учеников.
    Если же все кружки группы содержат только одну из трех указанных пар (например, {a, b}), то количество кружков в ней на 2 меньше количества всех учеников, их посещающих.
    Итак, число кружков не превосходит числа учеников в классе.

    Cancel Continue
    Confirm that you are a human
    Send Cancel
    Expand Close
    Close
    Отмена