Gönderen Konu: Sıralamayı değiştirme sorusu  (Okunma sayısı 2020 defa)

Çevrimdışı Metin Can Aydemir

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1.280
  • Karma: +9/-0
Sıralamayı değiştirme sorusu
« : Temmuz 29, 2021, 03:48:50 öö »
$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. (Metin Can Aydemir)
Gerçek hikayeler aslında söylenmeyenlerdir.

Çevrimdışı Metin Can Aydemir

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1.280
  • Karma: +9/-0
Ynt: Sıralamayı değiştirme sorusu
« Yanıtla #1 : Ağustos 01, 2021, 05:00:31 ös »
$1,2,\dots,n$ sıralamasında $i.$ sayıya uygulanan hamle sayısı $a_i$ olsun. $1$ sayısının $n$ olması için $k\in \mathbb{Z}^+$ için $n-1+nk$ hamle yapılması gerekir. $2$ için $n-3+nk$ (aynı $k$ olmak zorunda değil) hamle gerekir ve bu şekilde ilerler. $1$ sayısını arttıran $1$'e ve $2$'ye yapılan hamlelerdir. Ortadaki bir $i$'nci sayı için ona etki eden hamleler $i-1$'inci, $i$'nci ve $i+1$'inci sıradaki sayılara yapılan hamlelerdir. Dolayısıyla $$a_1+a_2\equiv n-1\pmod{n}$$ $$a_1+a_2+a_3\equiv n-3\pmod{n}$$ ve bu şekilde ilerlersek $$\vdots $$ $$a_{n-2}+a_{n-1}+a_n\equiv n-(2n-3)\equiv 3\pmod{n}$$ $$a_{n-1}+a_{n}\equiv n-(2n-1)\equiv 1\pmod{n}$$ elde edilir. $n$ tane denkliğin ortasından itibaren sanki $n$'nin tekliğine ve çiftliğine göre durum değişiyor gibi gözüküyor ama dikkatli incelenirse her iki durumda da denkliklerin sağ tarafının ikişerli olarak azaldığı görülebilir, isterseniz ufak değerlerde deneyebilirsiniz.

İlk iki denklikten $a_3\equiv -2\pmod{n}$ ve son iki denklikten $a_{n-2}\equiv 2\pmod{n}$ bulunur. $i$'inci ve $i+1$'inci denklikleri birbirinden çıkartırsak $i=1,2,\dots,n-3$ için $a_{i+3}\equiv a_i-2\pmod{n}$ bulunur. Şimdi $a_1\equiv A$ ve $a_2\equiv B$ dersek, $$a_{3k+2}\equiv a_{3k-1}-2\equiv a_{3k-4}-4\equiv \cdots\equiv a_2-2k\equiv B-2k\pmod{n}$$ $$a_{3k+1}\equiv a_{3k-2}-2\equiv\cdots \equiv a_1-2k\equiv A-2k\pmod{n}$$ bulunur. Eğer $n\equiv 2\pmod{3}$ ise $n=3k+2$ olacak şekilde bir $k$ tamsayısı vardır. $$a_{n-1}+a_{n}\equiv a_{3k+1}+a_{3k+2}\equiv A+B-4k\equiv 1\pmod{n}$$ $$a_1+a_2\equiv A+B\equiv -1\pmod{n}$$ olacaktır. Bu iki denklikten $$A+B-4k\equiv -1-4k\equiv 1\pmod{n}$$ $$3\equiv -3-12k\equiv-3-4(3k+2-2)\equiv -3+8\equiv 5\pmod{n}\Longrightarrow 2\equiv 0\pmod{n}$$ olur. $n\geq 3$ olduğundan bu mümkün değildir. Dolayısıyla $n,n-1,\dots,2,1$ sıralaması elde edilemez.

Sanırsam $a_{n-2}=a_{3k}\equiv 2\pmod{n}$ ve $a_3\equiv -2\pmod{n}$ olmasından da benzer bir çelişki elde edilebiliyor.

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

Gerçek hikayeler aslında söylenmeyenlerdir.

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal