alpsahin/tubitak-olimpiyat-dataset-v2 huggingface dataset:
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 2

[2-3 soruları için açıklama]
\(F(n)\) ile \(n\) uzunluğunda olan ve sadece 0 ve 1 karakterlerinden oluşan ve içerisinde üç tane ardışık 1 bulunmayan dizilerin sayısını ifade edelim. Örnek vermek gerekirse, üç uzunluğundaki 8 diziden sadece “111” dizisinde üç tane ardışık 1 olduğu için \(F(3) = 7\)’dir. Dört uzunluğundaki 16 diziden sadece “1110”, “1111” ve “0111” dizilerinde üç tane ardışık 1 olduğu için \(F(4) = 13\)’tür.

---

\(F(8)\) kaçtır?

Şıklar:
A) 81 | B) 100 | C) 121 | D) 144 | E) 149

Cevap: E 149

Çözüm:
Bir kısmı açıklamada verilen örneklerden \(F(1) = 2\), \(F(2) = 4\), \(F(3) = 7\) ve \(F(4) = 13\) olduğunu biliyoruz. \(n \ge 4\) olmak üzere, \(n\) uzunluğundaki bir diziyi ele alalım.
Dizinin ilk karakterinin 0 olması durumunda sonraki \(n-1\) karakterin içerisinde üç tane ardışık 1 olmaması halinde dizide üç tane ardışık 1 yoktur. Öyleyse, ilk karakteri 0 olan içerisinde ardışık üç tane 1 bulunmayan \(n\) uzunluğundaki dizilerin sayısı \(F(n-1)\)’dir.
Dizinin ilk karakterinin 1 olması durumunda dizinin ikinci karakterini de dikkate almamız gerekmektedir. Dizinin ilk iki karakteri 10 ise sonraki \(n-2\) karakterin içerisinde üç tane ardışık 1 olmamasını halinde dizide üç tane ardışık 1 yoktur. Öyleye, ilk iki karakteri 10 olan içerisinde ardışık üç tane 1 bulunmayan n uzunluğundaki dizilerin sayısı \(F(n-2)\)’dir. Dizinin ilk iki karakteri 11 ise dizinin üçüncü karakterini de dikkate almamız gerekmektedir. Dizinin üçüncü karakteri de 1 ise dizinin içerisinde üç tane ardışık 1 vardır. Dizinin ilk üç karakteri 110 ise sonraki \(n-3\) karakterin içerisinde üç tane ardışık 1 olmamasının halinde dizide üç tane ardışık 1 yoktur. Öyleyle, ilk üç karakteri 110 olan içerisinde ardışık üç tane 1 bulunmayan **n** uzunluğundaki dizilerin sayısı \(F(n-3)\)’dir. Öyleye, \(n \ge 4\) için \(F(n) = F(n-1) + F(n-2) + F(n-3)\) eşitliği sağlanır. Soru bu özyinelemeli ifade kullanılarak çözülebilir. \(F(5) = 13 + 7 + 4 = 24\)’tür. \(F(6) = 24 + 13 + 7 = 44\)’tür. \(F(7) = 44 + 24 + 13 = 81\)’dir. \(F(8) = 81 + 44 + 24 = 149\)’dur.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 3

[2-3 soruları için açıklama]
\(F(n)\) ile \(n\) uzunluğunda olan ve sadece 0 ve 1 karakterlerinden oluşan ve içerisinde üç tane ardışık 1 bulunmayan dizilerin sayısını ifade edelim. Örnek vermek gerekirse, üç uzunluğundaki 8 diziden sadece “111” dizisinde üç tane ardışık 1 olduğu için \(F(3) = 7\)’dir. Dört uzunluğundaki 16 diziden sadece “1110”, “1111” ve “0111” dizilerinde üç tane ardışık 1 olduğu için \(F(4) = 13\)’tür.

---

\(F(12)\) kaçtır?

Şıklar:
A) 1705 | B) 1947 | C) 2034 | D) 2368 | E) 2672

Cevap: A 1705

