Bir dairesel dizi oyunu

Question

$[1 … N]$ aralığındaki tamsayılarla oynanan bir oyun şu şekilde tanımlanıyor: Sayılar artan sırada olacak şekilde yan yana dizilir. İlk sayı olan 1’den başlayarak bu dizilimdeki sayılar birer atlanarak silinir. Dizinin dairesel olduğu düşünülerek dizi sonuna gelindiğinde koruma/silme işlemine dizinin başından itibaren geriye kalan sayılarla devam edilir. Bu oyun, geriye sadece bir sayı kalana kadar oynanır. İlk geçiş, 1’in korunmasıyla başlar.
Örnek: 
$N = 7  $ için dizimiz 1 2 3 4 5 6 7 şeklindedir. 
İlk geçiş:   1 korunur, 2 silinir, 3 korunur, 4 silinir, 5 korunur, 6 silinir, 7 korunur. 
(Dizinin son hali: 1 3 5 7)
İkinci geçiş:  1 silinir, 3 korunur, 5 silinir, 7 korunur. 
(Dizinin son hali: 3 7)
Üçüncü geçiş:  3 silinir, 7 korunur. 
(Dizinin son hali: 7) 
Geriye kalan son sayı 7’dir.
 
Buna göre oyunda $ N = 160 $ için geriye kalan son sayı kaçtır?
$A) 65 $

$B) 83 $

$C) 101 $

$D) 129 $

$E) 157 $

$Cevap : A$

Şimdi (IE = ilk eleman , SE = Son eleman)

$Döngü 1$

$1,2,3,...,160$  dizisinde $2n+1$ korunur ve $2n$ silinir. Yeni döngüde$ IE = 1 $ $SE = 159$

$1,3,5,...,159$ dizisinde $4n-1$ korunur ve $4n+1$ silinir. Yeni döngüde$ IE = 3 $ $SE = 159$

$3,7,11,...,159$ dizisinde $8n-1$ korunur ve $8n+3$ silinir. Yeni döngüde$ IE = 7 $ $SE = 159$

$7,15,23,...,159$ dizisinde $16n-1$ korunur ve $16n+7$ silinir. Yeni döngüde$ IE =15 $ $SE = 159$

$15,31,47,...,159$ dizisinde (Bir fikrim yok) Yeni döngüde$ IE = 31 $ $SE = 159$

$31,63,95,127,159$ dizisinde (Bir fikrim yok). Yeni döngüde$ IE = 63 $ $SE = 127$

$63,127$ dizisinden $127$ silinir ve geriye $63$ kalır.

Nerede hata yaptım bilmiyorum.Yardım ederseniz sevinirim.

Comments

160'dan sonra olecek olan 3 degil mi?

---

Ilk tur sonunda $159$ korundu $160$ silindi ikinci tura başlarken $1$'in korunması gerekmez mi? 

Verdiğin $n=7$ örneğinde ikinci tura başlarken 1'in silinmesinin sebebi $7$'nin tek sayı olmasıydı. Ama $160$ çift.

---

Evet ikinci tur başlarken hata yapmışım.3 Silinmeliydi.

Answer 1

Sana soyle bir yontem onereyim:

$n$ kisi icin son kalacak tek kisiyi $f(n)$ olarak adlandiralim. Zaten fonksiyon da verir bize...

Diyelim ki  $n\ge 1$ icin $2n$ kisi baslasin.

Ilk turdan sonra $$1,3,\cdots,2n-1$$ kalir ve $n$ kisilik oyunu adlari $2k-1$ yazarak baslatmis oluruz. Dolayisiyla $$f(2n)=2f(n)-1$$ ecitligini elde ederiz. 

Mesela buradan $m\ge 1$ tam sayilari icin $$f(2^m)=1$$ oldugunu gorebiliriz.

Tek sayilari sana/okuyucuya birakiyorum...

Son olarak formulize edildiginde: $n=2^m+l$ olarak $0\le l <2^m$ yazarsak $$f(n)=2l+1$$ olur. Burada $160=128+32$ oldugundan $$f(160)=2\cdot 32+1=65$$ olur.

Problemin adi `Josephus problem' olarak geciyor. Internetten de genel halini arastirabilirsiniz.

Comments

Burada https://www.youtube.com/watch?v=uCsD3ZGzMgE 

$n$'i ikilik tabana çevirip en büyük basamağı başa($2^0$'ın soluna) atacak şekilde bir yöntem gösterilmiş.

Yani şöyle oluyor:

$160 = 2^7 + 2^5$----->10100000---->1000001

$1000001 =$ $2^6+2^0$

$ = 65$

---

Dedigin tamamen ayni. 2^m+l olarak yazip 2l+1'i hesaplama..

Cunku 2^m'yi siliyor. Geriye l kalir..
Bunu bi yana kaydirmak 2 ile carpmak
sonra yanina 1 yazmak 1 eklemek..

---

Hatta bunu ikilik basamak olarak acmak da ayri bir kulfet... 

---

Hocam zaten dediğiniz şeyden geliyor. Sadece $f(n) = 2l+1$ pek akılda kalıcı olmadığını düşündüğümden yazdım.Bilmem ikilik taban bana daha eğlenceli geliyor.

---

Yok, yazmana bir soz demedim. Sadece ayni oldugunu ve biraz islemi uzattigini soylemek istedim. sonucta muhabbet ediyoruz:)

---

Hatta yazmalisin ki, pekistirelim, gelistirelim.