Tübitak Lise 2. Aşama 2003 Soru 6

[geo]

$m\times n$ bir satranç tahtasının her birim karesine $0$ ya da $1$ yazılarak elde edilen bir yazılıma, $0$ ve $1$ lerin sayısı eşitse, eşit bir yazılım diyoruz. $a$ gerçel bir sayı olmak üzere, $m$ satır ve $n$ sütunun her biri için, o satır ya da sütun içindeki $1$ lerin yüzdesi $a$ dan küçük ya da $100-a$ dan büyük olmayacak şekilde bir eşit yazılımı olanaklı kılan $m$ ve $n$ sayıları bulunuyorsa, $a$ ya güzel sayı diyoruz. En büyük güzel sayıyı bulunuz.

[geo]

(Sinan KARAL)

İddiamız en büyük güzel sayının $75$ olduğudur. $75$ için örnek şekildeki gibidir.Her satır ve sütunda ya bir tane $1$ ya da üç tane $1$ vardır, yani $1$'lerin oranı hep ya $\leq \% 25$ ya da $\geq \% 75$ tir.
$$
\begin{array}{|c|c|c|c|}
\hline
0 & 0 & 0 & 1 \\ \hline
1 & 0 & 0 & 0 \\ \hline
1 & 1 & 0 & 1 \\ \hline
1 & 0 & 1 & 1 \\ \hline
\end{array}
$$
Varsayalım bir $a>75$ güzel sayı olsun. Bir $m$ ve $n$ için de $m$ x $n$ satranç tahtasını $1$ ve $0$ lar ile kaplamış olalım. Tam olarak $m_1$ satırda $1$ lerin yüzdesi $\geq a$ ve tam olarak $m_2=m-m_1$ satırda da $1$ lerin yüzdesi $\leq 100-a$ olsun. Benzer şekilde $n_1$ ve $n_2$ sayılarını sütunlarda tanımlayalım. Genelliği bozmadan, $m_2 \geq m_1$ varsayabiliriz çünkü $0$ ve $1$ lerin yazılımı birbirine göre simetriktir.
$1$ lerin yüzdesi $\leq 100-a$ olan $n_2$ sütundaki $1$ lerin toplam sayısı $\leq \dfrac{(100-a).n_2m}{100} < \dfrac{n_2(m_1+m_2)}{4}$
Diğer taraftan, bu yazılım eşit olduğu için tüm tahtadaki $1$ lerin toplam sayısı :  $\dfrac{mn}{2}= \dfrac{(m_1+m_2)(n_1+n_2)}{2}$ dir. Demek ki kalan $n_1$ sütunda :
$$\dfrac{(m_1+m_2)(n_1+n_2)}{2} - \dfrac{n_2(m_1+m_2)}{4}= \dfrac{(2n_1+n_2)(m_1+m_2)}{4}$$
den fazla sayıda $1$ var. Bu $1$ lerin en fazla $n_1m_1$ tanesi tanımladığımız $n_1$ sütun ve $m_1$ satırın kesişiminde olabilir. Dolayısıyla $n_1$ sütunun üstündeki $1$ lerin $$\dfrac{(2n_1+n_2)(m_1+m_2)}{4}-m_1n_1= \dfrac{n_2m_1+n_2m_2-2m_1n_1+2n_1m_2}{4}$$
den fazlası, aynı zamanda $1$ lerin yüzdesi $\leq 100-a$ olan $m_2$ satır üstünde.
Fakat biz, bu $m_2$ satır üstünde $\dfrac{(100-a)n}{100}.m_2$ den fazla $1$ olamayacağını biliyoruz. $$\implies \dfrac{(n_1+n_2)}{4}m_2 \geq \dfrac{100-a}{100}m_2.n > \dfrac{n_2m_1+n_2m_2-2m_1n_1+2n_1m_2}{4}$$
$$\implies 2m_1n_1 > n_2m_1+n_1m_2 ... (*)$$ bulunur.
$m_2 \geq m_1$ olduğundan, $(*)$ dan : $2m_1n_1 > n_2m_1+n_1m_2 \geq n_2m_1+n_1m_1$
$$\implies \boxed{n_1 > n_2}$$
Şimdi, $(*)$'ı bulana kadar yaptığımız hesabın benzerini $0$ ları sayarak yaparsak :
$2m_2n_2 > n_2m_1+n_1m_2$ bulunur, $(*)$ ile toplarsak : $$m_1n_1+m_2n_2 > n_2m_1+n_1m_2 \iff (m_1-m_2)(n_1-n_2) > 0$$ bulunur.  Fakat $$m_1-m_2 \leq 0 \text{ ve } n_1-n_2 > 0$$ olduğundan çelişki elde edilir.
Demek ki güzel sayı $\leq 75$ olmalıdır. İspat biter.

[efecan]

Çözüm kontrol edilmiştir, Sinan hocamızın eline sağlık.

Çözüm düzeltildi.