Çözüm:
Yukarıdaki sorunun çözümünden devam ile \(F(9) = 149 + 81 + 44 = 274\)'tür. \(F(10) = 274 + 149 + 81 = 504\)'tür. \(F(11) = 504 + 274 + 149 = 927\)'dir. \(F(12) = 927 + 504 + 274 = 1705\)'tir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 4

Ali, Buğra, Can ve Demir'den oluşan dört öğrencilik bir sınıfı sıraya dizmeniz istenmektedir. Ali en önde olmak istememektedir. Buğra önden ikinci sırada olmak istememektedir. Can önden üçüncü sırada olmak istememektedir. Demir ise en arkada olmak istememektedir. Öğrencileri isteklerine uygun olarak kaç farklı şekilde sıralayabilirsiniz?

Şıklar:
A) 6 | B) 7 | C) 8 | D) 9 | E) 10

Cevap: D 9

Çözüm:
Bu soru muhtemel bütün permütasyonları kontrol ederek çözülebilir. Öğrencileri isimlerinin baş harfleriyle simgelersek şartları sağlayan permütasyonlar *BADC, BCDA, BDAC, CADB, CDAB, DABC, DCAB* ve *DCBA'dır*. Bu yüzden doğru cevap 9'dur.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 5

Ali, Buğra, Can, Demir, Enes ve Faruk'tan oluşan altı öğrencilik bir sınıfı sıraya dizmeniz istenmemektedir. Ali en önde olmak istememektedir. BuğrA önden ikinci sırada olmak istememektedir. Can önden ÜÇÜNCÜ sırada olmak istememektedir. Demir önden dördüncü sırada olmak istememektedir. Enes önden beşinci sırada olmak istememektedir. Faruk ise en arkada olmak istememektedir. Öğrencileri isteklerine uygun olarak kaç farklı şekilde sıralayabılırsiniz?

Şıklar:
A) 255 | B) 260 | C) 265 | D) 270 | E) 275

Cevap: C 265

Çözüm:
Bize *n* tane birbirinden farklı nesne sıralı bir şekilde verilmiş olsun. Hiçbir nesnenin orijinal konumunda kalmadığı permütasyona verilen sıralı listenin bir düzensizliği denir. *n* elemanlı bir kümenin düzensizlik sayısı \(D(n) = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n \frac{1}{n!}\right)\) eşitliğine göre hesaplanabilir. Bu soruda bize \(D(6)\)'nın değeri sorulmaktadır. \(D(6) = 6! \left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120} + \frac{1}{720}\right) = 265\)'tir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 6

[6-10 soruları için açıklama]
n uzunluğunda bir tamsayı dizisi verilmiş olsun: A: {A₁, A₂, A₃, ... Aₙ}. Verilen dizideki ardışık olmak zorunda olmayan en uzun artan alt diziyi bulmak istiyoruz. Örnek vermek gerekirse A dizisi eğer {-3,12,10,1,4,7,7,0} olarak verilmişse en uzun artan dizi 4 uzunluğundaki {-3,1,4,7} dizisidir. Hedefimiz verilen bir dizi için en uzun artan alt dizinin uzunluğunu belirlemektir. Bu problemin çözümü için aşağıdaki özyineli denklemler kullanılabilir. Dizinin i. elemanında biten en uzun artan alt dizinin uzunluğunu U(i) olarak gösterecek olursak:
\[
U(1) = 1
\]
\[
U(i) = \max (U(j) + 1), \forall j \in [1..i-1] \text{ ve } A_j < A_i, \text{ ya da bu koşulu sağlayan bir j yok ise } U(i) = 1
\]
En son U(n) hesaplandıktan sonra max(U(i)), ∀i ∈ [1..n] değeri verilen A dizisi için en uzun artan alt dizinin uzunluğunu doğru bir şekilde gösterir.

---

A: {-7, 14, 10, 2, 3, 8, 8, 5, 8, 11, 15} olduğunda U(3) değeri ne olur?

Şıklar:
A) 0 | B) 1 | C) 2 | D) 7 | E) 10

Cevap: C 2

Çözüm:
U(3) için en ∀j ∈ [1..i-1] ve A_j < A_i koşulunu sadece U(1) sağlar ve U(3) de bu nedenle 1+1 = 2 olur.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 7

