Tübitak Ortaokul 2. Aşama 2011 Soru 4

[geo]

Öğretmen sınıfa $20$ tane matematik ve $11$ tane fizik sorusundan oluşan bir liste vererek, her öğrencinin tam olarak $1$ matematik ve $1$ fizik sorusu seçip çözmesini istiyor. Aynı soru ikilisi birden fazla öğrenci tarafından seçilmemişse ve her öğrencinin seçtiği iki sorudan en az biri kendisinden başka en çok bir öğrenci tarafından seçilmişse, bu sınıfta en çok kaç öğrenci olabileceğini belirleyiniz.

(Azer Kerimov)

[alpercay]

Kaynak: http://geomania.org/forum/fantezi-cebir/2011-ilkogretim-olimpiyati-2-asama-sinavi/.   Ferhat GÖLBOL

çözüm-4 :
    Matematik sorularının m adedini, fizik sorularının n adedini 2'den fazla öğrenci çözmüş olsun. Bu n fizik sorusundan herhangi birini çözen öğrenci, soruda verilen koşula göre bu m matematik sorusundan birini çözemez. Dolayısıyla, n fizik sorusunun her biri, her birinin çözdüğü matematik sorusu farklı (ve m sorunun dışında) olan en fazla 20-m öğrenci tarafından çözülebilir. Ancak ikinci bir kısıtlama, 20-m matematik sorusunun her birini en fazla 2 öğrenci çözdüğünden, n fizik sorusunu çözen toplam öğrenci sayısının 2(20-m)=40-2m 'den fazla olamayacağıdır. Geriye kalan 11-n fizik sorusu en fazla ikişer öğrenci tarafından çözüldüğünden, toplam öğrenci sayısı en fazla 40-2m + 2(11-n) = 62-2m-2n  olur. O halde m ve n sayılarını olabildiğince küçük seçmeliyiz.
    Öte yandan, n fizik sorusunu çözen 40-2m öğrenci olduğundan, en fazla çözülen fizik sorusunu çözen öğrenci sayısı en az (40-2m)/n 'dir (güvercin yuvası ilkesi). (40-2m)/n < 20-m olduğundan n > 2 bulunur. Benzer işlemlerle m > 2 'dir. O halde maksimum öğrenci sayısı 54 bulunur.
    54 öğrenci için sağlanan bir durum bulursak çözüm tamamlanır. Öğrencilere A1, A2, ... , A54 ;   matematik sorularına M1, M2, ... , M20 ;    fizik sorularına F1, F2, ... , F11 diyelim. M19 ve M20 ile F10 ve F11 soruları 2'den fazla öğrenci tarafından çözülen sorular olsun. A2n-1 ile A2n (n=1,2,...,18) öğrencileri Mn sorusunu çözsün. Bu öğrencilerden çift indisli olanlar (A2, A4, ...), F10 ;   tek indisli olanlar (A1, A3, ...), F11 sorusunu çözsün. Kalan öğrencilerden A2n-1 ile A2n (n=19,20,...,27) öğrencileri Fn-18 sorusunu çözsün. Bu öğrencilerden tek indisli olanlar M19, çift indisli olanlar M20 sorusunu çözsün. Bu durumda verilen tüm koşullar sağlanır.

[geo]

Soruyu graf sorusuna çevirip öyle çözelim. Grafımızda 31 köşe olsun: $M_1, M_2,\ldots M_{20}, F_1, F_2, \ldots F_{11}$. $M_i$ köşeleri matematik soruların\i, $F_j$ fizik soruların\i, her bir kenar da öğrencilerin seçtiği soru çiftlerini temsil etsin. Yani bir öğrenci $M_5$ matematik sorusu ile $F_8$ fizik sorusunu çözdüyse bunu $M_5$ ile $F_8$'i birleştiren kenarla göstereceğiz. Bu durumda açıktır ki öğrenci sayısı ile kenar sayısı birbirine eşittir.

