Geomania.Org Forumları
Yarışma Soruları => Tübitak Ortaokul 2. Aşama => 2022 => Konuyu başlatan: matematikolimpiyati - Aralık 25, 2022, 10:22:14 ös
-
$101$ öğrencinin bulunduğu bir okulda her öğrencinin diğer öğrenciler arasında en az bir arkadaşı vardır. Her $1<n<101$ tam sayısı için bu okuldan $n$ öğrencinin öyle seçilebileceğini gösteriniz ki seçilen her öğrencinin seçilen diğer öğrenciler arasında en az bir arkadaşı olsun.
-
Çözüm: İlk önce her çift $n$ sayısı için $n$ öğrencinin seçilebileceğini gösterelim. $n = 2$ için iki arkadaştan oluşan herhangi iki kişi seçebiliriz. $n = 2l$ için $n$ öğrenciden oluşan ve koşulları sağlayan $A_{2l}$ öğrenci grubunun seçilebileceğini varsayalım. Okuldaki tüm öğrenciler kümesi $S$ olsun. $S - A_{2l}$ kümesinde iki arkadaş varsa bu iki öğrenciyi $A_{2l}$'ye ekleyerek $A_{2l+2}$'yi elde ederiz. Bu işlem $A_n$'ye kadar devam ederse $A_n$ seçilmiş olacaktır. Aksi takdirde bir $2m < n$ sayısı için $S - A_{2m}$'deki öğrencilerin herhangi ikisi aralarında arkadaş olmayacaktır. $101$ öğrenciden herhangi birinin en az bir arkadaşı olduğuna göre, bu durumda $S - A_{2m}$'deki herhangi bir öğrencinin $A_{2m}$'de arkadaşı vardır ve $S - A_{2m}$'den herhangi $n - 2m$ öğrenciyi seçip $A_{2m}$'ye ekleyerek $A_n$'yi elde ederiz.
$n$'nin tek olduğu durumda ilk adımda $3$ öğrenciden oluşan $A_3$ grubunu seçmemiz ve $n$ çift durumundaki gibi devam etmemiz yeterli olacaktır. Bunun için en az iki arkadaşı bulunan bir öğrenciyi ve onun iki arkadaşını seçebiliriz. Böyle bir öğrenci yoksa her öğrencinin sadece bir arkadaşı var ve okuldaki $101$ öğrenci birbirinden ayrık arkadaş ikililerine parçalanıyor, çelişki.
Kaynak: Tübitak resmi çözüm kitapçığı