Областная олимпиада по математике, 2011 год, 10 класс

В группе из 42 человек каждый знаком, по крайней мере, с 36 людьми из группы. Докажите, что в этой группе найдется компания из 7 человек, в которой все знают друг друга.

Комментарий/решение

Ең нашар жағдайды қарастырғанда әр адам 36 адамды таниды. Яғни $41-36=5$ адамды танымайды. 41 болу себебі өзін алып тастаймыз. Енді әр адам 5 адамды танымайтынын білдік. Осы 5 адамды 5 топқа бөлейік, ал адамның өзі 6шы топта болсын. Әр адамның 5 танымайтынын адамын жаңағы 5 топқа бөліп шығайық. Олай болса 7 адамнан 6 топ шығады. Және 7 адамдардың ішіндегі әр адамның 5 танымайтын адамы басқа топта болып, танитын адамдарымен бірге болады. Онда бір-бірін танитын 7 адамнан құралған топ табылады.

Жағдай ең нашар екенін дәлелдеу керек.

Дым өзгермейтін секілді

"5 адамды танымайды" емес "ең көп дегенде 5 адамды танымайды" деген жөнірек секілді. Және егерде біреу 37 адам танитын болса, біз онын танымайтын адамдарын 5 топқа бөле алмаймыз (бұл жағдай оңай деп ойлаймын).