ONE
    Númas
    ← Back to the programme
    OlympiadHardCombinatorics10–12

    Six People, Three Alike

    Seis Pessoas, Três Iguais

    Prove that in any group of six people there are always three who all know one another, or three no two of whom know one another. (Acquaintance is mutual.)

    Fix one person and sort the other five by whether that person knows them; one of the two groups must be large.

    Solution

    Step 1 of 7

    1. 1.Colour each pair red if the two know each other and blue if they do not. We must find a red triangle or a blue triangle.