5 sayının (A,B,C,D,E) sıralaması 5! = 120 şekilde olabilir.
- A ve B'yi karşılaştıralım. A < B durumu ile B < A durumu simetriktir. Yani ABCDE'nin permütasyonlarının 60 tanesinde A B'den önde, kalan 60 tanesinde ise B A'dan öndedir.
- Benzer şekilde C < D olarak varsayabiliriz. Yani Durum sayımız 30'a indi.
- Şimdi yapacağımız karşılaştırmayı durumu (yapabilirsek) 15 - 15 'e bölecek şekilde seçmemiz lazım.
- A < B ve C < D olduğunu biliyoruz. A ile C'yi karşılaştırdığımızda durum yine simetriktir. Yani A < C için 15, C < A için yine 15 olasılığımız var. Etti 3 karşılaşırma.
- A,B,C ve D arasında 3 farklı durum söz konusudur:
A < B < C < D
A < C < B < D
A < C < D < B
E'yi de araya herhangi bir yere (5 yerden) katabiliriz. Yani 3 x 5 = 15 olasılığımız mevcut.
- Sıradaki(Dördüncü) karşılaştırmada E'yi hesaba katmaz isek en şanssız durumda bu sıralamalardan 2 tanesi kalır. Bu da 10 olasılık eder. 10 > 23 olduğundan dolayı en az 4 tartı gerektirir. Yani 7 karşılaştırmada işi bitiremeyiz. O zaman E sayısını buradakilerden birisi ile karşılaştırmamız gerekmektedir.
- A'yı seçersek kötü bir seçim yapmış oluruz. Çünkü sıralamaların bir çoğunda A en küçük olduğu için A < E sonucunda 8'den fazla olasılık çıkar. Bu yüzden ortalarda bir tane seçmeliyiz. En ideali C'dir.
A < B < C < D sıralamasında C < E --> 2 olasılık (C'nin sağında 2 tane boşluk var E'yi yerleştirebileceğimiz)
A < C < B < D sıralamasında C < E --> 3 olasılık
A < C < D < B sıralamasında C < E --> 3 olasılık
Yani toplam 8 olasılık. C > E için de 7 olasılık kalır. Yani uzayı yarıya yakın böldük. 15 = 7 + 8.
- Şanssız durum C < E olduğundan bu durumu inceleyelim. Geriye kalan 8 olasılık şöyle sıralanabilir:
------------------------------------------------------------------------------------------------------------------------------------
A < B < C < D ABCDE A < C < B < D ACBDE A < C < D < B ACDBE
ABCED ACBED ACDEB
ACEBD ACEDB
------------------------------------------------------------------------------------------------------------------------------------
- Kaldı sadece 3 tane karşılaştırma. Uzayda 8 eleman var, yapacağımı karşılaştırma uzayı tam olarak 2'ye bölmeli.
Yani seçeceğimiz 2 sayı X ve Y bu 8 olasılığın 4'ünde X < Y, diğer 4'ünde X > Y sonucu vermeli. Biraz dikkat edilirse
E ve D sayıları bu koşulu sağlar.
- E < D olsun. Kalan olasılıklar: ABCED, ACBED, ACEBD, ACEDB --> buradan B ve E'yi karşılaştırırsak yine uzayı 2'ye böleriz.
B < E --> ABCED, ACBED --> B ve C karşılaştırması sonucu verir.
B > E --> ACEDB, ACEBD --> B ve D sonucu verir.
- E > D durumu da benzer.
- Yani 5 sayıyı toplam 7 karşılaştırma da sıralayabildik. O zaman 6 sayıyı da 10 karşılaştırma da sıralayabiliriz.
Bu da 9 < log26! < 10 olduğundan, teorik limitimize uygundur.
