Tübitak Lise 2. Aşama 1997 Soru 3

[Lokman Gökçe]

$n>1$ tek, $k$ de pozitif bir tam sayı olsun. $n$ seçmen, $k$ adaydan oluşan $A$ kümesine ait bir üyeyi seçerken aşağıda tanımlanan "çoğunlukçu uzlaşı'' sistemini kullanmaktadır. Buna göre, her seçmen, adayları kendi tercihine göre bir sütun halinde yukarıdan aşağıya doğru sıralar. Bu "oy sütunları'' (herhangi bir sırayla) yan yana yazılarak $k\times n$ bir "oy matrisi'' elde edilir.
$a\in A$ adayının oy matrisinin $i.$ sırasında kaç kez geçtiğini $a_{i}$ sayısı ile gösterelim; $l_{a}$ tam sayısı da $\sum\limits_{i=1}^{l}{a_{i}} > \dfrac n2$ eşitsizliğini sağlayan en küçük $l$ sayısı olsun. $\overline l=\min\limits_{a\in A} l_{a}$ olmak üzere; $\lbrace a \in A | l_{a}= \overline l \rbrace $ kümesinin tek elemanlı olmasına yol açan oy matrislerine geçerli oy matrisleri diyeceğiz ve böyle her matris için, çoğunlukçu uzlaşıya göre yukarıdaki kümeye ait tek aday seçilmiş olacaktır.
Öte yandan, $\omega _{1}\ge \omega _{2}\ge \ldots \ge \omega _{k}\ge 0$ koşulunu sağlayan $\omega _{1}, \omega _{2}, \ldots ,\omega _{k}$ gerçel sayılarına bir ağırlık sistemi; her geçerli oy matrisi için de, $\sum\limits_{i=1}^{k}{\omega _{i}a_{i}}$ sayısına $a$ adayının toplam ağırlıklı puanı diyelim. Bir $\omega _{1}, \omega _{2}, \ldots ,\omega _{k}$ ağırlık sistemi, tüm geçerli oy matrisleri için, çoğunlukçu uzlaşıya göre seçilen adayın toplam ağırlıklı puanının diğer bütün adaylarınkinden büyük olmasına yol açıyorsa, bu ağırlık sistemi çoğunlukçu uzlaşıyı temsil ediyor diyeceğiz.

• $k=3$ için, çoğunlukçu uzlaşıyı temsil eden bir ağırlık sisteminin bulunup bulunmadığını belirleyiniz.
• $k>3$ ise, böyle bir ağırlık sisteminin bulunmadığını gösteriniz.

[geo]

$n=2m+1$ olsun.
Her aday, oy matrisinde $2m+1$ kez geçecektir.

a.

$k=3$ için, $\overline{l}=2$ olduğunda, $a$ adayının birinci geldiğini, $b$ adayının da ikinci olduğunu varsayalım. Tanım gereği $l_a=2$ dir. İlk $2$ sırada toplamda $4m+2$ tercih yer alacağı ve $a$ adayın en fazla $2m+1$ oyu bu sırada yer alacağından, geri kalan $2$ adaya ilk sırada $4m+2-\left(2m+1\right)=2m+1$ oy kalacaktır. Güvercin yuvasına göre, bu adaylardan çok oy alanı, $b$, en az $\left\lceil \frac{2m+1}{2}\right\rceil =m+1$ oy alacaktır. Bu durumda, bu aday için de $l_b=2$ olacaktır. Bu durumda $\overline{l}$ tanımlı değildir. Demek ki, $3$ aday olduğunda, $\overline{l}<2$ olmalı.

$\overline{l}=1$ için, $a$ adayı birinci, $b$ adayı da ikinci olsun.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
 & 1 & 2 & \dots  & m & m+1 & m+2 & \dots  & 2m+1 \\ \hline
w_1 & a & a & a & a & a & b & b & b \\ \hline
w_2 & b & b & b & b & b &  &  &  \\ \hline
w_3 &  &  &  &  &  & a & a & a \\ \hline
\end{array}$$
$a$ adayının alabileceği en küçük toplam ağırlık; $\left(m+1\right)w_1+mw_3$ olacaktır.

$b$ adayının alabileceği en büyük toplam ağırlık; $mw_1+\left(m+1\right)w_2$ olacaktır.

