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

[matematikolimpiyati]

$31$ kişiden oluşan bir sınıfta, $4$ öğrenci içeren her grubun içinde kendisi dışındaki diğer $3$ öğrenciyle arkadaş olan en az bir öğrenci bulunuyor. Buna göre bu sınıfta kendisi dışındaki tüm öğrencilerle arkadaş olan öğrenci sayısı en az kaç olabilir?

$\textbf{a)}\ 26  \qquad\textbf{b)}\ 27  \qquad\textbf{c)}\ 28  \qquad\textbf{d)}\ 29  \qquad\textbf{e)}\ 30$

[Lokman Gökçe]

Yanıt: $\boxed{C}$

En az arkadaşı olan bir $A$ kişisini alalım. $A$ nın $n$ tane arkadaşı olsun. O halde en çok $n$ kişi, diğer herkesle arkadaş olabilir. $30-n$ kişi $A$ nın arkadaşı değildir.

$\bullet$ $30-n\geq 3$ olduğunu varsayalım. Bu durumda $A$ ile arkadaş olmayan $B,C,D$ gibi en az $3$ kişi vardır. Problemde verilenden dolayı $A,B,C,D$ dörtlü grubunda diğer üçü ile arkadaş olan biri olmalıdır. Fakat $A$, bu üç kişiyle arkadaş olmadığı için çelişki oluşur.

$\bullet$ O halde $30-n \leq 2$ olmalıdır. Buradan $n\geq 28$ elde edilir. $n_{\min} = 28$ olduğu bir örnek verelim. $A$ kişisi, $B$ ve $C$ kişileriyle arkadaş olmasın. Geri kalan tüm ikililer arasında arkadaşlık olsun. $A, B, C$ dışındaki $28$ kişi, kendisi dışındaki herkesle arkadaş olmuş olur.



Not: Sınav esnasında minimum değeri hissederek çözen öğrenciler olmuş olabilir. Bu çizge (graph) teorisi sorusunun çözümü kısa görünmekle beraber, tam bir ispat sunulmak istendiğinde sınavın en seçici sorularından birisi olabileceğini düşünüyorum.