Tübitak Ortaokul 1.Aşama 2015 Soru 30

[ERhan ERdoğan]

$k$ bir pozitif tam sayı olmak üzere, her $a$ tam sayısı için $2^{n_{1}}+2^{n_{2}}+\cdots+2^{n_{k}} \equiv a \pmod{20}$ olacak biçimde $n_{1},n_{2},\cdots,n_{k}$ negatif olmayan tam sayıları bulunabiliyorsa, $k$ nin alabileceği en küçük değer nedir?

$
\textbf{a)}\ 1
\qquad\textbf{b)}\ 2
\qquad\textbf{c)}\ 3
\qquad\textbf{d)}\ 4
\qquad\textbf{e)}\ 5
$

[çılgın]

Yanıt: $\boxed{C}$

2 nin kuvvetlerini mod 20 de incelersek 1,2,4,8,12,16 bıraktığını kolayca görebiliriz. mod 20 deki kalanların bu sayılardan en az kaç tane kullanılarak elde edilebileceğine bakalım.

0 : 4+16 - 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
1 : 1 - 1 sayı, en küçük mümkün değerdir.
2 : 2 - 1 sayı, en küçük mümkün değerdir.
3 : 1+2 - 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
4 : 4 - 1 sayı, en küçük mümkün değerdir.
5 : 1+4 - 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
6 : 2+4 - 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
7 : 1+2+4 - 3 sayı, 2 kullanılarak elde edilemez çünkü en az 1 adet 1 kullanılmak zorundadır ve 6 sayısı 2 adet kullanılarak elde edilebilir.
8 : 8 - 1 sayı, en küçük mümkün değerdir.
9 : 1+8 - 2 sayı, 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
10 : 2+8 - 2 sayı, 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
11 : 1+2+8 - 3 sayı, 3 sayı, 2 kullanılarak elde edilemez çünkü en az 1 adet 1 kullanılmak zorundadır ve 6 sayısı 2 adet kullanılarak elde edilebilir.
12 : 12 - 1 sayı, en küçük mümkün değerdir.
13 : 1+12 - 2 sayı, 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
14 : 2+12 - 2 sayı, 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
15 : 1+2+12 - 3 sayı, 3 sayı, 2 kullanılarak elde edilemez çünkü en az 1 adet 1 kullanılmak zorundadır ve 14 sayısı 2 adet kullanılarak elde edilebilir.
16 : 16 - 1 sayı, en küçük mümkün değerdir.
17 : 1+16 - 2 sayı, 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
18 : 2+16 - 2 sayı, 2 sayı, 1 kullanılarak elde edilemeyeceği açıktır.
19 : 1+2+16 - 3 sayı, 3 sayı, 2 kullanılarak elde edilemez çünkü en az 1 adet 1 kullanılmak zorundadır ve 18 sayısı 2 adet kullanılarak elde edilebilir.

Görüldüğü üzere bazı sayıları elde etmek için en az 3 sayıya ihtiyacımız var, şimdi 3 sayı ile tüm sayıları elde edebileceğimizin örneklerini verelim:

Yukarıdaki örnekte 1 sayı ile elde ettiğimiz sayılara 4 ve 16 ekleyerek elde edebiliriz.
3 sayı ile elde ettiğimiz sayılara herhangi bir işlem yapmamıza gerek yoktur.
0 : 2+2+16
3 : 1+1+1
5 : 1+2+2
6 : 2+2+2
9 : 1+4+4
10 : 2+4+4
13 : 1+4+8
14 : 2+4+8
17 : 1+8+8
18 : 2+8+8

Görüldüğü gibi 3 sayı ile tüm sayıları elde edebiliriz, yani cevap 3 tür.