Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: senior - Ağustos 14, 2011, 06:32:54 ös
-
A,B,C,D,E,F diye birbirinden farklı 6 tane sayıyı sıralamak istiyoruz. Sayıların tam değerlerini bilmemekle beraber, birbirleri ile karşılaştırabiliyoruz. Bu 6 sayıyı sıralamak için (Ör: F < A < B < E < D < C ) en şanssız durumda minimum kaç karşılaştırma yaparız?
-
biraz daha detaylı düşündüm
-
f(k) - f(k-1) güzel bir algoritma :) Aslında cevap biraz daha az, çözümün bir parçasında yine bulduğunuz algoritmayı kullanabilirsiniz. Mesele
f(5)'in aslında 7 olduğunu bulmak. Sonuçta 5 sayı için teorik limit 26 < 5! < 27, yani 7 karşılaştırma. Sonrasında bulduğunuz bağıntı ile asıl cevap olan f(6) = 10 bulunur. ( 29 < 6! < 210 )
-
Güneş hocam, 5 farklı sayıyı 7 işlemde sıralayan algoritmanızı paylaşabilir misiniz?
-
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.
-
Teşekkürler hocam. Bir türlü 8'in altına inememiştim.
-
Önemli değil. Aslında bu tür sorular deneme yanılma soruları gibi gözüküyor, ondan tam cevaptan emin olunamıyor ama göründüğü gibi öyle değil :) Ayrıca bu soru UMO 2004'te 4 sayı için sorulmuştu.