Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
544 kez görüntülendi

$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$

Lisans Matematik kategorisinde (127 puan) tarafından  | 544 kez görüntülendi
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.
20,275 soru
21,807 cevap
73,489 yorum
2,450,930 kullanıcı