Modüler Aritmetik ve Kombinasyon

[AtakanCİCEK]

$n>2$, $n$ elemanlı bir $S$ kümesinde herhangi $2$ elemanın toplamı herhangi bir pozitif tam sayının $4.$ kuvvetine eşit olduğu ve bu toplamların birbirinden farklı olduğu biliniyor. Daha sonra $S$ kümesindeki elemanlar üçerli gruplar halinde toplanıyor.(Toplanan sayılar aynı toplama işlemi sırasında kullanılamıyor ancak A kümesinin diğer elemanlarının elde edilmesinde tekrardan kullanılabiliyor. Örneğin:$1+1+3$ şeklinde toplam olamıyorken $1+2+4$ ve $1+2+5$ şeklinde $2$ farklı toplamda aynı sayılar kullanılabilir. ) Buna göre elde edilen farklı tüm  tek sayı olan toplamlar $A$ kümesine yazılıyor. Böyle bir kümenin var olduğu kabul edilirse $|A| ≤\left( \begin{matrix}n-1\\2\end{matrix} \right)$ olduğunu ispatlayınız.($|A|$, $A$ kümesinin eleman sayısını belirtmektedir.)
(Hazırlayan : İbrahim Atakan Çiçek)

[AtakanCİCEK]

Öncelikle iki elemeanın toplamının bir sayının $4.$ kuvvetine eşit olması bilgisini kullanmaya çalışalım. Teklik ve çiftlikle ilgili de bir şeyler söyleyebilmek için $(mod2^n)$ değerlerinden biriyle bakmamız daha sağlıklı olacaktır. $(mod2)$ yeterince açık sonuç vermeyeceğinden
$x^4≡...(mod4)$ ifadesinde noktalı yere gelecek değerleri bulalım.
$(4k)^4≡0(mod4)$
$(4k+1)^4≡1(mod4)$
$(4k+2)^4≡0(mod4)$
$(4k+3)^4≡1(mod4)$  Buradan $x^4≡${$0,1$}$(mod4)$ olabilir. iki sayının toplamının $0$ ve $1$ kalanlarını vermesi için biraz gözlem yapalım. Bu iki sayı $a$ ve $b$ olsun.
$1)$ $a≡0(mod4)$ ve $b≡3(mod4)$ olursa $a+b≡3(mod4)$ olur mümkün değildir.
$2)$ $a≡0(mod4)$ ve $b≡2(mod4)$ olursa $a+b≡2(mod4)$ olur mümkün değildir.
$3)$ $a≡1(mod4)$ ve $b≡2(mod4)$ olursa $a+b≡3(mod4)$ olur mümkün değildir.
$4)$ $a≡1(mod4)$ ve $b≡1(mod4)$ olursa $a+b≡2(mod4)$ olur mümkün değildir.
$5)$ $a≡3(mod4)$ ve $b≡3(mod4)$ olursa $a+b≡2(mod4)$ olur mümkün değildir.
Şimdi bu gözlemleri yorumlayalım.
aynı anda $4k+1$ veya $4k+3$ formlarında en az $2$ sayı olması mümkün değildir. dolayısıyla en fazla $2$ tek sayı olabilir. Bu nedenle $n>2$ verildiğinden  en az $1$ tane çift sayı bulunmalıdır. bu sayıya $c$ diyelim.
$a)$ $c=4k$ olursa  $1$ özelliğinden dolayı $3(mod4)$ formunda sayı bulunamaz. En fazla $1$ tane tek sayı olabilir.
$b)$ $c=4k+2$ olursa $3$ özelliğinden dolayı $1(mod4)$ formunda sayı bulunamaz. En fazla $1$ tane tek sayı olabilir.
Şimdi kümemizde $0$ veya $1$ tane tek sayı olduğunu göstermiş olduk.  Herhangi $3$ elemanın toplamının tek olabilmesi için en az $1$ tek sayı bulunmalıdır. Bu sayıya $x$ diyelim. $S$ kümesinden seçilen $3$ elemanın toplamının tek sayı olabilmesi için $x$ sayısı kesin bulunur.
Bu sayının yanına $S$ kümesinin kalan $n-1$ elemanından $2$ tanesini seçerek toplamı tek sayı elde etmiş oluruz . (tabii ki verilen şart bize kombinasyonu çağrıştırmalı.). Bu nedenle $A$ kümesi en fazla $\left( \begin{matrix}n-1\\2\end{matrix} \right)$ elemana sahip olabilir. $|A| ≤\left( \begin{matrix}n-1\\2\end{matrix} \right)$ ispatlanmış olur fakat uygun $S$ kümesi göstermek çok zor olduğu için $A$ kümesinin bu elemana sahip olabilip olamayacağını söylemek zordur.