[6-10 soruları için açıklama]
n uzunluğunda bir tamsayı dizisi verilmiş olsun: A: {A₁, A₂, A₃, ... Aₙ}. Verilen dizideki ardışık olmak zorunda olmayan en uzun artan alt diziyi bulmak istiyoruz. Örnek vermek gerekirse A dizisi eğer {-3,12,10,1,4,7,7,0} olarak verilmişse en uzun artan dizi 4 uzunluğundaki {-3,1,4,7} dizisidir. Hedefimiz verilen bir dizi için en uzun artan alt dizinin uzunluğunu belirlemektir. Bu problemin çözümü için aşağıdaki özyineli denklemler kullanılabilir. Dizinin i. elemanında biten en uzun artan alt dizinin uzunluğunu U(i) olarak gösterecek olursak:
\[
U(1) = 1
\]
\[
U(i) = \max (U(j) + 1), \forall j \in [1..i-1] \text{ ve } A_j < A_i, \text{ ya da bu koşulu sağlayan bir j yok ise } U(i) = 1
\]
En son U(n) hesaplandıktan sonra max(U(i)), ∀i ∈ [1..n] değeri verilen A dizisi için en uzun artan alt dizinin uzunluğunu doğru bir şekilde gösterir.

---

A: {-7, 14, 10, 2, 3.8, 8, 5, 8, 11, 15} olduğında en uzun artan dizinin uzunluğu ne olur?

Şıklar:
A) 4 | B) 5 | C) 6 | D) 7 | E) 8

Cevap: D 7

Çözüm:
En uzun artan alt dizi {-7, 2, 3, 5, 8, 11, 15} dizisidir ve uzunluğu 7'dir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 8

[6-10 soruları için açıklama]
n uzunluğunda bir tamsayı dizisi verilmiş olsun: A: {A₁, A₂, A₃, ... Aₙ}. Verilen dizideki ardışık olmak zorunda olmayan en uzun artan alt diziyi bulmak istiyoruz. Örnek vermek gerekirse A dizisi eğer {-3,12,10,1,4,7,7,0} olarak verilmişse en uzun artan dizi 4 uzunluğundaki {-3,1,4,7} dizisidir. Hedefimiz verilen bir dizi için en uzun artan alt dizinin uzunluğunu belirlemektir. Bu problemin çözümü için aşağıdaki özyineli denklemler kullanılabilir. Dizinin i. elemanında biten en uzun artan alt dizinin uzunluğunu U(i) olarak gösterecek olursak:
\[
U(1) = 1
\]
\[
U(i) = \max (U(j) + 1), \forall j \in [1..i-1] \text{ ve } A_j < A_i, \text{ ya da bu koşulu sağlayan bir j yok ise } U(i) = 1
\]
En son U(n) hesaplandıktan sonra max(U(i)), ∀i ∈ [1..n] değeri verilen A dizisi için en uzun artan alt dizinin uzunluğunu doğru bir şekilde gösterir.

---

Problemin çözümü için hesaplanan U(i) değerleri için aşağıdaki ifadelerden hangisi yanlıştır?

Şıklar:
A) U(i) değerleri her zaman sıfırdan büyüktür | B) \( \forall i \in [1..n-1] \)  için  \( U(i+1) \geq U(i) \) | C) Elemanları birbirinden farklı küçükten büyüğe sıralı bir dizi için en yüksek değere sahip olan U(i) değeri n'dir | D) Elemanları birbirinden farklı büyükten küçüğe sıralı bir dizi için en yüksek değere sahipl olan U(i) değeri birdir | E) Bütün elemanları birbirine eşit olan bir dizi için en yüksek değere sahip olan U(i) değişir birdir

Cevap: B \( \forall i \in [1..n-1] \)  için  \( U(i+1) \geq U(i) \)

Çözüm:
Yanlış ifade B şıkkındaki ifadedir çünkü dizideki en küçük değer dizinin ortalarında bir yerde ise ve dizinin başlarında bir artan dizi var ise dizinin en küçük değerinin indeksindeki U değeri 1 olacaktır ve kendisinden önceki değerden küçük olabilir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 9

