Tübitak Lise 1. Aşama 2010 Soru 32

[ERhan ERdoğan]

$1001$ kişilik bir okulda herhangi üç öğrenciden en az ikisi arkadaştır. Bu okulda en çok arkadaşa sahip olan öğrencilerden birinin arkadaş sayısı, $334,412,450,499$ değerlerinden kaçını alabilir?

$
\textbf{a)}\ 4
\qquad\textbf{b)}\ 3
\qquad\textbf{c)}\ 2
\qquad\textbf{d)}\ 1
\qquad\textbf{e)}\ \text{Hiçbiri}
$

[Lokman Gökçe]

En büyük - en küçük değer prensibi ile ilgili bir problem, çözelim

En çok arkadaşa sahip olan öğrencilerden biri $a$ olsun. $a$ nın arkadaş sayısı da $n$ olsun. Geriye kalan $1000$ kişiden $a$ ile arkadaş olan kişilerin kümesi $A=\{a_1, a_2, \dots, a_n \}$, $a$ ile arkadaş olmayan kişilerin kümesi $B= \{b_1, b_2, \dots, b_{1000-n} \}$ olsun. Seçilen herhangi $3$ kişiden ikisi arkadaş olduğundan $i \neq j$ için her $\{b_i,b_j, a \}$ üçlüsü için $b_i$ ile $b_j$ arkadaş olmak zorundadır. Yani $B$ kümesindeki herkes birbiriyle arkadaştır. O halde $B$ kümesindeki birinin en az $999-n$ arkadaşı vardır. Bu sayı, $a$ nın arkadaş sayısı olan $n$ den daha büyük değildir. $999-n \leq n$ eşitsizliğinden $n\geq 500$ bulunur. Yani $n$ sayısı $334, 412, 450, 499$ değerlerinden hiçbirini alamaz.

[mehmetutku]

(Mehmet Utku Özbek)

Yanıt: $\boxed{E}$

$A$ ve $B$ arkadaş olmayan iki kişi olsun. Herhangi üç kişiden ikisi arkadaşmış. O zaman $A$ ve $B$ nin dışındaki öğrenciler ya $A$ ya da $B$ den sadece biriyle arkadaştır. O zaman $A$ veya $B$ den birinin en az $500$ arkadaşı vardır. Yani o değerlerden hiçbirini alamaz.