Sınavdaki çözümümün bitirilmiş hali.
Cevap: $2n-3$Örnek: Gezgin, açgözlüce hareket edecek. Genelliği bozmadan sırayı
$$a_1+a_2<a_1+a_3<\dots<a_1+a_n<a_2+a_3<\dots<a_{n-1}+a_n$$ alabiliriz. Şu şehir sırası maksimum sefer sırasına ulaşmayı sağlar:
$$C_2\rightarrow C_1\rightarrow C_3\rightarrow C_2\rightarrow C_4\rightarrow C_3\rightarrow \dots \rightarrow C_{i+1}\rightarrow C_i\rightarrow C_{i+2}\rightarrow C_{i+1}\rightarrow\dots \rightarrow C_n\rightarrow C_{n-1}$$
Sayılırsa $2n-3$ sefer yapıldığı görülür.
İspat: $C_i\rightarrow C_j$ seferini $(i,j)$ kutucuğu temsil edecek şekilde $n\times n$ bir kare çizelim. Her $i$ için $(i,i)$ kutucuğunu siyaha boyalım. Gezgin $C_i\rightarrow C_j$ seferini yapınca $(i,j)$ kutucuğuna $(\cdot)$ koyalım. Gezginin yolunu işaretli kutuları bağlayarak belirtelim. Bu sisteme göre gezgin tahtada sadece yatay ve dikey hareket edebilir. Siyaha boyalı kutucuklara hareket edemez. Sorudaki koşulun sağlanması için her $(i,j)$ kutucuğu işaretlendiğinde her $i\geq x$ ve/veya $j\geq y$ için $(x,y)$ kutucuğu siyaha boyanmalı. Ayrıca karenin siyaha boyalı köşegeni kareyi ikiye ayırır. Bu yarılardan birinde çalışmak yeterlidir.
Şimdi çelişki yoluyla ispatı yapacağız. $İşaretlenmiş Kare Sayısı\geq 2n-2$ olsun. Sol alt yarıda çalışalım. Bu yarıda $n-1$ tane satır mevcuttur. İlk satırda bir kare vardır, bunu işaretlemek zorunludur. O halde kalan $n-2$ satır için
$$\frac{İşaretli Kutu}{Satır Sayısı}\geq\frac{2n-3}{n-2}>2$$
sağlanır. Bu ise Güvercin Yuvası Prensibi'nden en az bir satırda $3$ adet işaretli kare bulunması gerektiğini ifade eder. Gezginin hareket kabiliyeti sınırlı olduğundan sol alt yarıda sadece aşağı ve sağa doğru hareket edebilir. Bunu göz önünde bulundurduğumuzda
$$Yatay Mesafe\geq 2(n-2)-(n-1)+3=n$$
kare olacaktır. Fakat tahtanın sol alt yarısında ilerleyebileceği maksimum mesafe $n-1$ dir. Çelişki. O halde baştaki varsayım hatalıdır. İspat biter.