[6-10 soruları için açıklama]
n uzunluğunda bir tamsayı dizisi verilmiş olsun: A: {A₁, A₂, A₃, ... Aₙ}. Verilen dizideki ardışık olmak zorunda olmayan en uzun artan alt diziyi bulmak istiyoruz. Örnek vermek gerekirse A dizisi eğer {-3,12,10,1,4,7,7,0} olarak verilmişse en uzun artan dizi 4 uzunluğundaki {-3,1,4,7} dizisidir. Hedefimiz verilen bir dizi için en uzun artan alt dizinin uzunluğunu belirlemektir. Bu problemin çözümü için aşağıdaki özyineli denklemler kullanılabilir. Dizinin i. elemanında biten en uzun artan alt dizinin uzunluğunu U(i) olarak gösterecek olursak:
\[
U(1) = 1
\]
\[
U(i) = \max (U(j) + 1), \forall j \in [1..i-1] \text{ ve } A_j < A_i, \text{ ya da bu koşulu sağlayan bir j yok ise } U(i) = 1
\]
En son U(n) hesaplandıktan sonra max(U(i)), ∀i ∈ [1..n] değeri verilen A dizisi için en uzun artan alt dizinin uzunluğunu doğru bir şekilde gösterir.

---

A:  \( \{-15, -2, -2, 11, 6, -7, -8, 12, 13, 8, -8, -6, -14, -4, -8\} \)  olduğunda en uzun artan dizinin uzunluğu ne olur?

Şıklar:
A) 1 | B) 2 | C) 3 | D) 4 | E) 5

Cevap: E 5

Çözüm:
En uzun artan alt dizilerden birisi  \( \{-15, -2, 11, 12, 13\} \)  dizisidir ve uzunluğu 5'dir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 10

[6-10 soruları için açıklama]
n uzunluğunda bir tamsayı dizisi verilmiş olsun: A: {A₁, A₂, A₃, ... Aₙ}. Verilen dizideki ardışık olmak zorunda olmayan en uzun artan alt diziyi bulmak istiyoruz. Örnek vermek gerekirse A dizisi eğer {-3,12,10,1,4,7,7,0} olarak verilmişse en uzun artan dizi 4 uzunluğundaki {-3,1,4,7} dizisidir. Hedefimiz verilen bir dizi için en uzun artan alt dizinin uzunluğunu belirlemektir. Bu problemin çözümü için aşağıdaki özyineli denklemler kullanılabilir. Dizinin i. elemanında biten en uzun artan alt dizinin uzunluğunu U(i) olarak gösterecek olursak:
\[
U(1) = 1
\]
\[
U(i) = \max (U(j) + 1), \forall j \in [1..i-1] \text{ ve } A_j < A_i, \text{ ya da bu koşulu sağlayan bir j yok ise } U(i) = 1
\]
En son U(n) hesaplandıktan sonra max(U(i)), ∀i ∈ [1..n] değeri verilen A dizisi için en uzun artan alt dizinin uzunluğunu doğru bir şekilde gösterir.

---

A:  \( \{-10, -5, -8, 0, 10, 2, 0, -7, 9, 12\} \)  olduğunda en uzun artan dizinin uzunluğu neo olur?

Şıklar:
A) 4 | B) 5 | C) 6 | D) 7 | E) 8

Cevap: C 6

Çözüm:
En uzun artan alt dizi  \( \{-10, -5, 0, 2, 9, 12\} \)  dizisidir ve uzunluğu 6'dır.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 11

## [11-12 soruları için açıklama]
Bir törende Ahmet, Beyza, Canan, Demet, Elif, Furkan ve Gürkan belirli bir sıra ile birer şiir okuyacaktır. Belirlenecek sırada aşağıdaki kısıtlar göz önüne alınmalıdır.
 Elif birinci ya da ikinci sırada olmamalıdır.
 Demet mutlaka Elif şiirini okuduktan sonraki bir sırada şiirini okumalıdır (hemen sonra olmak zorunda değil).
 Ne Ahmet ne de Furkan yedinci sırada şiir okuyamaz.
 Ya Furkan ya da Gürkan hemen Demet’ten sonra şiir okumalıdır.
 Canan, ya Beyza’dan hemen sonra ya da Beyza’dan hemen önce şiir okumalıdır.

