Matematik Ev İşlerinize Nasıl Yardım Eder? : Çoraplarınızı Sıralamanın Farklı Bir Yolu

Eğer çoraplarınız çamaşır makinesinden karmakarışık çıktıysa onları nasıl düzenlersiniz? Daha düzenli bir dizi elde etmek için piramit misali yığılmış çorapları aynı hizada olacak şekilde sıralamak işinizi daha kolay bir hale getirecektir. Ancak, ne yazık ki, şimdi farklı şekillere sahip çorapların hepsi karıştı ve daha da kötüsü, nasıl yapacağınızı bildiğiniz tek şey x. çorabı y. sıraya koyarak sonuçta aynı şekle sahip olan çorapları yan yana getirmeye çalışmak.

Yapacağımız işlem kabataslak haliyle bir sıralama olacağından bunu permütasyon kullanarak yapabiliriz. Çoraplarımızı türüne göre 1,1,2,2,3,3,...,n,n olarak sıraladığımız takdirde 1,1,2,2,3,3,...,n,n sayılarını içeren ve P ile göstereceğimiz permütasyonumuzu, {1,1,2,2,3,3,...,n,n} sayılarını içeren bir liste olarak kabul edebiliriz. Örneğin 3,1,4,2,1,4,2,3 sayı dizisi {1,1,2,2,3,3,4,4} sayılarını içeren bir permütasyondur. Şimdi ise P permütasyonumuzu tanım kümesindeki her sıra numarasını çorap şekillerine verdiğimiz sayıları içeren görüntü kümesine götüren bir fonksiyon olarak hayal edelim. Dolayısıyla eğer permütasyonumuzu yukarıdaki özellere sahip P fonksiyonu olarak isimlendirirsek, P listesinin i konumundaki sayı için P(i) yazabiliriz. Örneğin eğer P listemiz 3,1,2,1,2,3 ise P(3)=2 olur.

Yukarıdaki bilgiler ışığında görevimiz, çamaşır makinemizin bize verdiği permütasyonumuz P'yi 1,1,2,2,3,3,...,n,n şekline çevirmektir. Çoraplarımızı soldan sağa bir dizi olarak sıraladığımızdan bunu, permütasyonumuzun en soldaki bölümünü tekrar tekrar değiştirerek yapabiliriz. Bu işlemi genel hatlarıyla ifade edecek olursak yapacağımız işlem ilk önce bir i noktası seçmek ve buradaki çorabı permütasyonumuzun en soluna koymaktır. Dolayısıyla yeni permütasyonumuz şuna dönüşür:

$P(i),P(i-1),...,P(1),P(i+1),P(i+2),...,P(2n)$

Ancak çoraplarımız çok karışık olduğundan sadece bir çorabın yerini değiştirmek bize istediğimiz sonucu vermeyecektir. Dolayısıyla bu işlemi yeni seçtiğimiz bir j noktası için de yapmamız gerekir ve bu böyle tüm çoraplarımız sıralanana kadar devam eder. Peki eğer 2n kadar çorabımız (ve bunun sonucu olarak 2n uzunluğunda bir permütasyonumuz) varsa bu permütasyonumuzu 1,1,2,2,3,3,...,n,n şekline en kolay yoldan getirmek için yapabileceğimiz kaç farklı yer değiştirme vardır?

Bir Örnekle Başlayalım

Kolay bir sıralama yöntemi için aşağıdaki yöntemi izleyebiliriz:

1. Permütasyonumuzun ilk halindeki ilk sayının eşini bulun. Burada bahsedilen sayı permütasyonumuzun en solundaki sayıya eşittir. Yazımızın ilerleyen bölümlerinde değineceğimiz zor sıralamalarda tüm sayılar yer değiştirebilir ve dolayısıyla en soldaki çorap en sağa geçebilir. Bu yüzden ilk olarak bu sayımızın eşini bulmak işimizi kolaylaştıracaktır. Buna j pozisyonundaki k sayısı diyelim.
2. j pozisyonumuzda bulunan sayımızı permütasyonumuzun en soluna koyun. Böylece k sayımızın yeni konumu 1 olur.
3. Yeni permütasyonumuzda (varsa) en çok karmaşıklığa neden olan parçayı bulun. Bu parça, kendisi aynı sayı numarasına sahip diğer parçanın yanında olmadığı gibi aynı sayı numarasına sahip olan iki parçanın arasına girmiş olabilir. Böylece o sayıyı yeniden yerleştirmek için yaptığınız hamle bahsi geçen iki parçayı da düzeltecektir.
4. Diğer sayıların da yerlerini değiştirerek devam edin.

Şimdi P=3,1,4,2,3,2,4,1 şeklinde 4 çorabımız olduğunu varsayalım. Bu permütasyondaki hem en baştaki sayının eşiti olan hem de en çok karmaşıklığa sebep olan parça j=5 pozisyonundaki k=3 sayısıdır. Gerekli düzeltmeyi yaptığımızda yeni permütasyonumuzu P' ile gösterirsek P'=3,3,1,4,2,2,4,1 permütasyonunu elde ederiz. Devamında yeni j değerleri için sırasıyla:

1. j=3 pozisyonundaki k=1 sayısını
2. j=8 pozisyonundaki k=1 sayısını
3. j=8 pozisyonundaki k=4 sayısını
4. j=5 pozisyonundaki k=4 sayısını

