Sıralamayı değiştirme sorusu

Question

$n\geq 3$ tamsayısı için bir tahtaya $1,2,3, \dots ,n$ sayıları artan sırada yazılıyor. Her hamlede bir sayı seçiliyor ve kendisi, solundaki ve sağındaki ilk sayılar, eğer varsa, $1$ arttırılıyor. Eğer arttırılacak sayılardan birisi $n$ ise $n+1$ değil $1$ oluyor. Buna göre, $n\equiv 2\pmod{3}$ ise sonlu hamle sonrasında $n, n-1, \dots, 2,1$ sıralamasının elde edilemeyeceğini gösteriniz.

Gözlemim ve ek sorum:  $n\not\equiv 2\pmod{3}$ ise $n, n-1, \dots, 2,1$ sıralaması elde edilebiliyor. Peki en az kaç hamlede bu sıralamayı elde edebiliriz? Ufak değerlerde $5n-12$ gibi gözüküyor ama elimde bir ispat yok.

$n=3$ için örnek, $1,2,3\xrightarrow{(1)} 2,3,3\xrightarrow{(1)} 3,1,3\xrightarrow{(3)} 3,2,1$

Comments

Oyunu ttam anlamadım örnekle tekrar anlatır mısınız?

---

$n=4$ için örnek (ok üzerindeki sayı, kaçıncı sıradaki sayıya hamle yapıldığını gösteriyor) $$1,2,3,4\xrightarrow{(1)} 2,3,3,4\xrightarrow{(2)} 3,4,4,4\xrightarrow{(2)} 4,1,1,4$$ $$\xrightarrow{(3)} 4,2,2,1 \xrightarrow{(3)} 4,3,3,2 \xrightarrow{(4)} 4,3,4,3 \xrightarrow{(4)} 4,3,1,4 \xrightarrow{(4)} 4,3,2,1$$

$8$ hamlede sıralamayı tersine çevirebiliyoruz. $n=5$ için yapılamıyor.

---

Elemanları teker teker inceleyelim mesela n=4 için 2. sıradaki sayıyı alalım.

Tanım: Hamle yapıldığı zaman n. elemanı etkileyen elemnlar kümesine n'nin etki kümesi diyelim.

Örn: 2'nin etki kümesi=(1,2,3)

Tanım: Bir oyunda oyuncu kaç defa n'in etki kümesindeki bir elemana hamle yapmışsa ona n'in bu oyundaki derecesi diyelim.(Der(n))

Lemma1: Diyelim elimizde bitirilmiş(Yani sıralama tersine çevrilmiş) k elemanlı bir oyun var. Her n için Der(n)=n-1 (mod k)

Bariz.

Tanım:der(n)=n'ye yapılan hamle sayısı   

Lemma2: $$\sum_{j\in n'nin etki kümesi}der(j) = Der(n)$$

Bariz.

Amaç 1:der(n)'ler için Lemma 1 tarzı bir denklem bulmak. k tane bilinmeyen ve Lemma 2'den gelen k tane modüler denklem var. Eğer bir k için bu denklemi çözemezsek bu k için bu oyunun asla bitemeyeceği anlamına gelir. Oyunda hamlelerin sırası önemsiz olduğundan kaç defa bir elemana hamle yapacağını (der(n)) hesaplamak oyunu tarif etmiş oluyor.