Ülkedeki Şehirlerin Sayısı

Question

$\color{red}{\textbf{Problem [Lokman GÖKÇE]:}}$ Bir ülkedeki $n$ tane şehirden herhangi ikisi arasında doğrudan ulaşım sağlayan en fazla bir karayolu vardır. Doğrudan kara yolu ulaşımı en az olan şehirlerin her birinin ulaşabildiği $17$'şer şehir vardır. Ülkedeki toplam şehirlerarası karayollarının sayısı  $190$ ise, $n$ nin alabileceği değerler toplamını bulunuz.

 

 

$\color{blue}{\textbf{Not:}}$ Çizge teorisi çok bilgili olduğum bir alan değildir. Bu yüzden sorunun hikayesini sunarken yanlış anlaşılacak bir kısım olmaması için, problemin graf teorisi diliyle ifadesini de vermek iyi olabilir. Kendim de daha iyi kavrayabilmek için temel kavramları kullanarak yeni problemler üretmeye çalışıyorum. Bu düzeyde yeni bir soru yazarsam ya da öğrenirsem onları da paylaşabilirim. Sorumuz şuna eşdeğerdir:

 

Bir (basit) grafta, derecesi en az olan köşenin/köşelerin derecesi $17$ dir. Graftaki toplam kenar sayısı $190$ ise, köşe sayısının alabileceği değerler toplamını bulunuz.

Answer 1

Yanıt: $\boxed{43}$

 

$\color{red}{\textbf{Çözüm:}}$ Şehirleri $A_1, A_2, \dots, A_n$ noktalarıyla gösterelim. Eğer iki şehir arasında doğrudan bir yol varsa, bu iki noktayı birleştirelim. $n$ için bir alt sınır ve bir üst sınır bulmamız gerekmektedir. Akla gelebilecek basit bir alt sınır $n\geq 18$ olabilir. Çünkü, her bir noktanın derecesi en az $17$ ise, o nokta başka $17$ noktaya daha bağlıdır. Böylece $n\geq 17+1 = 18$ yazılabilir.

Fakat bu sınırı daha da geliştirebiliriz. $n$ köşeli bir tam çizge düşünelim. Yani herhangi iki şehir arasında daima bir yol olması durumuna bakıyoruz. Toplam $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ tane yol (tam çizgenin kenar sayısı) vardır. Böylece $\dfrac{n(n-1)}{2} \geq 190$ olup $n\geq 20$ elde edilir. $n=18$ ve $n=19$ durumlarında uygun konfigürasyonun varlığını/yokluğunu araştırma zahmetinden kurtulduk. $n=18$ ve $n=19$ için çözüm yoktur.

Peki, $n=20$ için çözüm var mıdır? sorusuna da hemen cevap verelim. $n=20$ iken çizgemiz, bir tam çizge olursa ancak bu durumda yol sayısı (çizgenin kenar sayısı) $|E|=190$ olabilmektedir. Fakat bu halde de tüm köşeler için derece $19$ olur. Yani derecesi $17$ olan köşe yoktur. $n=20$ olamaz.

 

Şimdi $n=21,22,23, 24 \dots$ değerlerini incelemeden önce, $n$ için bir üst sınır araştıralım. El sıkışma teoremine göre, tüm noktaların dereceleri toplamı $2|E| = 2\cdot 190 = 380$ dir. Her köşe için derece en az $17$ verildiğinden, $380 = 2|E| \geq 17\cdot n$ olup $n\leq 22$ elde edilir. 

 

$\color{red}\bullet$ $n=21$ için örnek çizge araştıralım. Noktaların (şehirlerin) dereceleri $17, 18, 19, 20$ olabilir. Bu derecelere sahip noktaların sayısı sırasıyla $a, b, c, d$ olsun. $a \geq 1$ olmak üzere

$$\begin{equation*} \left. \begin{split}   17a+18b+19c +20d & = & 380 \\   a+b+c+d & = & 21 \end{split} \text{ } \right\} \end{equation*}$$  

denklem sistemi için negatif olmayan tam sayılarda bir çözüm bulmalıyız. Bir çok pozitif tam sayı çözüm vardır, biz $(a,b,c,d) = (12, 1, 2, 6)$ çözümünü örnekleyelim. (Soruyu hazırlarken pozitif tam sayı çözüm olduğunu söylemek yeterli olur diye düşünmüştüm, şimdi aynı fikirde değilim. Gerçek bir örnek bulmak zorundayız ve bu da soruyu biraz daha zorlaştırıyor.) Önce $A_1, A_2, \dots ,A_{21}$ noktalarını kullanarak bir $K_{21}$ tam çizgesi oluşturalım. $21\cdot 20/2 = 210$ tane kenar oluşur. Her bir köşenin derecesi $20$ dir. Şimdi kenarlardan bazılarını köşe dereceleri $17$ nin altına düşmeyecek şekilde kaldıralım.

