Tübitak Lise 1. Aşama 2009 Soru 36

[ERhan ERdoğan]

Yüz kenti olan bir ülkedeki bazı kentler arasında yapılan tek yönlü uçak seferleri, başkentten başlayıp, ülkedeki her kentten en az bir kez geçerek, yeniden başkente dönmeyi mümkün kılan en az bir sefer dizisi bulunacak biçimde düzenlenmiştir. Böyle bir düzenlemede, bu şekildeki uçak seferi dizilerinden sefer sayısı en az olanın sefer sayısı, bütün bu tür düzenlemeler arasında en çok kaç olabilir?

$
\textbf{a)}\ 1850
\qquad\textbf{b)}\ 2100
\qquad\textbf{c)}\ 2550
\qquad\textbf{d)}\ 3060
\qquad\textbf{e)}\ \text{Hiçbiri}
$

[Lokman Gökçe]

Yanıt: $\boxed{C}$

Sorunun ifadesi benim için anlaşılır olmamakla beraber cevaba göre bir çözüm vereceğim. Böylece problemde bizden istenenin ne olduğu anlamış olacağımızı ümit ediyorum.

Öncelikle bir tanım verelim. $A_1,A_2,\dots , A_n$ şehirleri için $A_1 \to A_2 \to \dots \to A_n \to A_1$ seferi varsa buna $n$ uzunluğunda bir döngü diyelim. Soruda verilen ifadelerden, bütün şehirlerden başkente dönmek mümkün ve başkentten de bütün şehirlere ulaşmanın mümkün olduğunu anlıyoruz. Yani her bir şehir ile başkent arasında (en az) birer döngü vardır. Başkentten geçen bu döngüler arasında  en uzun döngünün uzunluğu $n$ olsun. Bunu bir çember üzerindeki $n$ nokta gibi düşünebilirsiniz. Bu döngüyle $n$ sefer yaparak başkentten başlayıp tam $n$ şehir dolaşıp tekrar başkente dönmüş oluyoruz. Geriye kalan $100-n$ şehir var. Başkentten bu şehirlerin her birine gidip gelmek en fazla $n$ seferle mümkündür. Çünkü başkentten başlayan döngülerin uzunluğunun en fazla $n$ olduğunu varsaymıştık. Dolayısıyla en çok $n(100-n)$ sefer daha elde edilir. Bu döngülerin oluşturduğu seferlerin toplamı en fazla $T=n+n(100-n)$ olup $T=n(101-n)$ dir. Şimdi bu $T$ değerleri arasından da en büyüğünü seçeceğiz. $n=50$ ya da $n=51$ için $T_{\max} = 50\cdot 51 = 2550$ elde edilir.

Peki sefer sayısı en az olanın ifadesiyle ne anlatılmak isteniyor? Çünkü sanki bunu çözümümde hiç kullanmadım gibi. ''Sefer sayısı en az olanın'' ifadesiyle aradığımız sefer dizisinde birbirinin aynı olan alt döngüler bulunmasını kısıtlamak amacı taşınmış olmalı. Yani $ A_1 \to A_2 \to A_1 \to A_2 \to \dots $ biçiminde $ \{ A_1 \to A_2 \to A_1 \}$ döngüsünü $1.000.000$ defa tekrarlamamız engellenmek istenmiş.

Yine de çözüm tam sayılmaz. Çünkü $2250$ kenardan oluşan bir sefer dizisi örneği bulmalıyız ve bu sefer dizisi içindeki herhangi iki döngü birbirinin aynısı olmamalı. $n=50$ durumunda $T=2550$ olduğuna örnek verelim. Şehirlerimiz $A_1,A_2,\dots , A_{100}$ ve $A_1$ başkent olsun. Aşağıdaki farklı döngüleri inceleyelim.

$ A_1 \to A_2 \to \dots \to A_{49} \to A_{50} \to A_1$
$ A_1 \to A_2 \to \dots \to A_{49} \to A_{51} \to A_1$

$\vdots$

$ A_1 \to A_2 \to \dots \to A_{49} \to A_{99} \to A_1$
$ A_1 \to A_2 \to \dots \to A_{49} \to A_{100} \to A_1$

Bu $51$ tane döngünün her birinin uzunluğu $50$ dir. İlk döngü $A_{50}$ den geçiyor ve bu döngüden başkası da $A_{50}$ den geçmiyor. İkinci sıradaki döngü ise $A_{51}$ den geçiyor ve bu döngüden başkası $A_{51}$ den geçmiyor ...vs. Son sıradaki döngü de $A_{100}$ den geçiyor ve bu döngüden başkası $A_{100}$ den geçmiyor. Yani tüm şehirleri dolaşabilmek için yapılması gereken $50\cdot 51 = 2550$ sefer örneğini de bulduk. Şekille göstermek istersek, tüm çember yaylarını saatin dönme yönünde yönlendirmek yeterlidir.

[Lokman Gökçe]

Yorum 1. ''Soruda ne isteniyordu, neyi buldun?'' diye sorabilirsiniz, haklısınız da. Şimdi sıradaki iş, bu çözüme uygun olan anlaşılır bir soru yazmak. Örneğin

$100$ köşeli bir yönlü graftın bir $A$ köşe noktasından diğer tüm noktalara döngüler aracılığıyla ulaşmak mümkün olsun. İçinde birbirinin aynısı olan iki alt döngüyü bulundurmayan, $A$ dan başlayıp yine $A$ da biten döngüye bir minimum döngü diyelim. Bir minimum döngünün uzunluğu en fazla kaç olabilir?

