kombinatorik en küçük değer sorusu {Çözüldü}

[sarmaticus]

Dedektif  her gün aralarında suçlu ve suçun bir tanığı bulunan $80$ kişiden birini veya daha fazlasını ofise davet edebilir ve onlarla dava ile ilgili konuşabilir. Dedektif eğer davet edilenler arasında tanık varsa ancak suçlu yoksa tanığın suçlunun kim olduğunu söyleyeceğini biliyor. Bu yöntemi izleyen dedektif en az kaç günde kesin olarak suçluyu bulabilir?

[Lokman Gökçe]

Çözüm Öncesi Motivasyonu:

Dedektif suçluyu $80$ günde kesin olarak bulabilir. Her gün bir kişiyi çağırır ve en kötü ihtimalle, tanık olan kişi ifade verecekler listesinde son sıraya düşebilir.

Peki $2$ şer kişilik $40$ grup oluşturursak ne olabilir? Gruplar $\{ a_1, b_1\}, \{ a_2, b_2\}, \dots , \{ a_{40}, b_{40}\}$ şeklinde olsun. Bunların araştırılması $40$ gün sürer. Eğer bu gruplardan herhangi bir sonuç alınamazsa tanık ile suçlu aynı grupta bulunuyor demektir. Grupları farklı bir yöntemle, örneğin, $ \{ a_1, a_2\},  \{ a_3, a_4\}, \dots  \{ a_{39}, a_{40}\}, \{ b_1, b_2\},  \{ b_3, b_4\}, \dots  \{ b_{39}, b_{40}\}$ biçiminde oluşturursak artık suçlu ve tanık farklı gruplardadır. Bu grupların sorgulanması da $40$ gün sürer. Yine, $40+40=80$ güne ihtiyaç oluyor.

Daha az günde suçlu belirlenebilir mi? Farklı gruplandırma yöntemleri ile daha başarılı sonuçlar alınabilir belki. $80$ kişiyi $9$ gruba ayıralım.

$\{a_1,a_2,\dots ,a_9\},\{a_{10},a_{11},\dots ,a_{18}\},\dots ,\{a_{73},a_{74},\dots ,a_{80}\}$. Bunların araştırılması $9$ gün sürer. Eğer sonuç alınamazsa suçlu ve tanık aynı grupta demektir. Şimdi yeniden gruplandıralım. $\{a_1,a_{10},\dots ,a_{73}\}, \{a_2,a_{11}, \dots,a_{74} \},\dots,\{a_8,a_{17},\dots ,a_{80} \}, \{a_9,a_{18},\dots ,a_{72} \}$ gruplarında suçlu ve tanık farklı gruplardadır. Böylece $9$ güne hada ihtiyacımız var ve toplam $18$ günde suçluyu belirlemiş oluyoruz.

Daha az günde bu işlem yapılabilir mi? Yapılamaz ise neden yapılamaz? Bunlara da cevap vermemiz gerekiyor.

[Lokman Gökçe]

Çözüm[Thomas Andrews]:

Kişileri $1, 2, \dots , 80$ biçiminde numaralandıralım. $i$-inci gün ifadeye çağırılan insanların kümesi $S_i$ olsun. $n$ gün boyunca çağırılan insanların kümelerini $S_1,S_2,\dots,S_n$ ile gösteririz. 

Her $i$ kişisi için, $T_i=\{j\mid i\in S_j\}$ kümesini tanımlayalım. Yani $T_i$, $i$-kişisinin sorgulandığı günlerin listesidir.
Şimdi, verilen $i_1\neq i_2$ için, $T_{i_1}\subseteq T_{i_2}$ ise, $i_1$-kişisini davet ettiğimiz her gün, $i_2$-kişisini de davet etmiş oluyoruz.  Bu durumda, $i_1$ tanık ve and $i_2$ suçlu iken problemi çözememiş oluyoruz.

Öyleyse bir çözüm oluşması için $T_i$ ler, $\{1,2,\dots,n\}$ kümesinin altkümelerinden oluşan bir anti-zincir (antichain) olmalıdır. Diğer bir deyişle, $T_i$ alt kümelerinden hiçbiri, bir diğerinin alt kümesi olmamalıdır. Öte yandan, Sperner Teoreminden, bu şekildeki en uzun anti-zincirin uzunluğu is $\dbinom{n}{\lfloor n/2\rfloor}$ olmaktadır.

Dolayısıyla, $\dbinom94\geq 80>\dbinom84$ olduğundan gerekli gün sayısı $9$ dan daha az olamaz.

Bununla beraber, $80$ uzunluğunda bir anti-zincirden yanıt üretmek için yukarıdakileri tersine çevirebiliriz.

$\mathcal U=\mathcal U_{9,4}$ ; $\{1,\dots,9\}$ kümesinin $4$-elemanlı alt kümelerinin kümesi olsun. Bu bir anti-zincirdir ve $126=|\mathcal U|>80$ dir. Her $j=1,\dots,80$ için farklı bir $T_j\in \mathcal U$ seçeriz. Böylelikle, $T_1,\dots,T_{80}$ bir anti-zincirdir.

Nihayetinde $S_i=\{j\mid i\in T_j\},$ $i=1,\dots,9$ dersek, $S_1,\dots, S_9$ kümeleri problemimizi $9$ günde çözer.


Bazı Faydalı Notlar:

$\color{blue}\bullet$ $\dbinom93=84>80$ olduğundan $\mathcal U$ olarak $\mathcal U_{9,3}$ alabiliriz. Sadece uzunluğu $80$ olan bir anti-zincire ihtiyacımız var. Bu, toplam gün sayısını azaltmaz, ancak her kişinin dört yerine sadece üç gün içinde gelmesi gerekir.

$\color{blue}\bullet$ Genel olarak $N$ kişilik bir popülasyon için soruyu çözmek istersek, gerekli olan en az gün sayısı $n$ olmak üzere $\dbinom n{\lfloor n/2\rfloor}\geq N$ eşitsizliği sağlanmalıdır.

$\color{blue}\bullet$ Örneğin $10$ kişi için, en az $n=5$ güne ihtiyaç vardır ve $T_i$ anti-zinciri şu şekilde oluşturulabilir: $$(T_i)_{i=1}^{10} = \{ \{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\} \}.$$
Bu durumda,
$$\begin{align}  S_1&=\{1,2,3,4\}\\
S_2&=\{1,5,6,7\}\\
S_3&=\{2,5,8,9\}\\
S_4&=\{3,6,8,10\}\\
S_5&=\{4,7,9,10\}
\end{align}$$
olacaktır.


Kaynak: Problemi math.stackexchange.com sitesinde paylaştım. Sıra dışı ve parlak bir çözüm sunuldu. Bunu çevirisiyle beraber paylaşmak faydalı olacaktır.