$A_1$ in bağlı olduğu $\{ A_{19}, A_{20}, A_{21} \}$ köşeleri ile aralarındaki kenarları kaldıralım.

$A_2$ nin bağlı olduğu $\{ A_{19}, A_{20}, A_{21} \}$ köşeleri ile aralarındaki kenarları kaldıralım.

$A_3$ ün bağlı olduğu $\{ A_{19}, A_{20}, A_{21} \}$ köşeleri ile aralarındaki kenarları kaldıralım. Böylece $\deg(A_1) = \deg(A_2)  = \deg(A_3) = \deg(A_{19}) = \deg(A_{20}) = \deg(A_{21}) = 17$ olur. Mevcut kenar sayısı $210 - 3\cdot 3 = 201$ dir. Devam edelim.

Benzer şekilde $\{ A_{4}, A_{5}, A_{6} \}$ grubu ile $\{ A_{16}, A_{17}, A_{18} \}$ grubu arasındaki kenarları kaldıralım. Böylece $\deg(A_4) = \deg(A_5)  = \deg(A_6) = \deg(A_{16}) = \deg(A_{17}) = \deg(A_{18}) = 17$ olur. Mevcut kenar sayısı $201 - 3\cdot 3 = 192$ dir. Devam edelim.

$A_7$ nin bağlı olduğu $\{ A_{14}, A_{15} \}$ köşeleri ile aralarındaki kenarları kaldıralım. $\deg(A_7) = 18$, $\deg(A_{14}) = \deg(A_{15}) = 19$ olur. Dokunmadığımız köşeler için $\deg(A_8) = \deg(A_9)  = \deg(A_{10}) = \deg(A_{11}) = \deg(A_{12}) = \deg(A_{13}) = 20$ dir. Mevcut kenar sayısı $192 - 2 = 190$ dır. Örnek bir konfigürasyon bulundu.

 

$\color{red}\bullet$ $n=22$ için örnek çizge araştıralım. Noktaların (şehirlerin) dereceleri $17, 18, 19, 20, 21$ olabilir. Bu derecelere sahip noktaların sayısı sırasıyla $a, b, c, d, e$ olsun. $a \geq 1$ olmak üzere

$$\begin{equation*} \left. \begin{split}   17a+18b+19c +20d + 21e& = & 380 \\   a+b+c+d +e & = & 22 \end{split} \text{ } \right\} \end{equation*}$$  

denklem sistemi için negatif olmayan tam sayılarda bir çözüm bulmalıyız. Daha da önemlisi, bu çözüme uygun bir çizge konfigürasyonu bulmalıyız. Önce $K_{22}$ tam çizgesini çizelim. Her bir köşenin derecesi $21$ dir. $22\cdot 21/2 = 231$ kenar vardır. Bunlardan bazılarını silerek $190$ a kadar ineceğiz. Fakat her bir köşe derecesinin de $17$ nin altına düşmesine izin vermemeliyiz. Benzer adımları kullanalım.

$\{ A_{1}, A_{2}, A_{3}, A_{4} \}$ grubu ile $\{ A_{19}, A_{20}, A_{21}, A_{22} \}$ grubu arasındaki kenarları silelim. $4\cdot 4 = 16$ kenar silinir. Bu $8$ noktanın derecesi $17$ ye düşer. $231 - 16 = 215$ kenar kalır.

$\{ A_{5}, A_{6}, A_{7}, A_{8} \}$ grubu ile $\{ A_{15}, A_{16}, A_{17}, A_{18} \}$ grubu arasındaki kenarları silelim. $4\cdot 4 = 16$ kenar silinir. Bu $8$ noktanın derecesi de $17$ ye düşer. $215 - 16 = 199$ kenar kalır.

$\{ A_{9}, A_{10}, A_{11} \}$ grubu ile $\{ A_{12}, A_{13}, A_{14} \}$ grubu arasındaki kenarları silelim. $3\cdot 3 = 9$ kenar silinir. Bu $6$ noktanın derecesi $18$ e düşer. $199 - 9 = 190$ kenar kalır. 

$n=22$ iken $(a,b,c,d,e) = (16, 6, 0, 0, 0)$ çözümüne karşılık bir konfigürasyon bulmuş olduk.

Öte yandan $n=22$ çift sayı iken $0\leq m < n$ aralığındaki her $m$ tam sayısı için $m$-düzenli çizge bulabildiğimizi şurada göstermiştik. $m=17$ için $22$ köşeli $17$-düzenli çizgede $22\cdot 17/2 = 187$ kenar vardır. $190 - 187 = 3$ kenar daha eklersek örnek bulmuş olacağız. Örneğin $A_1$ köşesini alalım ve bunun bağlı olmadığı $22-17-1 = 4$ köşe vardır. $A_1$ i bunlardan üçüne bağlarsak bir başka örnek durum elde etmiş oluruz.

 

 

Sonuç olarak, $n\in \{21, 22\}$ şeklinde iki değer vardır. Bunların toplamı ise $21+22 = \boxed{43}$ olur.