Crux 1975 Problem - 26, $n$ ile Bölünebilme

Question

$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.

Comments

Soru böyle mi? Ben mi yanlış anlıyorum.

$n$ ile bölünen varsa bunu alırız. Yoksa ikisi denk olmalı. O ikisininin farkını alırız.

---

Orijinal soru metni şu şekilde:

Given $n$ integers. Show that one can select a subset of these numbers and insert plus or minus signs so that the number obtained is divisible by $n$.

 

Aralara $-$ işareti koyma hakkı vermeseydi, sadece $+$ kullanılabilseydi soru biraz daha zorlaşırdı. Çözümünüzü girebilirsiniz Sercan hocam. İlave soru yazayım. Sonra da buna bakarız:

 

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.

Answer 1

$n$ ile bölünen varsa bunu alırız. Yoksa ikisi denk olmalı. O ikisininin farkını alırız.

Answer 2

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.