çocuk-şeker problemi ve UMO(2006) sorusu

[ERhan ERdoğan]

Bir çocuk her gün istediği kadar (en az bir tane) şeker yiyerek n tane şekeri
kaç farklı şekilde yer ?

XIV.UMO(2006)

10 şekeri olan Ali, her gün en az bir şeker yiyorsa, şekerlerin tümünü günlere
dağılımı itibariyle kaç değişik biçimde yiyebilir?

A)64    B)126    C)243      D)512       E)1025

[Lokman Gökçe]

10 şeker sorusunu çözelim. n şeker için genellemeyi bulmak kolay olacaktır.

10 şekeri bir günde bitiriyorsa bunu 1 yolla yapabilir. (hepsini ilk gün yemiştir, tek durum) Bunu 1 = C(9,0) ile gösterelim.
10 şekeri iki günde bitiriyorsa x₁ + x₂ = 10 denkleminin pozitif tamsayı çözümlerini arıyoruz. Bu sayı 9 dur ve 9 = C(9, 1) ile gösterelim.
10 şekeri üç günde bitiriyorsa x₁ + x₂ + x₃ = 10 denkleminin pozitif tamsayı çözümleri C(9, 2) tanedir.
10 şekeri dört günde bitiriyorsa x₁ + x₂ + x₃ + x₄ = 10 denkleminin pozitif tamsayı çözümleri C(9, 3) tanedir.

...vs devam edilirse

10 şekeri 10 günde bitiriyorsa x₁ + x₂ + ... + x₁₀ = 10 denkleminin pozitif tamsayı çözümü yalnızca 1 tanedir. 1 = C(9, 9) ile gösterelim.

Toplam C(9,0) + C(9, 1) + C(9, 2) + ... + C(9, 9) = 2⁹ = 512 elde edilir.


n şeker için formül C(n - 1,0) + C(n - 1, 1) + C(n - 1, 2) + ... + C(n - 1, n-  1) = 2^{n - 1} olur.

[proble_m]

10 şeker sorusunu çözelim. n şeker için genellemeyi bulmak kolay olacaktır.

10 şekeri bir günde bitiriyorsa bunu 1 yolla yapabilir. (hepsini ilk gün yemiştir, tek durum) Bunu 1 = C(9,0) ile gösterelim.
10 şekeri iki günde bitiriyorsa x₁ + x₂ = 10 denkleminin pozitif tamsayı çözümlerini arıyoruz. Bu sayı 9 dur ve 9 = C(9, 1) ile gösterelim.
10 şekeri üç günde bitiriyorsa x₁ + x₂ + x₃ = 10 denkleminin pozitif tamsayı çözümleri C(9, 2) tanedir.
10 şekeri dört günde bitiriyorsa x₁ + x₂ + x₃ + x₄ = 10 denkleminin pozitif tamsayı çözümleri C(9, 3) tanedir.

...vs devam edilirse

10 şekeri 10 günde bitiriyorsa x₁ + x₂ + ... + x₁₀ = 10 denkleminin pozitif tamsayı çözümü yalnızca 1 tanedir. 1 = C(9, 9) ile gösterelim.

Toplam C(9,0) + C(9, 1) + C(9, 2) + ... + C(9, 9) = 2⁹ = 512 elde edilir.


n şeker için formül C(n - 1,0) + C(n - 1, 1) + C(n - 1, 2) + ... + C(n - 1, n-  1) = 2^{n - 1} olur.

Lokman hocam güzel açıklamış. Literatürde de bir n pozitif tamsayının kendisinden küçük veya eşit pozitif tamsayıların toplamı biçiminde yazılabilme sayısı 2^n-1 ile verilmektedir. Örneğin 4 için;

1+1+1+1
1+1+2
2+1+1
1+2+1
2+2
1+3
3+1
4

yani 2³=8 dir.