Latin Kareler {çözüldü}

[NazifYILMAZ]

Yardimci olan arkadaşlara teşekkür ederim.

[NazifYILMAZ]

Arkadaşlar  bu çözüm için yorumlarınızı alabilirmiyim

[Squidward]

İlk satıra , $4!$ şekilde koşulsuz yerleştiririz 4 boyayı, ikinci sıraya hiçbir boya bir önceki sırasına gelmeyecek şekilde içerme dışarmayla; $4! - \binom{4}{1} \cdot 3! + \binom{4}{2} 2! - \binom{4}{3} 1! + \binom{4}{4} = 12$ farklı şekilde "derangement" yapılabilir. Genelliği bozmadan ilk satırda $\text{MSKY}$ olsun, ikinci satırda da $\text{SKYM}$ olsun, üçüncü satırda ilk boya $\text{K}$ olursa son sütündaki $\text{S}$ olmak zorunda olur, son sütündaki $\text{S}$ olursa, üçüncü sütündaki $\text{M}$ olmak zorunda olur, gerisine tek durum olduğu açıktır yani üçüncü satırdaki ilk boya tüm satırı belirleyecektir, son satır da açık bir şekilde belli olacaktır en sonunda yani üçüncü ve dördüncü satır için $2$ durum vardır, toplam durum sayısı $24 \cdot 12 \cdot 2 = 576$'dır.


Yanlışım yoksa cevabı doğru bulmuşsunuz ama argümanınızın doğruluğundan emin olamadım detaylı açıklarsanız yardımcı olabilirim.

[Lokman Gökçe]

Arkadaşlar  bu çözüm için yorumlarınızı alabilirmiyim

Nafiz bey, cevabı doğru vermiş olsa da çözüm yolu doğru değildir. Çünkü ok üzerindeki renkler hep aynı olmak zorundaymış gibi işlem yapılmış. Böyle bir zorunluluk yoktur. Ayrıca gönderdiğiniz çözümdeki üçüncü satıra bakılırsa $KSMS$ yazılıdır. Yani $S$ (sarı renk) aynı satırda iki kez kullanılmıştır, probleme göre bu yasaktır.

Squidward'ın çözümü ise doğrudur.

[Eray]

İlk satıra , $4!$ şekilde koşulsuz yerleştiririz 4 boyayı, ikinci sıraya hiçbir boya bir önceki sırasına gelmeyecek şekilde içerme dışarmayla; $4! - \binom{4}{1} \cdot 3! + \binom{4}{2} 2! - \binom{4}{3} 1! + \binom{4}{4} = 12$ farklı şekilde "derangement" yapılabilir. Genelliği bozmadan ilk satırda $\text{MSKY}$ olsun, ikinci satırda da $\text{SKYM}$ olsun, üçüncü satırda ilk boya $\text{K}$ olursa son sütündaki $\text{S}$ olmak zorunda olur, son sütündaki $\text{S}$ olursa, üçüncü sütündaki $\text{M}$ olmak zorunda olur, gerisine tek durum olduğu açıktır yani üçüncü satırdaki ilk boya tüm satırı belirleyecektir, son satır da açık bir şekilde belli olacaktır en sonunda yani üçüncü ve dördüncü satır için $2$ durum vardır, toplam durum sayısı $24 \cdot 12 \cdot 2 = 576$'dır.


Yanlışım yoksa cevabı doğru bulmuşsunuz ama argümanınızın doğruluğundan emin olamadım detaylı açıklarsanız yardımcı olabilirim.

Çözüme bir itirazım olacak. Kaçırdığım/yanıldığım bir nokta varsa affola.

İlk iki satırdaki dizilim genelliği bozmayacağı iddia edilerek uygun bir biçimde dizilmiş, ardından 3. ve 4. satırlar için $2$ farklı durum mümkün olduğu söylenmiş.

Kanımca bu düşünce yanlış, çünkü ilk iki satırın farklı dizilimleri için 3. ve 4. satır için mümkün durum sayısı değişebiliyor. İki örnekle göstereyim:

Örnek 1: İlk satır MSKY, ikinci satır SMYK iken üç ve dördüncü satır için YKSM+KYMS, YKMS+KYSM, KYSM+YKMS, KYMS+YKSM olmak üzere $4$ farklı mümkün durum vardır.

