Tübitak Lise 1. Aşama 2024 Soru 04

[matematikolimpiyati]

$100$ öğrencinin katıldığı bir yaz okulunda en fazla $4$ arkadaşı olan öğrencilere utangaç diyelim. Her öğrencinin en az $4$ tane utangaç arkadaşı varsa, utangaç öğrenci sayısının alabileceği kaç farklı değer vardır?

$\textbf{a)}\ 1  \qquad\textbf{b)}\ 2  \qquad\textbf{c)}\ 3  \qquad\textbf{d)}\ 5  \qquad\textbf{e)}\ 8$

[geo]

Yanıt: $\boxed A$

Her öğrencinin en az 4 utangaç arkadaşı varsa her öğrencinin en az $4$ arkadaşı vardır. O zaman herhangi bir utangaç öğrencinin en az $4$ arkadaşı vardır.
Bir utangaç öğrencinin en fazla $4$ arkadaşı olacağı için herhangi bir utangaç öğrencinin tam olarak $4$ arkadaşı vardır. Her öğrencinin en az $4$ utangaç arkadaşı olduğu için bir utangaç öğrencinin bütün arkadaşları utangaçtır.
O halde utangaç olmayan bir öğrenci utangaç bir öğrenci ile arkadaş olamaz. Her öğrencinin en az 4 utangaç arkadaşı olması gerektiği için bu topluluktaki bütün öğrenciler utangaçtır.

Soru bizden istemese de örnek bir konfigürasyon oluşturabiliriz:

$\begin{array}{l|ccccc}
1 && 55&56 &57&58\\
\hline
2 && 56&57&58&59\\
\hline
3 && 57&58&59&60\\
\hline
4 && 58&59&60&61\\
\hline
\vdots \\
\hline
46 && 100&51&52&53\\
\hline
47&& 51&52&53&54 \\
\hline
48&& 52&53&54&55 \\
\hline
49&& 53&54&55&56 \\
\hline
50&& 54&55&56&57 \\
\hline
\end{array}$

Not:
Her köşesinden tam olarak $4$ kenar çıkan çizgeye (graf), $4-$düzenli çizge denir.
Wikipedia

[Lokman Gökçe]

Bir başka basit örnek konfigürasyon şu olabilir:

Önce $K_5$ tam grafı (çizgesi) çizelim. Bunu, bir düzgün beşgenin tüm kenarları ve köşegenleri çizilmiş olarak düşünebilirsiniz. $20$ tane $K_5$ grafı çizersek, tüm koşullar sağlanır.