Pangeya

    Description of object 
    Groups of object
    View object
    Name national Каждый из учеников класса занимается не более чем в двух кружках
    Name international Kazhdyj iz uchenikov klassa zanimaetsya ne bolee chem v dvuh kruzhkah
    Show all avatar photo(1)
    Source of objectCreated by the viewed user
    Object memory
    59 501  byte
    Inheritance   
    000
    Date of creation05 March 2017 Year 18H:47M:14S
    Date of update   05 March 2017 Year 18H:49M:07S


    SHARE 

    Detailed description of the object
    Каждый из учеников класса занимается не более чем в двух кружках Kazhdyj iz uchenikov klassa zanimaetsya ne bolee chem v dvuh kruzhkah
    Dual mode
    Text mode
    Image mode

    Сложность: 4-
    Классы: 5,6,7

    Каждый из учеников класса занимается не более чем в двух кружках, причем для любой пары учеников существует кружок, в котором они занимаются вместе. Докажите, что найдется кружок, в котором занимается не менее двух третей всего класса.

    Решение
    Если в некоторый кружок ходит весь класс, то все в порядке. Далее мы считаем, что такого кружка нет. Пусть самый многочисленный кружок – математический; его участников мы будем называть математиками. Есть ученик Вася, который в него не ходит. Рассмотрим его и одного из математиков. Они вместе ходят в другой кружок, допустим, в фото. Вася не может ходить в этот кружок вместе со всеми математиками, иначе математический кружок не будет самым многочисленным. Значит, с кем-то из математиков он ходит ещё в один кружок, например, в танцевальный. Итак, каждый математик ещё является либо фотографом, либо танцором (и никем другим). То, что было выше сказано про Васю, можно сказать и про любого ученика, который не является математиком: каждый из таких учеников – фотограф и танцор одновременно (и больше ни в какие кружки не ходит). Таким образом, кружков всего три, и каждый ученик ходит ровно в два кружка. Пусть в классе n учеников, тогда на три кружка в общей сложности приходится 2n их участников. Поэтому в математический кружок (самый многочисленный) ходит не менее, чем 2n/3 учеников.

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