---

Eğer ilk şiir okuyacak kişi Canan olursa aşağıdakilerden hangisi kesinlikle doğru olmalıdır?

Şıklar:
A) Ahmet altıncı sırada şiir okur | B) Elif üçüncü sırada şiir okur | C) Gürkan yedinci sırada şiir okur | D) Ahmet, Furkan’dan hemen sonra şiir okur | E) Demet, Elif’ten hemen sonra şiir okur

Cevap: C Gürkan yedinci sırada şiir okur

Çözüm:
İlk iki sıralamanın Canan ve Beyza olacağı kesindir. Kalan 5 sırada Demet, Elif’ten sonra ve Furkan ya da Gürkan da Demet’ten hemen sonra olması gerektiği kesindir. Bu 5 sıra aşağıdakilerden birisi olabilir:
Ahmet, Elif, Demet, Furkan, Gürkan
Ahmet, Elif, Furkan, Demet, Gürkan
Ahmet, Furkan, Elif, Demet, Gürkan
Elif, Ahmet, Demet, Furkan, Gürkan
Elif, Ahmet, Furkan, Demet, Gürkan
Elif, Demet, Furkan, Ahmet, Gürkan
Elif, Furkan, Ahmet, Demet, Gürkan
Görüldüğü üzere Gürkan’ın yedinci olmadığı bir çözüm mümkün değildir. Diğer şıklardaki ifadelerin doğru olmadığı sıralamalar mümkündür.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 12

## [11-12 soruları için açıklama]
Bir törende Ahmet, Beyza, Canan, Demet, Elif, Furkan ve Gürkan belirli bir sıra ile birer şiir okuyacaktır. Belirlenecek sırada aşağıdaki kısıtlar göz önüne alınmalıdır.
 Elif birinci ya da ikinci sırada olmamalıdır.
 Demet mutlaka Elif şiirini okuduktan sonraki bir sırada şiirini okumalıdır (hemen sonra olmak zorunda değil).
 Ne Ahmet ne de Furkan yedinci sırada şiir okuyamaz.
 Ya Furkan ya da Gürkan hemen Demet’ten sonra şiir okumalıdır.
 Canan, ya Beyza’dan hemen sonra ya da Beyza’dan hemen önce şiir okumalıdır.

---

Eğer Beyza üçüncü sırada şiir okursa Furkan’ın en geç yer alabileceği sıra aşağıdakilerden hangisidir?

Şıklar:
A) Birinci | B) İkinci | C) Beşinci | D) Altıncı | E) Yedinci

Cevap: D Altıncı

Çözüm:
Furkan’ın yedinci sırada şiir okuyamayacağı verilen kısıtlardan birisidir. Ahmet, Canan, Beyza, Elif, Demet, Furkan, Gürkan sıralaması da bütün koşulları sağlayan olası bir sıralama olduğundan Furkan’ın en geç altıncı sırada şiir okuması mümkündür.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 13

Bir futbol maçında karşılaşan A ve B takımlarından, A takımı ataklarının %70’ini sağ kanattan %30’unu da sol kanattan yapmaktadır. Sağ kanattan yapılan atakların %60’ı ceza sağasına ulaşmadan savuşturulabilmektedir ve sol kanattan yapılan atakların da %80’i savuşturulabilmektedir. A takımının yaptığı tüm atakların yüzde kaçı B takımının ceza sağasına ulaşır?

Şıklar:
A) 34 | B) 42 | C) 60 | D) 66 | E) 70

Cevap: A 34

Çözüm:
100 atak varsa bunların 70'i sağ kanattan ve 30'u sol kanatta olur. 70 atagın %60'ı 42 atak ve 30 atagın %80'ı 24 ataki yani toplam 66 atak savuşturulmaktadır. Ceza sağasına 34 atak yanı %34 atak ulaşabilir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 14

10 kırmızı top ve 4 mavi top içeren bir torbadan 4 adet top bir kerede rastgele olarak seçilecektir. Seçilen 4 toptan birinin mavi olma ihtimali nedir?

