SSCB 1963 Sorusu

Question

PROBLEM: Birbirinden Farklı pozitif reel sayılardan oluşan $A=\{a_1,a_2,\cdots ,a_{100}\}$ kümesinin boş olmayan her bir alt kümesinin elemanları toplanarak $2^{100}-1$ tane toplam elde ediliyor. En az kaç farklı toplam elde edilebilir?

Comments

Küme elemanlarını  $a_1=1,a_2=2,a_3=3,...,a_{100}=100$ olarak alınırsak(ki bu sorunun verilerine aykırı değil) şöyle düşünebiliriz.

Oluşturulabilecek $2^{100}-1$ adet alt kümelerin her birinin elemanları toplamını(tabi aynı olanları aynı harfle göstermek üzere) $s_1,s_2,s_3,...,s_{100}$ olarak düşünürsek o zaman ;

$1<s_1<s_2<s_3<...<s_{100}<5050$  olacaktır. Bu da $5050$ adet farklı sonucu ifade eder. 

Ancak tam sayı olmayan pozitif rel sayılar için yaklaşım daha farklı olsa gerek

---

Reel sayılarla sorulmuş olsa da bu sorunun da cevabı $5050$. Ortak bir yaklaşım olabilir belki.

---

Verilen cevap 5050 gerçekten mi? 

---

Bu soruyu pozitif kisitlamasi olmadan gercel sayilar icin dusunsene Emre, olur mu? Sana biraktigimdan ben cozmuyorum :)

Su tarz bir onek gibi olacagini dusunuyorum. {0,1}, {-1,0,1},  {-1,0,1,2}, {-2,-1,0,1,2}.

Negatif ve pozitiflik ayri ayri bakildiginda ayni kapiya geliyor. Kumede bi denge saglanmali. 

Answer 1

Genel bir $n$ pozitif tam sayısını ele alalım. Elemanların artan bir şekilde sıraladığımızı düşünelim. 

Tek elemanı $n$ tane farklı toplam gelir. İki elemanlı için $n$. elemanın yanına ekleyeceğimiz diğer elemanlar ilk toplamlardan farklı olur. Buradan en az $n-1$ toplam gelir. Aynı şekilde $n$. ve $(n-1)$. elemanlarla toplayacağım üçüncü bir eleman ile elde edeceğimiz toplam diğerlerinden büyük olacağından $n-2$ tane farklı toplam elde ederiz. Bu şekilde toplamda $1$'den $n$'e kadar olan sayıların toplamı alt sınır olur. Bu alt sınırı $\{1,\ldots,n\}$ kümesi sağlar. 

Ek: Eğer elemanları $2$'nin kuvvetleri ile oluşturursak tüm toplamlar farklı olur. Taban aritmetiği ile bunu biliyoruz. Bu küme de üst sınırı sağlar.