Kombinatorik Sorusu 3 {çözüldü}

[MATSEVER 27]

$20$ takım her bir gün $10$ maç olmak üzere $2$ günde toplam $20$ maç yapıyor. Herhangi iki takım $2$ gün içinde birbirleriyle en çok $1$ kez maç yapabiliyor. Ayrıca her bir takım, bir gün içinde en fazla iki kez maç yapabilir. Bu iki günün sonunda öyle $k$ takım vardır ki bu $k$ takımdan herhangi ikisi aralarında maç yapmamıştır. $k$ nın alabileceği en büyük değeri belirleyiniz.

(Tashih edildi. Lokman Gökçe'ye teşekkürler.)

[Lokman Gökçe]

Maç yapan iki takım tekrar maç yapamaz gibi bir koşul yoktur. Dolayısıyla ilk gün $5$ takım ikişerli olarak eşleşerek $10$ maç yaparlar. Aynı takımlar ikinci gün de $10$ maç yaparlar. Geriye  kalan $15$ takım kimseyle maç yapmamıştır. $k=15$ en büyük değer olur.

[muuurat]

A ve B takımları bir günde 10 maç yaparlar. Ertesi gün de aynı şekilde. Geriye kalan 18 takıma A ya da B den birini dahil edersek k=19 takım aralarında maç yapmamıştır.

[Lokman Gökçe]

Haklısınız. Bir takım, aynı gün birden fazla maç yapamaz gibi bir şart verilmediği için cevap $19$ olur. Bunu da düşünmüştüm ama bu defa soru aşırı basit oluyor diye bu tür bir şey sorulmak istenmemiştir diye kendi kendime bir yorumda bulunmuştum

[Lokman Gökçe]

[En son düzenleme] $20$ takım her bir gün $10$ maç olmak üzere $2$ günde toplam $20$ maç yapıyor. Herhangi $1$ takım $2$ günde en çok $1$ maç yapabiliyor. Bu $2$ günün sonunda öyle $k$ takım vardır ki bu $k$ takımdan herhangi ikisi aralarında maç yapmamıştır. $k$ nın alabileceği en büyük değeri belirleyiniz.

Sorunun bu şekilde olması için ben yönlendirmiştim galiba. Fakat soru hatalıdır. Bu şekilde maç yapmaları mümkün değildir. $A_1,A_2, \dots, A_{20}$ gibi $20$ takımın her bir gün $10$ maç yapması $A_1 \leftrightarrow A_2$, $A_3 \leftrightarrow A_4$, ..., $A_{19} \leftrightarrow A_{20} $ şeklinde olur. Her bir takımın en fazla $1$ maç yapmasına izin verildiği için herkes kotasını doldurmuş durumdadır. İkinci günde kimsenin maç yapma şansı kalmaz.

Soruyu şu biçimlerde sorarsak hatasız olur sanıyorum:

Versiyon 1 [Kolay]: $20$ takım her bir gün $10$ maç olmak üzere $2$ günde toplam $20$ maç yapıyor. Herhangi iki takım $2$ gün içinde birbirleriyle en çok $1$ kez maç yapabiliyor. Bu iki günün sonunda öyle $k$ takım vardır ki bu $k$ takımdan herhangi ikisi aralarında maç yapmamıştır. $k$ nın alabileceği en büyük değeri belirleyiniz.

Versiyon 2 [Diğerine Nispeten Daha Zor]: $20$ takım her bir gün $10$ maç olmak üzere $2$ günde toplam $20$ maç yapıyor. Herhangi iki takım $2$ gün içinde birbirleriyle en çok $1$ kez maç yapabiliyor. Ayrıca her bir takım, bir gün içinde en fazla iki kez maç yapabilir. Bu iki günün sonunda öyle $k$ takım vardır ki bu $k$ takımdan herhangi ikisi aralarında maç yapmamıştır. $k$ nın alabileceği en büyük değeri belirleyiniz.

[Lokman Gökçe]

Versiyon 1'in Çözümü: $k\leq 19$ olduğu açıktır.  Takımları $A_1, A_2, \dots , A_{20}$ ile gösterelim. $k=19$ olabileceğini düşünelim. Bu durumda $A_2, A_2, \dots , A_{20}$ isimli $19$ takım birbiriyle hiç maç yapmamış olur. Yani tüm maçları $A_1$ diğerleriyle oynamıştır. Fakat bu halde $A_1$ en fazla $19$ maç yapabilir. Halbuki toplam maç sayısı $20$ olmalıdır. Demek ki $A_2, A_2, \dots , A_{20}$ takımlarının birbiriyle hiç maç yapmaması mümkün değildir. $k=18$ dir. Örnek durum bulmak basittir.

Versiyon 2'nin Çözümü: $k=15$ en büyük değerdir. Buna örnek verelim. $A = \{ A_1, A_2, A_3, A_4, A_5 \}$ ve geriye kalan $15$ takımın kümesine de $B$ diyelim. $B$ deki takımlar birbirleri arasında hiç maç yapmamış olsun. $A_1$ takımı, $ \{ A_6, A_7, A_7, A_9 \}$ takımlarıyla; $A_2$ takımı da, $ \{ A_6, A_7, A_7, A_9 \}$ takımlarıyla; $A_3$ takımı, $ \{ A_{10}, A_{11}, A_{12}, A_{13} \}$ takımlarıyla; $A_4$ takımı da, $ \{ A_{10}, A_{11}, A_{12}, A_{13} \}$ takımlarıyla; $A_5$ takımı, $ \{ A_{14}, A_{15}, A_{16}, A_{17} \}$ takımlarıyla maç yaparsa örnek durum oluşur.

Şimdi $k=16$ olamayacağını gösterelim. $A = \{ A_1, A_2, A_3, A_4 \}$ ve geriye kalan $16$ takımın kümesine de $B$ diyelim. $B$ deki takımlar birbirleri arasında hiç maç yapmamış olsun. Takımları düzlemde noktalarla ve maç yapan iki takımı da bu noktaları birleştiren doğru parçalarıyla ifade edebiliriz. $20$ tane doğru parçası çizilmelidir. $A$ kümesindeki noktalardan çıkan doğru parçalarını (yani çizge teorisi diliyle $A_1, A_2, A_3, A_4, $ köşelerinin derecelerini) saymak yeterlidir. Ancak bu noktaların her birinin köşe derecesi en fazla $4$ olduğundan toplam derece en çok $4\cdot 4 =16$ olabiliyor. Halbuki toplam derecenin $20$ olması gerekirdi. Sonuç olarak $k < 16$ dır.

[MATSEVER 27]

Soruyu yabancı kaynaktan çevirirken hata yapmışım galiba. Düzelttiğiniz için size çok teşekkür ediyorum. Galiba sorunun orijinali de 2. versiyondu.