Şıklar:
A) \( \frac{3}{4} \) | B) \( \frac{120}{210} \) | C) \( \frac{120}{1001} \) | D) \( \frac{210}{1001} \) | E) \( \frac{480}{1001} \)

Cevap: E \( \frac{480}{1001} \)

Çözüm:
Doğru cevap 10 kırmızıdan 3 tanesinin kaç farklı şekilde seçilebileceğinin 4 maviden 1 tanesinin kaç farklı şekilde seçilebileceği ile çarpımının 14 toptan 4 topun kaç farklı şekilde seçilebileceğine bölünmesi ile bulunabilir. Yani cevap \(\frac{10}{3} \times \frac{4}{1} = \frac{120 \cdot 4}{1001}\) olur.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 15

Yan yana 10 sandalye olan bir odada 4 öğrenci kaç farklı şekilde oturabilir?

Şıklar:
A) 24 | B) 5040 | C) 151200 | D) 907200 | E) 3628800

Cevap: B 5040

Çözüm:
Doğru cevap 10 faktöriyelin 10-4=6 faktöriyeler bölümü ile bulunur. Bu da 10*9*8*7 = 5040 yapar.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 16

[16-19 soruları için açıklama]
Ali yaşı küçük olmasına rağmen bilime çok meraklı bir çocuktur. Astronot olmak için gerekli bütün sınavlarda en yüksek notu almış ve Türkiye Uzay Ajansı tarafından aya gönderilecek ilk astronot olarak seçilmiştir. Ancak küçük bir problem vardır. Ali kedisini çok sevmektedir. Hatta öyle ki evdeki laboratuvarında kedisini klonlamayı başarmıştır. Ali'nin her birine 1 ile 20 arasında bir numara verdiği 20 adet kedisi vardır ve Ali evde bu kedileriyle beraber yaşamaktadır. Ali her nereye giderse gitsin yanında mutlaka kedilerinden en az bir tanesinin bulunması gerekmektedir. Ancak klonlama yaparken bazı ufak hesap hataları yaptığı için bazı kediler birbirlerinden hayatta oldukları müddetçe ayrılamamaktadır. Ayrılmaları durumunda galaksimiz yok olacaktır. Ali'nin elinde bu kedi ikililerinin listesi vardır ve aşağıdaki gibidir.
\[
L = \{(1,2), (2,3), (1,5), (2,16), (8,5), (12,13), (12,15), (8,9), (3,17), (3,18), (19,4), (7,4), (6,7), (7,10), (3,11), (14,11), (20,14)\}
\]
Bu listenin ilk ikilisi bize 1 ve 2 numaraları kedilerin birbirinden ayrılamayacağını, ikinci ikilisi 2 ve 3 numaralı kedilerin birbirinden ayrılamayacağı söylemektedir. Listede (1,3) ikilisi olmamasına karşın hem 1 numaralı hem de 3 numaralı kediler 2 numaralı kediden ayrılamadığından, dolaylı olarak birbirlerinden ayrılamamaktadırlar.
Ali bu durumu Türkiye Uzay Ajansı'na bildirmiş ve onlar da uzay mekiğinde yer sıkıntısı olduğu için Ali'nin yanında en fazla 10 tane kedi götürmesine izin vermişlerdir.

---

Ali beraberinde aya en az kaç kedi götürebilir?

Şıklar:
A) 1 | B) 2 | C) 3 | D) 4 | E) 5

Cevap: C 3

Çözüm:
Her bir kedinin bir düğüme ve L listesindeki her bir iklinin bir kenara karşılık geldiği bir çizge düşünelim. Bu çizgede aynı bağlı bileşende yer alan kediler ya topluca gideceklerdir ya da topluca kalacaklardır. Bu sorunun cevabı en küçük bağlı bileşendeki düğüm sayısıdır. En küçük bağlı bileşen 12, 13 ve 15 numaralı düğümlerden oluşmaktadır. Dolayısıyla cevap C şıkkı olan 3'tür.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 17