Şimdi soruyu okuyarak graf üzerindeki kısıtlamaları belirleyelim.

• Her kenarın bir köşesi $M$'lerden, diğer köşesi $F$'lerden olmak zorunda.
• Her iki nokta arasında en fazla $1$ kenar çizilebilir.
• Her kenarın iki köşesinden en az birinin derecesi $2$ ya da daha azdır.

Derecesi en fazla iki olan köşelerin dereceleri $d_1, d_2, \ldots d_k$ olsun. Yukarıdaki 3. maddeden dolayı $\text{kenar sayısı } \leq d_1+d_2+\ldots d_k$ olur. Çünkü her kenar bu toplamın içinde en az $1$ kez bulunur. $d_i \leq 2$ olduğu için, $d_1+\ldots d_k \leq 2k$ olur. Yani kenar sayısı $\leq 2k$ 'dir.

• $k=31$ ise,
     Bu durumda tüm noktaların derecesi en fazla $2$ olmak zorundadır. Fakat tüm kenarların en az bir köşesi $F$ olacağı için kenar sayısı en fazla $2\times 11= 22$ olabilir.
• $k=30$ ise,
     Bu durumda ya tüm $F$ noktalarının derecesi en fazla $2$ ya da tüm $M$ noktalarının derecesi en fazla $2$'dir. Kenar sayısı en fazla $2\times 11=22$ ya da $2\times 20=40$ olabilir.
• $k=29$ ise,
     $F$ 'lerin ya da $M$ lerin hepsinin derecesi en fazla $2$ olduğu durumda en cok $40$ kenar elde edilebildiğini yukarıda gösterdik. Geriye şu durum kalıyor: iki grupta da derecesi $2$'den fazla birer köşe varsa. $F$ lerde derecesi en fazla $2$ olan $10$ köşe ve derecesi $2$'den büyük bir köşe olacak. Derecesi $2$'den büyük olan köşenin derecesi en cok $20$ olabilir ($20$ tane $M$ olduğu için). Yani kenar sayısı en fazla $2\times 10+20=40$ olabilir.
• $k=28$ ise,
     Yani $3$ köşenin derecesi $2$'den fazla olması durumu. Yukarıdaki durumlarda $F$'de derecesi $2$'den büyük olan köşelerin sayısı $2$'den az iken en fazla $40$ kenar olabileceğini ispatlamıştık. Geriye sadece $F$ lerden derecesi $2$'den büyük olan köşelerin sayısı $2$ ve $M$ lerden derecesi $2$'den büyük olanlarin sayısı $1$ ise durumu kalıyor. Şimdi de kenarların sayısını $M$ lerden bulalım. $M$ lerde derecesi en fazla $2$ olan $19$ köşe ve derecesi $2$'den büyük olan $1$ köşe var ve o köşenin derecesi en fazla $11$. Dolayısıyla kenar sayısı en fazla $2\times 19+11=49$ olabilir.
• $k=27$ ise,
     Her $k$ değeri için en fazla $2k$ kenar olabileceğini biliyoruz. $k=27$ icin $54$ kenarlı bir graf bulmak mümkün. Kenarları listeleyelim:
     $(M_1, F_3)$
     $(M_1, F_4)$
     $\vdots$
     $(M_1, F_{11})$
     $(M_2, F_3)$
     $(M_2, F_4)$
     $\vdots$
     $(M_2, F_{11})$
     $(M_3, F_1)$
     $(M_3, F_2)$
     $(M_4, F_1)$
     $(M_4, F_2)$
     $(M_5, F_1)$
     $(M_5, F_2)$
     $\vdots$
     $(M_{20}, F_1)$
     $(M_{20}, F_2)$
     
     Toplamda $9+9+2\times 18=54$ kenar yazmış olduk. Daha küçük $k$ degerleri için $54$'ten az kenar oluşturulabileceği için cevap $\boxed{54}$ tür.
  

Kaynak:
Serdar ADA