Örnek 2: (Squidward'ın ele aldığı durum) İlk satır MSKY, ikinci satır SKYM iken üç ve dördüncü satır için KYMS+YMSK ve YMSK+KYMS olmak üzere $2$ farklı mümkün durum vardır.

[Squidward]

İlk satıra , $4!$ şekilde koşulsuz yerleştiririz 4 boyayı, ikinci sıraya hiçbir boya bir önceki sırasına gelmeyecek şekilde içerme dışarmayla; $4! - \binom{4}{1} \cdot 3! + \binom{4}{2} 2! - \binom{4}{3} 1! + \binom{4}{4} = 12$ farklı şekilde "derangement" yapılabilir. Genelliği bozmadan ilk satırda $\text{MSKY}$ olsun, ikinci satırda da $\text{SKYM}$ olsun, üçüncü satırda ilk boya $\text{K}$ olursa son sütündaki $\text{S}$ olmak zorunda olur, son sütündaki $\text{S}$ olursa, üçüncü sütündaki $\text{M}$ olmak zorunda olur, gerisine tek durum olduğu açıktır yani üçüncü satırdaki ilk boya tüm satırı belirleyecektir, son satır da açık bir şekilde belli olacaktır en sonunda yani üçüncü ve dördüncü satır için $2$ durum vardır, toplam durum sayısı $24 \cdot 12 \cdot 2 = 576$'dır.


Yanlışım yoksa cevabı doğru bulmuşsunuz ama argümanınızın doğruluğundan emin olamadım detaylı açıklarsanız yardımcı olabilirim.

Çözüme bir itirazım olacak. Kaçırdığım/yanıldığım bir nokta varsa affola.

İlk iki satırdaki dizilim genelliği bozmayacağı iddia edilerek uygun bir biçimde dizilmiş, ardından 3. ve 4. satırlar için $2$ farklı durum mümkün olduğu söylenmiş.

Kanımca bu düşünce yanlış, çünkü ilk iki satırın farklı dizilimleri için 3. ve 4. satır için mümkün durum sayısı değişebiliyor. İki örnekle göstereyim:

Örnek 1: İlk satır MSKY, ikinci satır SMYK iken üç ve dördüncü satır için YKSM+KYMS, YKMS+KYSM, KYSM+YKMS, KYMS+YKSM olmak üzere $4$ farklı mümkün durum vardır.

Örnek 2: (Squidward'ın ele aldığı durum) İlk satır MSKY, ikinci satır SKYM iken üç ve dördüncü satır için KYMS+YMSK ve YMSK+KYMS olmak üzere $2$ farklı mümkün durum vardır.

Haklısınız, ilginçtir soruya bir daha bakmak için defterimi açtığımda tam da karşıt örnek olarak verdiğiniz örneği defterime yazdığımı ama nedense incelemediğimi farkettim , çözümü şöyle düzeltmeye çalıştım:

İlk satırı koşulsuz $4$ renkle $4!$ farklı şekilde boyarız, ikinci satırı ise hiçbir boya orijinal yerinde bulunmayacak şekilde içerme dışarmayla: $4! - \binom{4}{1} \cdot 3! + \binom{4}{2} 2! - \binom{4}{3} 1! + \binom{4}{4} = 12$ farklı şekilde boyarız fakat $3.$ satırda birinci sütuna yerleştirdiğimiz renk, o rengin ve birinci sütunda, $4.$ satırdaki, ilk yerleştirdiğimiz renkle belirlenen rengin bulunduğu yerleri belirler $1.$ sütunda olmayan, yerleştirdiğimiz rengin belirlediği renkler farklı sütundaysa o sütunlarda tek bir boş yer kaldığından o sütunlar belirlenmiş olur ve böylece bir durum vardır fakat aynı sütundaysa geriye kalan $4$ kareyi $2$ renk ile sol üste koyulan renge göre birer farklı şekilde, toplamda $2$ farklı şekilde boyanır. Öyleyse, $12$ durumdan $3.$ satırda ilk sütuna rengin koyulmasıyla ilk sütunda olmayan yerleri belirlenen renklerin aynı ve farklı sütunda olanlarını ayrı hesaplamalıyız, aynı sütunda olmaları durumu, iki sütunun(dolayısıyla diğer iki sütunun da) ilk iki satırlarının aynı renkleri bulundurmasıyla olur, böyle durumlar $3.$ satırda ilk sütun $3$ renkten biriyle boyandıktan sonra tektir yani $3$ tanedir. Yani, $12$ durumun $9$'unda $3.$ satırın ilk sütununa koyulan $2$ rengin herbiri için tek durum, $3$ durumda ise $2$ rengin herbiri için $2$ durum vardır, sonuç olarak durum sayısı: $24\cdot(9\cdot2+3\cdot4) = 720$'dir.

Yer-renk, satır-sütun derken biraz karışık oldu, anlatımda ya da çözümde hala hata yoktur umarım

[Lokman Gökçe]

Cevap $576$ dır.

Aynı problemi daha önceki zamanlarda (4-5 yıl olmuştur) kurgulayıp forumdan senior arkadaşımıza da bilgisayar programı ile kontrol ettirmiştir. Benim yaptığım çözümde de İlk satır $4!$ ve ikinci satır ise $D_4=12$ yolla boyanabiliyor.

Buraya kadar bakınca Squidward'ın çözümünün gerisini kontrol etmedim. Sonucu da doğru bulduğu için hata olmadığını düşündürdü. Hata varsa da ufak bir düzeltme ile bu problemi giderebiliriz diye düşünüyorum. Kendi çözümümü de PDF olarak hazırlamıştım. Bulursam onu da paylaşayım. İyi çalışmalar.

[Eray]

Şu ana kadar fark etmediğimiz bir hata var:

$D_4 = 4! - \binom{4}{1} \cdot 3! + \binom{4}{2} 2! - \binom{4}{3} 1! + \binom{4}{4} =\color{red}9$

[Squidward]

İlk çözümümde şansa bir şekilde $576$ cevabını bulmuşum, $D_4$'e eşit olan $4! - \binom{4}{1} \cdot 3! + \binom{4}{2} 2! - \binom{4}{3} 1! + \binom{4}{4}$ ifadesi $12$'ye değil, $9$'a eşit ondan dolayı bir sorun olmuş, 2. çözümde son aşama $24\cdot(6\cdot2 + 3\cdot 4) = 576$ olmalıydı. (tam da ben yazıyordum @Eray da yazdı)

Problem de Latin Squares(https://en.wikipedia.org/wiki/Latin_square) olarak geçiyor, genel formül 1992'de bulunmuş fakat problem en az Euler kadar eski.

[Lokman Gökçe]

Notlarıma baktığımda, Latin Kareler problemiyle tarihsel gelişim sürecinden habersiz olarak $2015$ te uğraşmışım. $n=4$ için çözümünü aşağıda resim olarak ekliyorum.

Problemle İlgili Bulgularım:

1. $2\times 2$ ve $3\times 3$ problemleri kolaylıkla çözülebiliyor ve cevapları sırasıyla $2!\cdot D_2=2\cdot 1 =2$ ve $3!\cdot D_3=6\cdot 2 =12$ dir.

2. $2$ satırlı ve $n$ sütunlu dikdörtgenin $n$ renk kullanarak, her satırda farklı bir renk ve her sütunda farklı bir renk kullanarak $n!\cdot D_n$ yolla boyayabileceğimizi biliyoruz. Bu tür bir problemi www.hayatmatematiktir.com sitesinde verilen sonlu matematik kitabında görmüştüm. Diğer problemleri düşünmeme sebep olan problem de bu kitaptaki $2\times 5$ türü problemdir.

3. $4\times 4$ problemi aşağıda detaylı çözümde eklediğim gibi $576$ sonucuna sahiptir. Bariz olarak, $3$ satırlı $4$ sütunlu dikdörtgeni de $4$ renkle, her bir satırda farklı renkler ve her bir sütunda farklı renkler kullanmak koşuluyla $576$ yolla boyayabiliriz. Çünkü $4\times 4$ ün son satırı tek türlü boyanabilir. $4\times 4$ ve $3\times 4$ problemleri özdeştir.

4. $3\times 5$ probleminin, $4\times 4$ probleminde olduğu gibi bir yolla çözülebilir olduğunu gördüm. İlk satır $5!$ yolla, ikinci satır $D_5=44$ yolla boyanabiliyor. Fakat bu aşamadan sonra zorluk başlıyor. Üçüncü satırı boyamak için $44$ tane permütasyon fonksiyonunu ayrık devirlerin çarpımı biçiminde yazıp kategorilendirmek gerekiyor. Burada ayrık devirler $f_1=(ab)(cde)$ veya $f_2=(abcde)$ biçiminde olmak zorundadır. $f_1=(ab)(cde)$ türündeki bir permütasyon için üçüncü satırı boyama sayısı sayarak hesaplanır: $x_1$ tane olsun. $f_2=(abcde)$ türündeki bir permütasyon için üçüncü satırı boyama sayısı sayarak hesaplanır: $x_2$ tane olsun. $f_1=(ab)(cde)$ ve $f_2=(abcde)$ türündeki permütasyonların sayısı sırasıyla $y_1$, $y_2$ ($y_1+y_2=44$) olmak üzere $3\times 5$ probleminin çözümü özetle $5!\cdot(x_1y_1+x_2y_2)$ dir.

5. Yukarıda verdiğim yolda $x_1,x_2,y_1,y_2$ değerlerini pratik olarak hesaplayamadığım için $n\geq 6$ için $3\times n$ probleminin genel çözümü için uğraşmadım. $n=6$ durumunda $D_6=265$ tane permütasyon fonksiyonunu ayrık devirler olarak $(ab)(cd)(ef)$, $(abc)(def)$, $(ab)(cdef)$, $(abcdef)$ biçimlerinde yazıp her bir türün boyanma sayısını hesaplamamız gerekir. Şahsen $3\times n$ problemi için kısa bir yol göremedim. Genel halde $n\times n$ (Latin Kareler) problemi çözüldüğüne göre $3\times n$ probleminin de çözülmüş olmasını bekleyebiliriz. Ayrıca wikipediada verilen bilgiye göre, $n\times n$ Latin karelerin sayısını kolayca hesaplayabilen bilinen bir formül de yokmuş. Bu bilgi, yaptığımız hesapların giderek uzamaya başlamasını daha anlaşılabilir yapıyor.

[NazifYILMAZ]

teşekkür ederim Lokman  hocam. Sandıklı Park günlerini çok özledik.