[16-19 soruları için açıklama]
Ali yaşı küçük olmasına rağmen bilime çok meraklı bir çocuktur. Astronot olmak için gerekli bütün sınavlarda en yüksek notu almış ve Türkiye Uzay Ajansı tarafından aya gönderilecek ilk astronot olarak seçilmiştir. Ancak küçük bir problem vardır. Ali kedisini çok sevmektedir. Hatta öyle ki evdeki laboratuvarında kedisini klonlamayı başarmıştır. Ali'nin her birine 1 ile 20 arasında bir numara verdiği 20 adet kedisi vardır ve Ali evde bu kedileriyle beraber yaşamaktadır. Ali her nereye giderse gitsin yanında mutlaka kedilerinden en az bir tanesinin bulunması gerekmektedir. Ancak klonlama yaparken bazı ufak hesap hataları yaptığı için bazı kediler birbirlerinden hayatta oldukları müddetçe ayrılamamaktadır. Ayrılmaları durumunda galaksimiz yok olacaktır. Ali'nin elinde bu kedi ikililerinin listesi vardır ve aşağıdaki gibidir.
\[
L = \{(1,2), (2,3), (1,5), (2,16), (8,5), (12,13), (12,15), (8,9), (3,17), (3,18), (19,4), (7,4), (6,7), (7,10), (3,11), (14,11), (20,14)\}
\]
Bu listenin ilk ikilisi bize 1 ve 2 numaraları kedilerin birbirinden ayrılamayacağını, ikinci ikilisi 2 ve 3 numaralı kedilerin birbirinden ayrılamayacağı söylemektedir. Listede (1,3) ikilisi olmamasına karşın hem 1 numaralı hem de 3 numaralı kediler 2 numaralı kediden ayrılamadığından, dolaylı olarak birbirlerinden ayrılamamaktadırlar.
Ali bu durumu Türkiye Uzay Ajansı'na bildirmiş ve onlar da uzay mekiğinde yer sıkıntısı olduğu için Ali'nin yanında en fazla 10 tane kedi götürmesine izin vermişlerdir.

---

Ali beraberinde aya en fazla kaç kedi götürebilir?

Şıklar:
A) 4 | B) 6 | C) 7 | D) 8 | E) 10

Cevap: D 8

Çözüm:
Her bir kedinin bir düğüme ve L listesindeki bir her iklinin bir kenara karşılık geldiği çizgede üç bağlı bileşen vardır. Bu bağlı bileşenlerin düğüm sayıları 12, 5 ve 3'tür. Bu çizgede aynı bağlı bileşende yer alan kedirler ya topluca gideceklerdir yada topluca kalacaklardır. Uzay ajansı en fazla 10 kedi götürmeye izin verdiği için 12 düğümlü bağlı bileşendeki kediler topluca kalmak durumundadırlar. Bu yüzden Ali ya 3, ya 5, ya da 8 kedi götürecektir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 18

[16-19 soruları için açıklama]
Ali yaşı küçük olmasına rağmen bilime çok meraklı bir çocuktur. Astronot olmak için gerekli bütün sınavlarda en yüksek notu almış ve Türkiye Uzay Ajansı tarafından aya gönderilecek ilk astronot olarak seçilmiştir. Ancak küçük bir problem vardır. Ali kedisini çok sevmektedir. Hatta öyle ki evdeki laboratuvarında kedisini klonlamayı başarmıştır. Ali'nin her birine 1 ile 20 arasında bir numara verdiği 20 adet kedisi vardır ve Ali evde bu kedileriyle beraber yaşamaktadır. Ali her nereye giderse gitsin yanında mutlaka kedilerinden en az bir tanesinin bulunması gerekmektedir. Ancak klonlama yaparken bazı ufak hesap hataları yaptığı için bazı kediler birbirlerinden hayatta oldukları müddetçe ayrılamamaktadır. Ayrılmaları durumunda galaksimiz yok olacaktır. Ali'nin elinde bu kedi ikililerinin listesi vardır ve aşağıdaki gibidir.
\[
L = \{(1,2), (2,3), (1,5), (2,16), (8,5), (12,13), (12,15), (8,9), (3,17), (3,18), (19,4), (7,4), (6,7), (7,10), (3,11), (14,11), (20,14)\}
\]
Bu listenin ilk ikilisi bize 1 ve 2 numaraları kedilerin birbirinden ayrılamayacağını, ikinci ikilisi 2 ve 3 numaralı kedilerin birbirinden ayrılamayacağı söylemektedir. Listede (1,3) ikilisi olmamasına karşın hem 1 numaralı hem de 3 numaralı kediler 2 numaralı kediden ayrılamadığından, dolaylı olarak birbirlerinden ayrılamamaktadırlar.
Ali bu durumu Türkiye Uzay Ajansı'na bildirmiş ve onlar da uzay mekiğinde yer sıkıntısı olduğu için Ali'nin yanında en fazla 10 tane kedi götürmesine izin vermişlerdir.

