Tübitak Ortaokul 1. Aşama 2018 Soru 12

[matematikolimpiyati]

$2018$ kişinin katıldığı bir etkinlikte herhangi dört kişiden en az biri diğer üç kişinin her biri ile tokalaşmıştır. Bu etkinlikte birbirleriyle tokalaşmayan kişi ikilisi sayısı en çok kaç olabilir?

$\textbf{a)}\ 3  \qquad\textbf{b)}\ 12  \qquad\textbf{c)}\ 58 \qquad\textbf{d)}\ 252  \qquad\textbf{e)}\ 504$

[Metin Can Aydemir]

Cevap: $\boxed{A}$

Herkes birbiriyle tokalaşmış olmasın. $(A,B)$ ve $(C,D)$ ikilileri tokalaşmamış olsun. Eğer bu dört kişi farklı kişilerse diğer üç kişiyle tokalaşmış birisi olmayacağından çelişki elde edilir. Dolayısıyla, $(A,B)$ tokalaşmamış bir ikiliyse, tokalaşmamış diğer tüm ikililer ya $A$'yı ya da $B$'yi içermek zorundadır. Genelliği bozmadan ikinci ikili $(A,C)$ olsun. Aynı mantıkla, tüm tokalaşmayan ikililer ya $A$'yı ya da $C$'yi içermelidir. Bu da tokalaşmayan ikililerin sadece $(B,C)$ veya $(A,X)$ formatında olabileceğini gösterir. Eğer $(A,D)$ tokalaşmayacak şeklinde bir $B,C$'den farklı bir $D$ varsa, $A,B,C,D$'nin dörtlüsünü ele aldığımızda kimse $A$ ile tokalaşmadığından çelişki çıkar. Dolayısıyla, tokalaşmayan ikililer en fazla $(A,B),(A,C),(B,C)$ olabilir. Bu durumun sıkıntı çıkarmadığı da kolayca görülebilir çünkü her dörtlüde $A,B,C$'den farklı bir kişi vardır ve bu herkesle el sıkışır. Sonuç olarak tokalaşmayan ikili sayısı en fazla $3$ olabilir.