Crux 1975 Problem 26 {çözüldü}

[Lokman Gökçe]

$n$ tane tam sayı verilsin. Elemanlarının arasına $+$ veya $-$ işaretleri koyarak elde edilen değer $n$ ile tam bölünebilecek şekilde, bu sayıların bir alt kümesinin seçilebileceğini gösteriniz.

[Eray]

Eğer $\pmod n$ de aynı değere sahip olan iki tamsayı var ise, bu tam sayılara $a$ ve $b$ dersek $a-b$ sayısı $n$ ile tam bölüneceğinden $\{a,b\}$ istenen bir alt kümedir.
Aksi takdirde bu $n$ tam sayının her biri $\pmod n$ de farklı bir değere sahip olur ki bu durumda $n$ ye tam bölünen bir $a$ sayısı bulunmalıdır. Bu durumda $\{a\}$ istenen bir alt küme olur.

[Lokman Gökçe]

Bu problem, sayıların arasına yalnızca $+$ işareti koyulması durumunda da sorulabilir.


Ek soru: $n$ tane tam sayı verilsin. Elemanlarının toplamı $n$ ile tam bölünebilecek şekilde, bu sayıların bir alt kümesinin seçilebileceğini gösteriniz.

[Lokman Gökçe]

Ek Soru: $n$ tane tam sayı verilsin. Elemanlarının toplamı $n$ ile tam bölünebilecek şekilde, bu sayıların bir alt kümesinin seçilebileceğini gösteriniz.



Çözüm: $n$ tane tam sayı $a_1, a_2, \dots, a_n$ olsun. $k=1, 2, \dots, n$ için $T_k = a_1+a_2+\cdots + a_k$ toplamlarını tanımlayalım.

Eğer $n \mid T_k$ olacak biçimde bir $k$ değeri varsa $\{ a_1, a_2, \dots, a_k \}$ alt kümesi istenen özelliktedir.

Eğer her bir $k\in \{ 1,2, \dots, n \}$ için $ n \nmid T_k $ oluyorsa $T_1, T_2, \dots , T_n $ sayıları $n$ ile bölümünden $1, 2, \dots , n-1$ kalanlarını verebilir. Güvercin yuvası prensibi gereği $ 1 \leq i < j \leq n$ olacak biçimde öyle iki farklı $i$, $j$ değerleri vardır ki $T_i$ ile $T_j$, $n$ ile bölündüğünde aynı kalanı verirler. Yani $T_j - T_i \equiv 0 \pmod{n}$ olur. Bu durumda 
$$ n \mid T_j - T_i = a_{i+1} + a_{i+2} + \cdots + a_{j}$$
olup $\{ a_{i+1}, a_{i+2}, \dots , a_{j} \}$ kümesi istenen özelliktedir.