A GRUBU
Ayrık Hesaplama Yapıları
Numarası
:
Adı Soyadı
:
22.03.2014
2. A¸sagıdaki
˘
pseudocode ile verilen satırlar i¸sletilirse, cnt isimli degi¸
˘ skenin son degeri
˘
ne olur?
set cnt to 0;
FOR i = 1 to 20
FOR j = 2 to 21
FOR k = 3 to 22
FOR l = 4 to 23
if i + j + k + l = 15 THEN
cnt = cnt + 1
END FOR
END FOR
END FOR
END FOR
print cnt;
SINAV YÖNERGESI˙
˙ saretlemelerinizde kur¸sun kalem kullanınız.
• I¸
• Soru ve cevap kagıtlarına
˘
numaranızı ve isminizi mürekkepli kalem ile yazınız.
• Sınavın ilk 30 dakikasında sınıftan çıkılmayacaktır.
• Hesap makinesi kullanmak yasaktır.
• Sınav boyunca cep telefonlarınızı kapalı tutunuz. Cep telefonunuzun açık olması sınavınızın
geçersiz sayılmasına neden olacaktır.
• Hesaplamalarınız için soru kagıdındaki
˘
bo¸s yerleri kullanınız.
• Degerlendirmede
˘
4 yanlı¸s 1 dogruyu
˘
götürecektir.
• Toplam 20 adet soru vardır.
A) 56
• Sınav süresi 120 dakikadır.
B) 816
C) 165
D) 256
E) 128
• Sınavda her türlü ders notunun kullanımı yasaktır.
• Ba¸sarılar dilerim.
Doç. Dr. Emrah AKYAR
SORULAR
1. “MAKARA” kelimesinin tüm farklı dizilimlerinden kaç tanesinde iki tane ‘A’ harfi
yan yana gelmez? Not: Üç tane ‘A’ harfi yan yana geldi˘ginde iki ‘A’ harfi de yan yana
gelmi¸s olur.
3. (2 − 2x + 2y − 2z)5 ifadesinin açılımında xyz’nin katsayısı kaçtır?
A) 720
A) −320
B) 120
B) −160
C) 20
C) 1920
D) 24
D) 640
E) 36
E) 960
1. Ara Sınav
1
2013–2014 Bahar Dönemi
Ayrık Hesaplama Yapıları
A GRUBU
4. 10 adet özde¸s madeni 1TL A, B, C ve D ki¸silerine, A ve B ki¸silerinde toplamda en az
22.03.2014
7. n herhangi bir dogal
˘ sayı olmak üzere a¸sagıdakilerden
˘
hangisi 6TL olacak s¸ ekilde dagıtılmak
˘
suretiyle kaç farklı s¸ ekilde sıfırlanabilir?
her zaman bir alt sınır olur?
A) 64
n
n/2
sayısı için
A) n2
B) 3003
B) 2n
C) 286
C) n!
2n
D)
n+1
E) n!/(2n )
D) 84
E) 125
5. S = {1, 2, 3, 4, 5, 6} kümesinin kaç tane A alt kümesi için {3, 4} ⊂ A ko¸sulu saglanır?
˘
A) 8
B) 16
C) 32
D) 28
8. A¸sagıda
˘
verilen s¸ ekle göre, A noktasından B noktasına her seferinde bir önceki al-
E) 24
tıgenin sagında
˘
bulunan altıgenden geçmek ko¸suluyla kaç farklı s¸ ekilde gidilebilir?
Örnek bir rota çizilmi¸stir.
A
B
6. 1, 5, 10, 25, 50 ve 100 sayılarını bir kez kullanarak sadece toplama i¸slemi ile (bu sayılar
dahil) kaç farklı sayı elde edersiniz?
A) 63
A) 462
B) 64
B) 89
C) 32
C) 233
D) 33
D) 924
E) 96
E) 144
1. Ara Sınav
2
2013–2014 Bahar Dönemi
Ayrık Hesaplama Yapıları
A GRUBU
22.03.2014
˘
en büyük sayı ile en küçük
9. {1, 2, 3, . . . , 1199, 1200} kümesindeki sayılardan kaç tanesi hem 3 hem 5 hem de 7 ile 12. {1, 2, . . . , 19, 20} kümesinden rastgele 4 sayı seçildiginde
sayının farkının 10’a e¸sit olma olasılıgı
˘ nedir?
bölünmez?
A) 550
A)
(92)
C)
(10
2)
E)
10(92)
(20
4)
10
B) 20
(4)
B) 549
C) 548
D) 547
E) 546
(20
4)
1
D) 20
(4)
10. 5100 sayısı kaç basamaklıdır (log 5 ≈ 0.69897, log 100 = 2)?
(20
4)
A) 70
13. Dört tane ‘0’, be¸s tane ‘1’ ve bir tane ‘2’ kullanılarak 10 basamaklı kaç farklı tamsayı
B) 71
C) 72
üretilebilir?
D) 73
A) 1260
E) 74
B) 756
C) 126
D) 6300
E) 630
11. Üç zar aynı anda atıldıgında
˘
gelen en büyük sayının gelen en küçük sayının iki ka- 14. {1, 2, . . . , 2014} kümesinin kaç tane alt kümesinin eleman sayısı tektir?
tına e¸sit olma olasılıgı
˘ nedir?
A) 21007
A) 1/2
B) 22014
B) 1/5
D) 1/3
C) 22013
2014
D)
2
E) 1/4
E) 22014 − 1
C) 1/6
1. Ara Sınav
3
2013–2014 Bahar Dönemi
A GRUBU
Ayrık Hesaplama Yapıları
22.03.2014
15. A ve B kümeleri birbirini kapsamayan iki küme ve | A ∪ B| = 15, | A ∩ B| = 6 olsun. 18. 4 farklı top 4 farklı kutuya rastgele dagıtılırsa,
˘
ilk iki kutunun bo¸s olma olasılıgı
˘
Buna göre | A| en fazla kaç olabilir?
nedir?
A) 7
A) 1/8
B) 8
B) 1/2
C) 6
C) 1/16
D) 14
D) 1/32
E) 12
E) 1/4
16. {1, 2, . . . , 42} kümesinden hiçbiri bir digerinin
˘
2 katı olmayacak s¸ ekilde en fazla kaç
tane eleman alınabilir?
19. A¸sagıdaki
˘
ifadeler açıldıgında
˘
hangisinin terim sayısı en fazladır?
A) 28
B) 30
A) ( x1 + x2 )7
C) 29
B) ( x1 + x2 + x3 + x4 + x5 )4
D) 26
C) ( x1 + x2 + x3 + x4 )5
E) 27
D) ( x1 + x2 + x3 )6
E) ( x1 + x2 + x3 + x4 + x5 + x6 )3
17. A¸sagıdaki
˘
s¸ ekil, 1 × 1 boyutlarında 5 × 6 kare ile olu¸sturulduguna
˘
göre bu s¸ ekilde
kaç farklı dikdörtgen vardır? (Not: kare de bir dikdörtgendir)
20. {1, 2, . . . , 8} kümesinin kaç alt kümesi ardı¸sık iki eleman içermez?
A) 34
B) 27 − 1
C) 16
D) 32
A) 360
1. Ara Sınav
B) 150
C) 300
D) 315
E) 27
E) 256
4
2013–2014 Bahar Dönemi
A GRUBU
Ayrık Hesaplama Yapıları
22.03.2014
6. Dikkat edilecek olursa verilen sayıların toplanmasıyla elde edilecek sayılar, verilen
ÇÖZÜMLER
sayılardan her zaman farklı olacaktır. Buna göre bu altı sayıdan ikisi seçilip toplanarak (62) farklı s¸ ekilde yeni bir sayı elde edilebilir. Aynı s¸ ekilde bu altı sayıdan üçü
seçilip toplanırsa (63) farklı sayı elde edilir. Bu s¸ ekilde devam edilir ve sayıların kendileri de sayılırsa
1. “MAKARA” kelimesinden ‘A’ harflerini çıkaralım. Kalan harfleri 3! = 6 farklı s¸ ekilde sıralayabiliriz. Her bir sıralamada ‘A’ harflerinin yan yana gelmemesi için ‘A’
harflerinin ile i¸saret edilen dört yerden üçüne yerle¸stirilmesi gerekir (MKR).
˘
cevap (3!)(43) = 24 olur.
Bu i¸slem de (43) = 4 farklı s¸ ekilde yapılabileceginden
6
6
6
6
6
6
+
+
+
+
+
= 26 − 1 = 63
1
2
3
4
5
6
2. Cevap, 15 özde¸s objenin 4 farklı kutuya birinci kutuda en az 1, ikinci kutuda en az 2,
üçüncü kutuda en az 3 ve dördüncü kutuda en az 4 obje olacak s¸ ekildeki farklı dagılımlarının
˘
sayısına e¸sittir. Buna göre 15 objenin birini birinci kutuya, ikisini ikinci
kutuya, üçünü üçüncü kutuya ve dördünü dördüncü kutuya koyup, kalan 5 objeyi
kutulara (ko¸sulsuz) dagıtırsak
˘
cevabı bulmu¸s oluruz. 5 özde¸s objenin 4 farklı kutuya
5 +4 −1
dagılımlarının
˘
sayısının da ( 4−1 ) = (83) = 3!8!5! = 56 oldugunu
˘
biliyoruz.
elde edilir.
7.
3. Multinomial Teoremini kullanacak olursak istenen katsayı
5
5!
22 (−2x )1 (2y)1 (−2z)1 =
22 (−2)2(−2) xyz
2, 1, 1, 1
2! 1! 1! 1!
2n
n +1
sayısı bize Pascal üçgeninin n. satırındaki elemanların aritmetik ortalamasını
n
verir. (~n/2
˘
) sayısı Pascal üçgeninin n. satırındaki en büyük eleman oldugundan
n
2n
aritmetik ortalamadan her zaman daha büyüktür. O halde n+1 sayısı (~n/2) sayısı
için bir alt sınır olarak alınabilir.
8. S¸ eklin n tane altıgen ile olu¸sturuldugunu
˘
dü¸sünelim. Bu durumda A noktasından
B noktasına An farklı s¸ ekilde gidilsin. A noktasından hareket etmek için iki seçenek
vardır: Ya C ya da D noktasına gidilmelidir.
4
= (5!)2 = 120 · 16 xyz
= 1920 xyz
A
olarak bulunur.
C
D
4. 6 ≤ k ≤ 10 olmak üzere A ve B ki¸silerine tam olarak k tane özde¸s madeni 1TL
B
˘
Kalan 10-k tane 1TL ise C ve
(k+2−2−1 1) = (k+1 1) = k + 1 farklı s¸ ekilde dagıtılabilir.
2 −1
D ki¸silerine ((10−2k−)+
˘
O halde A ve B
) = 10 − k + 1 farklı s¸ ekilde dagıtılabilir.
1
ki¸silerinde tam olarak k tane 1TL olacak s¸ ekilde 10 tane 1TL (k + 1)(10 − k + 1) farklı
s¸ ekilde dagıtılabilir.
˘
k nın tüm durumlarını toplayacak olursak,
Eger
˘ C noktasına gidilirse artık D noktasına gitmek mümkün olmayacak geriye n − 2
tane altıgen kalacaktır. Kalan altıgenlerle An−2 farklı s¸ ekilde C den B ye gidilebilir.
Ancak ilk adımda D noktasına gidilirse, C noktasına da gidilebilir. Yani An−1 farklı
s¸ ekilde D noktasından B noktasına gidilebilir. O halde toplamda An = An−2 + An−1
olur. A1 = 1 ve A2 = 1 oldugu
˘ açıktır. O halde An = Fn olur. Böylece cevap F12 = 144
olur.
∑10
k =6 ( k + 1)(10 − k + 1) = 7 · 5 + 8 · 4 + 9 · 3 + 10 · 2 + 11 · 1
= 35 + 32 + 27 + 20 + 11 = 125
9. Soru, içerme–dı¸slama prensibi ile çözülebilir. S = {1, 2, 3, . . . , 1199, 1200} kümesin-
sonucu elde edilir.
deki sayılardan 3 ile bölünebilenlerin kümesini c1 , 5 ile bölünebilenlerin kümesini c2
ve 7 ile bölünebilenlerin kümesini de c3 ile gösterecek olursak,
5. S = {1, 2, 3, 4, 5, 6} kümesinden {3, 4} kümesini çıkaralım ve S′ = (S \ {3, 4}) ile
gösterelim. S′ kümesinin hiçbir A alt kümesi için {3, 4} ⊂ A olmaz. S¸ imdi S′ kümesinin tüm alt kümelerinin (24 tane) {3, 4} kümesi ile bile¸skesi alınırsa, istenen ko¸sulu
saglayan
˘
tüm alt kümeler elde edilmi¸s olur. O halde cevap 24 = 16 olur.
1. Ara Sınav
|S| = 1200 |c1 | =
5
1200
1200
1200
= 400 |c2 | =
= 240 |c3 | =
= 171
3
5
7
2013–2014 Bahar Dönemi
A GRUBU
Ayrık Hesaplama Yapıları
| c1 c2 | =
1200
= 80
3·5
1200
1200
= 57 |c2 c3 | =
= 34
3·7
5·7
1200
= 11
| c1 c2 c3 | =
3·5·7
| c1 c3 | =
Böylece cevap
yısı e¸sittir (aralarında birebir bir e¸sleme vardır). Toplam alt küme sayısı 22014 oldu2014
gundan
˘
cevap 2 2 = 22013 olur.
10. Verilen bir pozitif m tamsayısının basamak sayısının log
˘
derslerde
m + 1oldugunu
100
100
sayısının basamak sayısı, log 5
+ 1 = 100 log 5 +
15. A kümesinde en fazla eleman bulunması için B kümesinde en az sayıda eleman
˙ küme birbirini kapsamadıgına
bulunmalıdır. Iki
˘
göre B \ A kümesinde en az 1 tane
eleman bulunmalıdır. O zaman | B \ A| = 1 ve | B| = 7 olur. Buradan | A \ B| =
15 − 7 = 8 ve | A| = 8 + 6 = 14 cevabı elde edilir.
11. Üç zar aynı anda atıldıgında
˘
ortaya çıkabilecek tüm durumların sayısı 63 olur. En
büyük zarın, en küçük zarın iki katı oldugu
˘ durumlar ise:
(1,1,2)
(1,2,2)
(2,2,4)
(2,3,4)
(2,4,4)
(3,3,6)
(3,4,6)
(3,5,6)
(3,6,6)
3 farklı s¸ ekilde ortaya çıkabilir.
3 farklı s¸ ekilde ortaya çıkabilir.
3 farklı s¸ ekilde ortaya çıkabilir.
6 farklı s¸ ekilde ortaya çıkabilir.
3 farklı s¸ ekilde ortaya çıkabilir.
3 farklı s¸ ekilde ortaya çıkabilir.
6 farklı s¸ ekilde
6 farklı s¸ ekilde
3 farklı s¸ ekilde
Böylece 3 + 3 + 3 + 6 + 3 + 3 + 6 + 6 + 3 = 36 farklı durum var. O halde cevap
olur.
16. {1, 2}, {3, 6}, {4, 8}, {5, 10}, {7, 14}, {9, 18}, {11, 22}, {12, 24}, {13, 26}, {15, 30},
{16, 32}, {17, 34}, {19, 38}, {20, 40}, {21, 42} kümelerinin her birisinden en fazla birer eleman alınabilir. Dolayısıyla alınacak eleman sayısı en fazla 42-15=27 olabilir.
17. Bir dikdörtgen olu¸sturmak için 6 yatay dogrudan
˘
2 si ve 7 dü¸sey dogrudan
˘
2 si
seçilmelidir. Buna göre cevap (62)(72) = 15 × 21 = 315 olur.
˙ iki kutunun
18. 4 farklı top 4 farklı kutuya 4 · 4 · 4 · 4 = 44 farklı s¸ ekilde dagıtılabilir.
˘
Ilk
bo¸s oldugu
˘ durumların sayısı ise 2 · 2 · 2 · 2 = 24 olur. O halde cevap
olur.
62
63
=
24
44
=
42
44
=
1
16
19. Her bir ifadenin terim sayısını hesaplayalım:
1
6
( x1 + x2 )7 ⇒
( x1 + x2 + x3 )6 ⇒
( x1 + x2 + x3 + x4 )5 ⇒
( x1 + x2 + x3 + x4 + x5 )4 ⇒
( x1 + x2 + x3 + x4 + x5 + x6 )3 ⇒
12. {1, 2, . . . , 19, 20} kümesinden 4 sayı (204) farklı s¸ ekilde seçilebilir. S¸ imdi istenilen durumların sayısını hesaplayalım. Seçilen sayıların en küçügü
˘ n olsun. Bu durumda en
büyük sayı n + 10 olur. Diger
˘ iki sayısı ise n ile n + 10 arasındaki (bu sayılar hariç) 9
sayıdan biri olmalıdır. n nin alabilecegi
˘ degerler
˘
de 1, 2, . . . , 10 oldugundan
˘
istenen
durumların sayısı
10
9
·
·
1
|{z}
1
2
| {z }
| {z }
en büyük sayı
(7+2−2−1 1) = (81) = 8
(6+3−3−1 1) = (82) = 28
(5+4−4−1 1) = (83) = 56
(4+5−5−1 1) = (84) = 70
(3+6−6−1 1) = (85) = 56
oldugundan
˘
en fazla terim ( x1 + x2 + x3 + x4 + x5 )4 ifadesinde yer alır.
20. Derste {1, 2, . . . , n} kümesi için ardı¸sık eleman içermeyen alt kümelerin sayısının
Fn+1 oldugunu
˘
kanıtlamı¸stık. Buna göre istenen sayı F(8+1) = F9 = 34 olur.
n nin farklı seçim- en büyük ile en
lerinin sayısı
küçük arasındaki
sayılar
1. Ara Sınav
olur.
14. Tek sayıda eleman içeren alt kümeler ile çift sayıda eleman içeren alt kümelerin sa-
elde edilir.
kanıtlamı¸stık. Buna göre 5
1 = 69 + 1 = 70 olur.
(20
4)
göre, en soldaki basamak için 6 rakamdan birini kullanabiliriz. Diger
˘ basamaklar
için ise kalan 9 rakamın tüm dizili¸sleri kullanılabilir. Ancak tekrar eden rakamlar
oldugundan
˘
cevap 4!6··9!5! = 756 olur.
|c1 c2 c3 | = 1200 − (400 + 240 + 171) + (80 + 57 + 34) − 11 = 549
10(92)
13. 0,0,0,0,1,1,1,1,1,2 rakamlarının tüm dizilimleri soruluyor. 0 ba¸sa gelemeyecegine
˘
olur. Buradan
22.03.2014
6
2013–2014 Bahar Dönemi
Download

A GRUBU