gibi bir soru yazabiliriz. Bu soru uçaklı, seyahatli biçimde hikayeleştirilebilir de ...

Yorum 2. Sorunun sunuluş biçiminde bir sıkıntı olduğu kesin. Çünkü ''sefer sayısı en az olanın'' ifadesi yoruma açık, neyi kastettiği belirsiz. Mesela sefer sayısı en az olan denince akla her şehirden tam bir kez geçilen seferler akla gelebilir. Hiçbir şey de çağrıştırmayabilir, sonsuz döngüler oluşacağı düşünülebilir.

36. Sorunun Çözüm Hikayesi

Çok zorlama bir yorumla aynı döngüleri tekrar ve tekrar içermeme kastedilmiş olabilir diye düşününce problemi ancak yayınlanmasından $8$ yıl sonra çözebildim. Geçen zaman içinde saçımız ağardı.

Şöyle bir şey de mümkün olabilir: Belki ben açık ve net olan problemi anlamıyorumdur. Ancak 2009'da problem çözümlerini bu sayfada çözüp tartışmıştık. $36.$ soru için uğraşmamıza rağmen neredeyse hiç bir mesafe alamamıştık. Matematik zekasından şüphe duymadığımız insanlar da soruyu anlayamadı. $1$ yıl sonra Mustafa Töngemen bey'in güzel bir yorumunu eklemiştim. Yaptığı işlem cevabı veriyordu ancak yine de neyi hesapladığımızdan emin değildim. Problemi uzun süre öylece kenara koydum. Belki ara ara yoklama çekip çözmeye yeltendiğim de olmuştur.

Yaklaşık bir haftadır problemi tekrar ele aldım. Problemi çözmek için yeniden graf teorisi kavramlarını kurcalamaya başladım. Derece, kenar sayısı, döngü, ağaç, gezgin satıcı problemi ...vs. Problemimiz yönlü graflarla (digraph veya directed graph)ve döngü (cycle) ile ilgiliydi. Bunlarla ilgili bir teorem vardır belki diye internetteki dokümanları araştırıp karıştırdım. Bizim problemin yanından geçen bir şey yoktu. Belki de graf teorisi alimlerinin çok iyi bildiği bir problemdir bu. O halde soruyu ecnebi lisanıyla bir başka foruma sorayım dedim. Soruyu anlayacaklarından şüpheliydim ancak bu tür bir şeyi daha önce çözen varsa sorunun ne demek istediğini anlatıp çözümü açıklayabilirdi. Yani boş atıp dolu çekecektim. Oradaki alimler de soruyu anlamadılar ve açık-anlaşılır biçimde sorunun ifadesini düzeltirsem yardımcı olabilecekleri ifade ettiler. Soruyu tek anlamayan ben değilmişim, oh... Soruyla bir kez daha baş başa kaldım ve M. Töngemen bey'in $n+ n(100-n)$ ifadesine yoğunlaşayım dedim. Bu ifadeye graf teorisi diliyle bir anlam kazandırırsam sorunun da ne istediğini anlayabilirdim. Hamilton Turu'yla da ilgili değil, acaba Euler Turu'yla ilgili bir şey mi bilmem gerekiyor falan derken nihayetinde yukarıdaki çözüm çıktı. Hiç kolay olmadı yani.

[geo]

Cevap: $2550$.

Kentler $A_1, \ldots, A_{100}$ olmak üzere, uçuşlar:

her $i=1, \ldots, 49$ için $A_i$ den $A_{i+1}$ e

her $i=51, \ldots, 100$ için $A_{50}$ den $A_i$ ye

her $i=51, \ldots, 100$ için $A_i$ den $A_1$ e

düzenlenmiş olsun. Bu durumda her kente en az bir kez uğrayan ve en az uçuş içeren kapalı güzergah en az $51 \cdot 50=2550$ uçak seferi içermektedir.
Şimdi ise başkentten başlayıp, ülkedeki her kentten en az bir kez geçerek, yeniden başkente dönmeyi mümkün kılan her uçuş düzenlemesinde her kente en az bir kez uğrayan ve en az uçak seferi içeren kapalı güzergahın en fazla $2550$ uçak seferi içerdiğini gösterelim. Her $A_i$ ve $A_j$ kent ikilisi için $A_j$ den $A_i$ ye varmak için yapılması gereken en az uçuş sayısı $d\left(A_i, A_j\right)$ olmak üzere, $\max _{i, j} d\left(A_i, A_j\right)=d\left(A_l, A_m\right)=p$ olsun. $p$ uçuş içeren $A_l \rightarrow A_m$ güzergahı, $A_l$ den $A_m$ ye en kısa güzergah olduğundan $A_l$ dışında $p$ farklı kent içeriyor. $A_m$ den bu $p$ kentten farklı yeni bir kente en fazla $p$ uçuş kullanarak gidilebiliyor. Daha sonra tüm kalan kentlere her yeni kent için en fazla $p$ uçuş kullanarak birer birer uğrarsak her kente en az bir kez uğrayan ve en az uçuş içeren kapalı güzergahın toplam uçuş sayısı en fazla $$p+p(100-p)=p(101-p) \leq \frac{(101-p+p)^2}{4}=2550.25$$ olacaktır.

Kaynak: Tübitak 17. Ulusal Matematik Olimpiyatı Birinci Aşama Sınav Soru ve Çözümleri 2009