Tübitak Lise 1. Aşama 2020 Soru 20

[Eray]

Bir satranç turnuvasına katılan üç arkadaş, turnuvadaki herkesin en fazla üç arkadaşı bulunduğunu ve arkadaş olmayan her iki kişinin ortak en az bir arkadaşı bulunduğunu farkediyor. Bu turnuvaya katılan kisi sayısı en fazla kaç olabilir?

$
\textbf{a)}\ 6
\qquad\textbf{b)}\ 7
\qquad\textbf{c)}\ 8
\qquad\textbf{d)}\ 9
\qquad\textbf{e)}\ \text{Hiçbiri}
$

[Lokman Gökçe]

Yanıt: $\boxed{C}$

Kişilere $1, 2, 3, \dots , n$ biçiminde numara verelim ve bu kişileri noktalarla gösterelim. Arkadaş olan iki kişi arasına bir çizgi çizelim. Problemde verilen üç arkadaş $1,2,3$ olsun. Bu durumu, köşeleri $1,2,3$ sayıları olan bir üçgen ile ifade ederiz. $4.$ kişi $1,2,3$ den en az biriyle arkadaş olmak zorundadır. Aksi halde $4.$ kişi, $1,2,3$ den hiçbiriyle arkadaş olmazsa problemin koşulu ile çelişir. O halde $4$ ile $1$ in arkadaş olduğunu varsayabiliriz. (Şekil 1)

Herkesin en fazla üç arkadaşı olacağından; $2$, $3$, $4$ ile arkadaşlık kurabilecek yeni kişilerin sayısı sırasıyla $1$, $1$, $2$ dir. Yani $4$ kişilik grubumuza toplamda en fazla $1+1+2=4$ kişi daha ekleyebiliriz. Böylece kişi sayısı $n \leq 8$ olur.

Şimdi $n=8$ için bir örnek durum bulmalıyız. Bu örneği bulmak zor olabilir. Kolaylık olması için $2$ ile arkadaş yeni bir kişi, $3$ ile arkadaş yeni bir kişi, $4$ ile arkadaş yeni iki kişi ekleyerek çizgemizi dolduralım. (Şekil 2) Daha sonra da deneme yaparak gerekli ara çizgileri çizerek şeklimizi tamamlayabiliriz. (Şekil 3)