Matematyka.pl

Każdy z 30 osób z klubu miał kapelusz. Każdy z nich wysłał swój kapelusz innej osobie (być może niektórzy dostali więcej niż jeden kapelusz).
Udowodnić, że istnieje grupa 10 osób, z których żaden nie dostał kapelusza od innej osoby z tej grupy.

Wystarczy podzielić zbiór kapeluszników na trzy podzbiory:

\(\displaystyle{ A, B, C}\)

\(\displaystyle{ A}\) - zbiór gdzie żaden członek z tego zbiory nie otrzymał kapelusza od członka z tego zbioru, zbiór jest niepusty bo nikt nie wysyła kapelusza sam do siebie, załóżmy , że jest to największy zbiór tego typu...

\(\displaystyle{ B}\) - zbiór do którego wysyłali kapelusze członkowie ze zbioru \(\displaystyle{ A}\)

\(\displaystyle{ C}\)- zbiór członków do którego nie należą ani z \(\displaystyle{ A}\) ani z \(\displaystyle{ B}\)...

Widać, że liczność \(\displaystyle{ A}\) jest większa lub równa od liczności \(\displaystyle{ B}\)

\(\displaystyle{ D}\) - jest zbiorem tego samego typu co \(\displaystyle{ A}\) lecz jest mniej licznym z założenia

Widać tu podział zbioru kapeluszników na trzy rozłączne podzbiory z których najliczniejszy jest \(\displaystyle{ A}\)

Zatem:

\(\displaystyle{ |A| \ge 10}\)

Jest to też wynikiem słynnego twierdzenia, które mówi, że jeżeli funkcja \(\displaystyle{ f}\) jest bez punktów stałych, oraz:

\(\displaystyle{ f: S \rightarrow S < \infty }\)

to istnieje takie:

\(\displaystyle{ A \subset S}\)

\(\displaystyle{ |A| \ge \left[ \frac{|S|}{3} \right] \wedge f(A) \cap A= \emptyset}\)

cnd...