---

Ali’nin 5 numaralı kedisi ölmüştür. Bu durumda Ali aya en az kaç kedi götürebilir?

Şıklar:
A) 1 | B) 2 | C) 3 | D) 4 | E) 5

Cevap: B 2

Çözüm:
Çizgeden 5 numaralı düğüm kaldırılmıştır. Kalan çizge 2, 9, 3 ve 5 düğümlü 4 bağlı bileşenden oluşmaktadır. Aynı bağlı bileşende yer alan kediler ya topluca gideceklerdir yada topluca kalacaklardır. Bu durumda Ali 2 kediden oluşan bağlı bileşendeki kedileri (8 ve 9) götürebilir.
Bilgisayar Olimpiyatı 2021, 1. Aşama, Soru 19

[16-19 soruları için açıklama]
Ali yaşı küçük olmasına rağmen bilime çok meraklı bir çocuktur. Astronot olmak için gerekli bütün sınavlarda en yüksek notu almış ve Türkiye Uzay Ajansı tarafından aya gönderilecek ilk astronot olarak seçilmiştir. Ancak küçük bir problem vardır. Ali kedisini çok sevmektedir. Hatta öyle ki evdeki laboratuvarında kedisini klonlamayı başarmıştır. Ali'nin her birine 1 ile 20 arasında bir numara verdiği 20 adet kedisi vardır ve Ali evde bu kedileriyle beraber yaşamaktadır. Ali her nereye giderse gitsin yanında mutlaka kedilerinden en az bir tanesinin bulunması gerekmektedir. Ancak klonlama yaparken bazı ufak hesap hataları yaptığı için bazı kediler birbirlerinden hayatta oldukları müddetçe ayrılamamaktadır. Ayrılmaları durumunda galaksimiz yok olacaktır. Ali'nin elinde bu kedi ikililerinin listesi vardır ve aşağıdaki gibidir.
\[
L = \{(1,2), (2,3), (1,5), (2,16), (8,5), (12,13), (12,15), (8,9), (3,17), (3,18), (19,4), (7,4), (6,7), (7,10), (3,11), (14,11), (20,14)\}
\]
Bu listenin ilk ikilisi bize 1 ve 2 numaraları kedilerin birbirinden ayrılamayacağını, ikinci ikilisi 2 ve 3 numaralı kedilerin birbirinden ayrılamayacağı söylemektedir. Listede (1,3) ikilisi olmamasına karşın hem 1 numaralı hem de 3 numaralı kediler 2 numaralı kediden ayrılamadığından, dolaylı olarak birbirlerinden ayrılamamaktadırlar.
Ali bu durumu Türkiye Uzay Ajansı'na bildirmiş ve onlar da uzay mekiğinde yer sıkıntısı olduğu için Ali'nin yanında en fazla 10 tane kedi götürmesine izin vermişlerdir.

---

Ali’nin 5 numaralı kedisi ölmüştür. Bu durumda Ali aya en fazla kaç kedi götürebilir?

Şıklar:
A) 4 | B) 6 | C) 7 | D) 8 | E) 10

Cevap: E 10

Çözüm:
Çizgeden 5 numaralı düğüm kaldırılmıştır. Kalan çizge 2, 9, 3 ve 5 düğümlü 4 bağlı bileşenden oluşmaktadır. Aynı bağlı bileşende yer alan kediler ya topluca gideceklerdir yada topluca kalacaklardır. Bu durumda Ali 2, 3 ve 5 düğümlü bağlı bileşenlerdeki 10 kediyi götürebilir.