Yanıt: 43
Çözüm: Şehirleri A1,A2,…,An 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≥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≥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.