Zasada szufladkowa

[sympatia17]

Czy wśród pięciu osób zawsze znajdzie się trójka znajomych (tzn. każdy zna każdego) lub trójka nieznajomych? A wśród sześciu?

[adambak]

wśród pięciu - nie, pomyśl nad grafem znajomości będącym kontrprzykładem, daleko szukać nie trzeba..

wśród sześciu - tak, jest ich na tyle dużo, że da radę.. wybierz spośród nich dowolną osobę i rozważ zbiory jej znajomych oraz nieznajomych (dwa przypadki: więcej znajomych lub więcej nieznajomych), zawsze wyjdzie że gdzieś się tą trójkę znajdzie..