Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 2023 => Konuyu başlatan: matematikolimpiyati - Temmuz 03, 2023, 04:42:56 ös
-
$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$
-
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.