Examkin

Soru

Zorluk: ZorRutin Olmayan Problemler

Bir dairesel pist etrafında saat yönünde 11'den 1212'ye kadar ardı��ık sayılarla numaralandırılmış 1212 adet durak bulunmaktadır. Bu pistte bulunan bir robot, her adımda üzerinde bulunduğu durağın numarasının kendisi hariç en büyük pozitif böleni kadar durak saat yönünde ilerlemektedir. 11 numaralı durağın kendisi hariç pozitif böleni olmadığından, robot bu durakta iken 11 durak ilerlemektedir.

Bu robot ilk hareketine AA numaralı duraktan başlayıp 100100 adım attığında 99 numaralı durakta durmaktadır.

Buna göre, AA yerine yazılabilecek farklı durak numaralarının toplamı kaçtır?

  1. A
    15
  2. B
    18
  3. C
    21
  4. 25Cevap
  5. E
    28

Cevap

Doğru cevap 25 sayısıdır.
Robotun başlangıç noktası olarak seçilebilecek 2, 6, 7 ve 10 numaralı duraklarının her biri için 100 adım atıldığında döngüsel hareket analizi gereği 9. durağa ulaşılır. Bu durakların toplamı 2 + 6 + 7 + 10 = 25 değerini vermektedir.

Adım Adım Çözüm

1
Her bir durak numarası için robotun bir sonraki adımda ulaşacağı durağı bulalım. Bir durağın numarasını x, kendisi hariç en büyük pozitif bölenini g(x) ile gösterirsek, bir sonraki durak f(x) = (x + g(x) - 1) mod 12 + 1 kuralıyla bulunur.
Durak geçişleri şu şekildedir: 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 6, 5 -> 6, 6 -> 9, 7 -> 8, 8 -> 12, 9 -> 12, 10 -> 3, 11 -> 12, 12 -> 6.
Hangi durağın hangi durağa bağlanacağını belirleyerek robotun hareket örüntüsünü ortaya çıkarmak.
2
Durakların ileriye doğru adım adımlarını inceleyerek döngüsel yapıyı tespit edelim.
Tüm yolların en nihayetinde 6 -> 9 -> 12 -> 6... şeklinde 3 adımlı bir periyodik döngüye ulaştığı görülür.
Çok sayıdaki adımların sonucunu modüler aritmetik yardımıyla kolayca analiz edebilmek.
3
Olası tüm başlangıç durakları (A) için 100. adım sonundaki konumu hesaplayalım. 100 adımın 3'lük döngü periyodundaki yerini belirlemek için adımları yazalım.
A = 2 için adımlar: 2 -> 3 -> 4 -> 6 -> 9 -> 12 -> 6 -> 9... (k >= 3 için k = 3m ise 6, 3m+1 ise 9, 3m+2 ise 12 olur. 100 = 3*33 + 1 olduğundan 100. adımda 9 olur). Benzer şekilde A = 6, A = 7 ve A = 10 duraklarının da 100. adımda 9. durakta sonlandığı doğrulanır.
Robotun 100. adımda 9. durakta bulunmasını sağlayan tüm A başlangıç değerlerini belirlemek.
4
Koşulu sağlayan farklı A değerlerini toplayalım.
2 + 6 + 7 + 10 = 25 bulunur.
Bulunan durak numaralarının toplamını elde etmek.

Anahtar Kavram

Rutin Olmayan Problemler ve Döngüsel Hareket Analizi
Tahmini Süre:2m 0s
Bu soruyu puanla

Konular

Rutin Olmayan Problemler

Bu konudan daha fazla soru