Tübitak Lise 1. Aşama 1998 Soru 15

[geo]

$12$ evli çift yuvarlak bir masanın etrafında, erkeklerin hepsi masanın bir tarafında yan yana, her kadın da eşinin tam karşısında olacak şekilde oturmaktadır. Masada oturanlar, her seferinde yan yana oturan bir kadınla bir erkeğin yer değiştirmesi suretiyle, tüm eşler yan yana gelinceye kadar yer değiştirir. Bunun için en az kaç yer değiştirme işlemi yapılmıştır?

$
\textbf{a)}\ 36
\qquad\textbf{b)}\ 55
\qquad\textbf{c)}\ 60
\qquad\textbf{d)}\ 66
\qquad\textbf{e)}\ \text{Hiçbiri}
$

[geo]

Yanıt: $\boxed{D}$

$E_1$'i $K_1$ ile kavuşuncaya kadar yer değiştirelim.
$E_1 \leftrightarrow K_{12}, K_{11}, \dots K_2$ şeklinde toplam $11$ yer değiştirme gerekecek.
Şimdi de aynı şeyi $E_2$ için yapalım.
$E_2 \leftrightarrow K_{12}, K_{11}, \dots K_3$ şeklinde toplam $10$ yer değiştirme gerekir.
$$\vdots$$
$E_{10} \leftrightarrow K_{12}, K_{11}$, $2$ yer değiştirme gerektirirken,
$E_{11} \leftrightarrow K_{12}$ ile $1$ yer değiştirme ile eşine kavuşacaktır.
Tüm bunları toplarsak $1+2+\dots + 11 = \dfrac{11\cdot 12}{2} = 66$ yer değiştirme elde ederiz. $66$ yer değiştirme ile tüm eşleri yan yana oturttuk. Ama daha az sayıda yer değiştirme ile oturtabililir miyiz? Buna cevap vermemiz gerekiyor.
$|E_iK_i|$ ile eşlerin birbirinden uzaklığını gösterelim. Başlangıçta her çift için $|E_iK_i|=12$. Son durumda bunun $|E_iK_i|=1$ olmasını istiyoruz. Başlangıçta $\sum_{i=1}^{12} |E_iK_i| = 144$ iken son durumda $\sum_{i=1}^{12} |E_iK_i| = 12$ olmalı.
Her seferinde yer değiştirdiğimiz $E_x \leftrightarrow K_y$ ikilisi eşlerine en fazla $1$ birim yaklaşıyorlar. Bu durumda seferinde $\sum_{i=1}^{12} |E_iK_i|$ toplamı en fazla $2$ birim küçülebilir. Bu takdirde, toplam değerinin $144$ ten $12$ ye düşmesi için en az  $\dfrac{144-12}{2}=66$ adım gerekir. $66$ adımda soruda istenen yer değiştirmeyi yapabildiğimize göre cevap $66$ dır.