Bu oy matrisinin çoğunlukçu uzlaşıyı temsil etmesi için;
\[\left(m+1\right)w_1+mw_3>mw_1+\left(m+1\right)w_2\]
olmalı. Biraz düzenlersek
\[w_1-w_2>m\left(w_2-w_3\right)\]
elde ederiz. $w_1>w_2=w_3$ seçtiğimizde, yukarıdaki eşitsizlik her zaman sağlanır. Demek ki, $k=3$ için, çoğunlukçu uzlaşıyı temsil eden bir ağırlık sistemi bulunabiliyor.

b.

$k>3$ için,

$\overline{l}=1$ olduğunda
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
 & 1 & 2 & \dots  & m & m+1 & m+2 & \dots  & 2m+1 \\ \hline
w_1 & a & a & a & a & a & b & b & b \\ \hline
w_2 & b & b & b & b & b &  &  &  \\ \hline
w_3 &  &  &  &  &  &  &  &  \\ \hline
\dots  &  &  &  &  &  &  &  &  \\ \hline
w_k &  &  &  &  &  & a & a & a \\ \hline
\end{array}$$
\[\left(m+1\right)w_1+mw_k>mw_1+\left(m+1\right)w_2\Rightarrow w_1-w_2>m\left(w_2-w_k\right)\]
$\overline{l}=2$ olduğunda,

$k=4$ için:

İlk iki sırada yer alan toplam $4m+2$ oyun en fazla $3m$ tanesi birinci gelemeyen adaylara ait olmalı. Bu durumda, birinci gelen $a$ adayının en az $m+2$ oyu ilk iki sırada yer almalı.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
 & 1 & 2 & \dots  & m & m+1 & m+2 & \dots  & 2m+1 \\ \hline
w_1 & b & b & b & b & c & d & d & d \\ \hline
w_2 & a & a & a & a & a & a & c & c \\ \hline
w_3 &  &  &  &  & b & b & b & b \\ \hline
w_4 &  &  &  &  &  &  & a & a \\ \hline
\end{array}$$
$a$ adayı için en küçük toplam ağırlık ile, $b$ adayı için en büyük toplam ağırlığı karşılaştırırsak,
\[\left(m+2\right)w_2+\left(m-1\right)w_4>mw_1+\left(m+1\right)w_2\Rightarrow w_2-w_4>m\left(w_1-w_4\right)\]
elde ederiz. $\overline{l}=1$ ve $k=4$ durumunda $w_1-w_2>m\left(w_2-w_4\right)$ olduğu için, bu iki eşitsizliği birleştirdiğimizde, $\frac{w_1-w_2}{m}>w_2-w_4>m\left(w_1-w_4\right)\Rightarrow 1\ge \frac{w_1-w_2}{w_1-w_4}>m^2$ olur. Bu da $m>1$ olan oy matrisleri için bir ağırlık sisteminin bulunmadığını gösterir.

$k>4$ için:
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
 & 1 & 2 & \dots  & m & m+1 & m+2 & \dots  & 2m+1 \\ \hline
w_1 & b & b & b & b & c & d & d & d \\ \hline
w_2 & a & a & a & a & a &  & c & c \\ \hline
w_3 &  &  &  &  & b & b & b & b \\ \hline
\dots  &  &  &  &  &  &  &  &  \\ \hline
w_k &  &  &  &  &  &  & a & a \\ \hline
\end{array}$$

\[\left(m+1\right)w_2+mw_k>mw_1+\left(m+1\right)w_3\Rightarrow m\left(w_2-w_3\right)>m\left(w_1-w_k\right)-\left(w_2-w_3\right)\]
olacaktır.  $\overline{l}=1$ için daha önce elde ettiğimiz eşitsizlik ile bu eşitsizliği birleştirirsek $w_1-w_2>m\left(w_2-w_k\right)\ge m\left(w_2-w_3\right)>m\left(w_1-w_k\right)-\left(w_2-w_3\right)$
\[\Rightarrow w_1-w_2+w_2-w_3>m\left(w_1-w_k\right)\Rightarrow w_1-w_3>m\left(w_1-w_k\right)\Rightarrow 1\ge \frac{w_1-w_3}{w_1-w_k}>m\]
elde ederiz ki, bu da $m>1$ olan oy matrisleri için bir ağırlık sisteminin bulunmadığını gösterir.