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/.Â

[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