Tokalaşma (Çözüm)

Basit bir deneme olarak $N=1$ alalım ve 4 kişi için kutudan çıkan tokalaşmaların sayısı olarak $0, 1, 2$ değerlerini verecek durumu bulalım. Kişileri aşağıdaki gibi ifade edelim.

$BB$ : Bölüm başkanı
$BBE$ : Bölüm başkanının eşi
$D_{1}$ : 1 numaralı davetli
$DE_{1}$ : 1 numaralı davetlinin eşi

Bu kişilerin tokalaşma adedini de $T()$ ile gösterelim, yani $T(BB)$ bölüm başkanının tokalaşma sayısını göstersin.

Eğer $T(BBE) = 0$ ise o zaman $T(D_{1}) = 2$ ya da $T(DE_{1}) = 2$ olmalıdır. Bu ikisi birbirleriyle ve kendileriyle tokalaşmadıklarına göre birisi kalan iki kişiyle tokalaşmış olmalıdır. Bu durumda $T(BBE) > 0$ olmalıdır ve bu da varsayımımızla çelişmektedir. Demek ki $T(BBE) \ne 0$.

Eğer $T(BBE) = 2$ ise o zaman $T(D_{1}) = 0$ ya da $T(DE_{1}) = 0$ olmalıdır. BBE BB ile ya da kendiisiyle tokalaşmadığına göre hem $D_{1}$ ile hem de $DE_{1}$ ile tokalaşmış olmalıdır. Bu durumda $T(D_{1}) > 0$ ve $T(DE_{1}) > 0$ olmalıdır ve bu da varsayımımızla çelişmektedir. Demek ki $T(BBE) \ne 0$.

O zaman $T(BBE) = 1$ olmalıdır. Bu durumda $T(D_{1}) = 0$ ve $T(DE_{1}) = 2$ (ya da $T(D_{1}) = 2$ ya da $T(DE_{1}) = 0$) ve $T(BB) = 1$ olacak.

Bir davetli çift için bölüm başkanı ve eşi birer kere tokalaşmış olacak. Davetli çiftten bir kişi iki diğeri de sıfır kere tokalaşmıştır.

Şimdi çözüm için bazı gözlemler yapalım. $N > 0$ adet davetli ve eşleriyle beraber partide toplam $2N+2$ kişi (davetli çiftler, bölüm başkanı ve bölüm başkanının eşi) olacaktır.

1.) Herhangi bir kişi en fazla $2N$ kere tokalaşmış olabilir: Bir kişi kendisi ve eşi ile tokalaşamayacağına göre en fazla toplam kişi adedinden iki eksik kere tokalaşabilir. Bu da $(2N+2) - 2 = 2N$ kere tokalaşma demektir.  

2.) Partiye katılmış çiftlerden birindeki kişilerden biri $0$ diğeri de $2N$ kere tokalaşmıştır: Partidekilerden biri $2N$ kere tokalaşmıştır, yani eşi ve kendisi dışında herkesle tokalaşmış. Bu durumda $0$ kere tokalaşmış olabilecek tek aday vardır. Bu da bu kişinin eşidir.

3.) Bölüm başkanının eşi $0$ kere tokalaşmamıştır: Bölüm başkanı kutuya tokalaşma adedini koymadığına göre partideki diğer bir kişi $2N$ kişi ile tokalaşmıştır. Bu durumda bu kişi bölüm başkanının eşi ile de tokalaşmış olurdu ve böylece bölüm başkanının eşi $0$ kere tokalaşmış olamaz.

4.)  Bölüm başkanının eşi $2N$ kere tokalaşmış olamaz: Bölüm başkanı kaç kere tokalaştığını kutuya koymadığından başka bir davetli $0$ kere tokalaşmıştır. 2 numaralı gözlemden biliyoruz ki  bu davetlinin eşi de $2N$ kere tokalaşmış olmalıdır ama kutudan sadece bir adet $2N$ sayısı çıktığına göre bölüm başkanının eşi $2N$ kere tokalaşmış olamaz.

Bu gözlemlerden çıkan sonuç şudur: Bölüm başkanı ve eşi dışında partiye katılan bir çift $0$ ve $2N$ kere tokalaşmıştır. 

Bu çiftin özelliği de diğer herkese etkileri aynı olmuş olmaları. Yani biri herkesle birer kere tokalaşmış, diğeri de hiç kimseyle tokalaşmamış. Bu durumda bu çifti partiden (ve de sayımdan) çıkarırsak aynı şartlarda daha küçük bir problem elde ederiz. Yani kutudan çıkan sayılardan $0$ ve $2N$ sayılarını önce atarız, böylece geriye $1$'den $2N-1$'e kadar sayılar kalır. Şimdi de herkesle olan tokalaşmaları bir azaltırsak (bu çiftin herkesle olan eşit etkileşimi nedeniyle) problem bu sefer $0$'dan $2N-2$'ye kadar her sayının bir kere olduğu bir tokalaşma partisine dönüşür ve elimizde artık sadece $N-1$ davetli çift kalmıştır. Partiden çıkardığımız bu çift bölüm başkanı ile de toplam 1 kere tokalaşmıştır. 

Bu aşamada ilk dört gözlemimiz hala geçerlidir. Bu nedenle aynı dönüşümü davetli çiftler bitene kadar tekrarlayabiliriz ve çıkarılan her çift için bölüm başkanının toplam tokalaşma adedine bir ekleriz. Bütün davetli çiftler partiden çıkarıldığında da sonuç olarak bölüm başkanının $N$ kere tokalaşmış olduğunu buluruz.

Son çifti de çıkardığımızda davetli çift sayısı 0 olacaktır ve artık tokalaşma yapılmayacaktır. Bu aşamada da algoritmamız son bulacaktır.

5.) Her bir çift toplam $2N$ kere tokalaşmıştır: $0$ ve $2N$ yukarıda incelenmişti. $2N-1$ kere tokalaşmış kişi için durumu inceleyelim. Partide $n$ kere tokalaşmış kişiyi $K_{n}$ şeklinde gösterelim. $K_{2N-1}$, $K_{2N}$ ve $K_{0}$ dışında $2N-2$ kişiyle tokalaşmıştır (bir eksik tokalaşma $K_{2N}$ ile olan). Yani bu kişi kendisi, eşi, $K_{2N}$ ve $K_{0}$ dışında herkesle tokalaşmıştır. $K_{2N}$ de aynı kişilerle de tokalaştığından bu kişilerin tokalaşma adedi en az 2'dir. Bu durumda br kere tokalaşmış olan tek kişi $K_{2N-1}$'in eşidir. Aynı mantık diğer kişiler için de yürütülürse her çiftin toplam $2N$ kere tokalaştığı çıkar.

Dolayısı ile hem bölüm başkanı hem de eşi $N$ kere tokalaşmmıştır.