seçersek en son elde edeceğimiz sıralama P'''''=4,4,1,1,3,3,2,2 olacaktır. Buradaki amacımız her bir çorabı diğer eşiyle yan yana getirmek olduğundan sıralamamızdaki sayılarımızın büyüklük/küçüklük değerleri bizim için bir anlam ifade etmez (sonuçta onları sadece şekilleri belirtmek için seçmiştik).

Dolayısıyla ilk bölümümüzdeki sorumuzun cevabını bu örnek üzerinden düşünürsek, cevabı bulmaya her sayının ona eşit olan diğer bir sayıyla yan yana gelebilmesi için en fazla iki değişiklik yapmamız gerektiğini hatırlayarak başlayabiliriz, dolayısıyla sorumuzun cevabı bir tane ''x2'' değeri içermelidir. Devamında ilk yer değiştirmemiz olan j=5 konumunda k=3 sayısında yapılan bir değişiklikte j=4 ile j=6 konumlarındaki k=2 sayılarının otomatikman yan yana gelmesi hakkında düşünmeliyiz, bu yüzden düzenli olmayan sayılarımız sadece k=1 ve k=4'tür. Her birinden iki tane olduğundan hangisini seçeceğimiz ''x4'' şeklinde cevabımıza eklenir. Her şeyi hesaba kattığımızda örneğimiz için maksimum çevirme sayımız:

$2.4=8$

olarak bulunur. Ama bu örneğimizde ilk sayımızın eşiti aynı zamanda en çok karmaşıklık yaratan sayıya eşitti ve bu k=2 sayısını düzeltmemiz için gereken hesaplamamızı ortadan kaldırdı. Yani her zaman bu kadar kolay olmayabilir. Bu durumda çamaşır makinesinin bize bahşettiği en zor permütasyonun kaç çözümü olur?

Kolaydan Zora...

Bir önceki permütasyonumuzda, birbiriyle aynı olan iki sayıyı yan yana getirmek için ilk değişikliğimizi yaptığımızda, otomatikman başka iki aynı sayıyı da yan yana getirmiş olduk. Sonuç olarak bir permütasyonda yapacağımız pozisyon değişikliklerinin diğer iki aynı sayının yan yana gelmesi sonucunu beraberinde getirmediği şekildeki permütasyonların diğerlerine nazaran daha zor olduğunu düşünmek mantıklıdır. Yeni bir P=4,1,3,2,4,1,3,2 permütasyonu buna örnek gösterilebilir. Bu örneğimizdeki amacımız en çok karmaşıklığa yer açacak sayının elde edilememesidir. En zor durumumuz için aynı sayı değerlerinin birbirlerine maksimum uzaklıkta olması gerekir. Ancak tüm sayılar aynı anda permütasyonumuzun en sağında ve en solunda olamaz. Bu yüzden tüm sayılarımızın eşleri arasındaki uzaklık aynı olmalıdır. Bu permütasyonumuzu sıralamak için gereken işlemlerimiz kabaca şöyledir:

1. Permütasyonumuzun ilk halindeki ilk sayının eşini bulun. Bu örneğimizde j=1 pozisyonundaki k=4 sayımız permütasyonumuzun ilk sırasıdır. Dolayısıyla eşi j=5 pozisyonundaki k=4 olacaktır.
2. Yan yana getirmek istediğiniz ikinci bir k sayısını seçin ve o sayıyı en sola getirdikten sonra eşitini en sona getirin.
3. Tüm çoraplar sıralanana kadar 2. işleme devam edin.

Yukarıdaki uyguladığınızda elde edeceğiniz aynı şekildeki tüm çorapların yan yana olduğu sıralama için:

$C(6,1).C(4,1)=24$

seçenek vardır. Ama her zaman 4 çorabımız olmak zorunda değil. O zaman nasıl hesaplarız?

... Ama Hiç Bu Kadar Kolay Olmamıştı

Yazımızın en başında bahsettiğimiz gibi P permütasyonumuzu {1,1,2,2,3,3,...,n,n} sayılarını içeren bir liste olarak kabul edebiliriz. Bir önceki örnekten yola çıkarak elde edebileceğimiz en zor permütasyon P=1,2,3,...,n,1,2,3,...,n olur. Bu durumda yukarıdaki işlemleri bu örneğimize uygularsak tüm çorapların yan yana olduğu sıralama için elde edeceğimiz maksimum çevirme sayımız:

$C(n-2,1).C(n-4,1).C(n-6,1)....C(4,1)$

olacaktır. Bu durumda eşitliğimizi aşağıdaki gibi de gösterebiliriz:

$\mathrm{4.6.8....}(n-4).(n-2)$

Kaç tane çorabımız olursa olsun hepsi için bir çift iki tane çoraptan oluşacağından (eğer bir tanesini kaybedecek kadar şanssız değilseniz) denklemimizi şu şekilde yazabiliriz:

$2[\mathrm{2.3.4....}(\frac{n-4}{2})(\frac{n-2}{2})]=2.(\frac{n-2}{2})!$

Hayatın içindeki küçük sorunları bu şekilde anlamaya çalışmak eğlencelidir, aynı zamanda bu anlamlandırma çabası zorlukları farklı bir bakış açısıyla görüp daha kolaya indirgemeye yardımcı olur. Ancak gerçekte çamaşır makinesinden çıkan çorapları düzenlemek bu kadar eğlenceli olmayabilir. Bu durumda annenize danışabilirsiniz. Hesaba katmadığımız daha kolay yöntemleri olması muhtemeldir.