Tübitak Lise 1. Aşama 2014 Soru 12

[ERhan ERdoğan]

$21$ öğrenciden oluşan ve herhangi üç öğrencisinin en az ikisi arkadaş olan her sınıfta en az $k$ arkadaşı olan bir öğrenci bulunuyorsa, $k$ nin alabileceği en büyük değer nedir?   

$
\textbf{a)}\ 8
\qquad\textbf{b)}\ 9
\qquad\textbf{c)}\ 10
\qquad\textbf{d)}\ 11
\qquad\textbf{e)}\ 12
$

[Egemen]

(Egemen Erbayat)

Yanıt: $\boxed{C}$

En çok arkadaşa sahip öğrenci $A$ olsun ve $A$ ile $B$ arkadaş olmayan iki öğrenci olsun.

$A-B-X$ üçlüsünde, $X$ öğrencisi $A$ ile veya $B$ ile arkadaş olmak zorunda. Çünkü, sorudaki herhangi üç öğrencinin ikisi arkadaş şartı, bunu zorunlu kılıyor.
O halde, $X(A)$ ile $A$ ile arkadaş olan $X$ öğrencilerinin, $X(B)$ ile $B$ ile arkadaş olan $X$ öğrencilerinin sayısını gösterirsek, İçerme-Dışarma ilkesi gereğince $$X(A) + X(B) - X(A \cap B) = 19$$ olduğu görülür.
$X(A) + X(B) \geq 19$ ve $X(A) \geq X(B)$ olduğu için
$2\cdot X(A) \geq 19$ ve $X(A) \geq 9,5$ olacaktır.

En küçük $X(A)$ değeri $10$ dur.
Yani herhangi bir sınıfta, en az $10$ arkadaşı olan bir $A$ kişisi yer almak zorunda.

[Lokman Gökçe]

En çok arkadaşı olan kişilerden biri $A$, $A$ nın arkadaş sayısı $n$ olsun. $A$ ile arkadaş olan kişilerin kümesini $B= \{B_1,B_2, \dots , B_n \}$ ile gösterelim. $A$ ile arkadaş olmayan $20-n$ kişinin kümesini de $ C= \{C_1,C_2, \dots , C_{20-n} \}$ ile gösterelim. $C$ kümesinden seçtiğimiz herhangi iki kişi $C_i,C_j$ olsun. $\{A, C_i,C_j \}$ üçlüsünü göz önüne alırsak problemin hipotezi gereği $C_i$, $C_j$ arkadaş olmalıdır. O halde $C$ kümesindeki herkes birbiriyle arkadaştır. Böylece $C$ deki bir kişinin en azından $19-n$ arkadaşı olduğunu anlarız. Ancak $A$ nın maksimum sayıda arkadaşa sahip olması özelliğinden dolayı $n \geq 19 - n$ olup $n \geq 10$ elde edilir.

Burada çözümü tamamlayabilmek için $n=10$ olabilecek bir durum örneği de vermemiz gerekmektedir. Örnek: $A$ nın arkadaş olduğu $10$ kişi ve arkadaş olmadığı $10$ kişiden oluşan bir düzenlemede $B$ deki herkes kendi içinde arkadaş, $C$ deki herkes kendi içinde arkadaş olsun. $B$ deki ve $C$ deki kişilerin ortak arkadaşı bulunmasın.

Düşünce biçimi olarak aynı yolla çözülebilen bir başka soru 2010 Pr/32 de verilmiştir.