Tübitak Lise Takım Seçme 1998 Soru 4

[Lokman Gökçe]

$n$ değişik lojman $n$ kişiye dağıtılacaktır. Herkesin lojmanlara ilişkin bir tercih sıralaması vardır ve hiç kimse farklı iki lojman arasında kayıtsız değildir. Dağıtım yapıldıktan sonra, herkesi en az bu dağıtım kadar hoşnut edecek ve en az bir kişiyi de bu dağıtımda kendisine düşen lojmana tercih ettiği bir lojmana kavuşturacak başka bir dağtımın bulunmadığı anlaşılır. Yapılan dağıtımda, en az bir kişiye $n$ lojman arasında en çok tercih ettiği lojmanın düşmüş olduğunu kanıtlayınız.

[geo]

Aksini varsayalım. Yani hiç kimseye $1.$ tercihi çıkmasın.

$n$ köşeli bir çizge düşünelim. Köşelerle kişileri ifade edelim. $P_i$ kişisinin $1.$ tercihi olan lojman $P_j$ kişisine çıkmışsa, $P_i$ den $P_j$ ye bir yönlü kenar çizelim.
Şimdi de $P_1$ den başlayarak yönlü kenarları takip edelim. $P_1=P_{a_0}$, $P_{a_1}$, $P_{a_2}$, $\ldots$, $P_{a_n}$, $\ldots$ dizisinde bir yerden sonra döngü olmak zorunda. Çünkü çizgede $n$ tane köşe var. Diyelim döngü $P_{a_i}, P_{a_{i+1}}, \ldots, P_{a_j}, P_{a_i}$ şeklinde.
$P_{a_i}$ kişisine $P_{a_{i+1}}$ kişisine çıkan evi, $\ldots$, $P_{a_j}$ kişisine de $P_{a_i}$ kişisine çıkan evi verirsek, bu döngüdeki kişiler bir öncekinden daha hoşnut olur. Soruda böyle bir dağılım olmadığı söylenmişti. Çelişki.
O zaman en az bir kişi $1.$ tercihini almış olmalı.

[geo]

Bu da deepseek'in DeepThink özelliği ile verdiği yanıt:

Adım Adım Açıklama ve Çözüm:

1. Varsayım (Çelişki İçin): 
Yapılan Pareto etkin dağıtımda, hiç kimse en çok tercih ettiği lojmana sahip değildir. Yani, her kişi kendi tercih listesinde en üst sıradaki lojmandan daha düşük bir lojmanda kalmıştır.

2. Lojmanlar ve Tercihlerin Analizi:
- Her lojman, en az bir kişi tarafından en çok tercih edilen olarak işaretlenmiştir (pigeonhole ilkesi). 
- Pareto etkin dağıtımda, bu lojmanlar başka kişilere verilmiştir (varsayıma göre). 

3. Döngüsel Takasın İncelenmesi:
- Bir kişi $ A $, en çok tercih ettiği lojman $ X $’e sahip değilse, $ X $ başka bir kişi $ B $’ye verilmiştir. 
- $ B $ de en çok tercih ettiği lojman $ Y $’ye sahip değilse, $ Y $ başka bir kişi $ C $’ye verilmiştir. 
- Bu döngü, sonlu sayıda kişi olduğu için bir noktada kendini tekrar eder. 

4. Pareto İyileştirmesi:
- Döngüdeki tüm kişiler, kendilerinden sonra gelen kişinin lojmanını tercih ediyorsa, bu kişilerin lojmanlarını takas etmek mümkündür. 
- Örneğin, $ A \rightarrow B \rightarrow C \rightarrow A $ şeklindeki bir döngüde: 
  - $ A $, $ X $’i alır (en çok tercihi), 
  - $ B $, $ Y $’yi alır (en çok tercihi), 
  - $ C $, $ Z $’yi alır (en çok tercihi). 
- Bu takas, hiçbir kişiyi daha kötü duruma düşürmez ve en az bir kişiyi daha iyi duruma getirir. 

5. Çelişkinin Elde Edilmesi:
- Pareto etkin bir dağıtımda böyle bir takas mümkün olamaz, çünkü bu durumda mevcut dağıtım Pareto etkin değildir. 
- Dolayısıyla, başlangıçtaki varsayım (hiç kimse en çok tercihine sahip değil) yanlıştır. 

6. Sonuç: 
En az bir kişi, en çok tercih ettiği lojmana sahip olmalıdır. 

Matematiksel Gösterim: 
$n$ kişi ve $n$ lojman için, Pareto etkin bir $\sigma$ dağıtımı olsun. 
- Her $i$ için $\sigma(i)$, $i$. kişinin aldığı lojman. 
- $\sigma$’nın Pareto etkin olması için, her $i$ ve $j$ çiftinde: 
$$
\sigma'(i) \succ_i \sigma(i) \Rightarrow \exists j \text{ öyle ki } \sigma'(j) \prec_j \sigma(j).
$$ 
- Varsayım: $\forall i, \sigma(i) \neq \text{en çok tercih edilen lojman}$. 
- Bu durumda, yukarıdaki döngüsel takas ile $\sigma'$ dağıtımı oluşturulabilir ve bu da $\sigma$’nın Pareto etkin olmadığını gösterir. 
- Çelişki! 

Cevap: 
$\boxed{\text{En az bir kişi en çok tercih ettiği lojmana sahiptir.}}$