IMO - 1964 - 4

[Kiriti]

\(17\) জন ব্যাক্তি \(3\) টি বিষয়ের মধ্যে যেকোনো একটি বিষয় নিয়ে পরস্পরের মাঝে চিঠি আদান-প্রদান করে । প্রমাণ করো যে, এদের মধ্যে এমন \(3\) জন আছে যারা পরস্পরের মাঝে একই বিষয়ে চিঠি বিনিময় করে ।

[Fatin Farhan]

First mark 3 languages as p,q,r and a person as A.
এখন A কমপক্ষে ৬ জনকে একই বিষয়ে চিঠি লেখে ,ধরি এটি p । এই ৬ জনের মধ্যে যদি ২ জন p বিষয়ে চিঠি লেখে তাহলে হয়েই গেল। যদি তা না হয়, তাহলে ৬ জনের মধ্যে আরেকজন B নিই। বাকী ৫ জনের মধ্যে B কমপক্ষে ৩ জনকে একই বিষয়ে চিঠি লেখে, ধরি এটি q. এই ৩ জনের মধ্যে ২ জন যদি q বিষয়ে চিঠি লেখে তাহলে B ও ঐ ২ জন q বিষে চিঠি লেখে। তা না হলে B বাদে বাকী ৩ জন r ভাষায় চিঠি লেখে

[Phlembac Adib Hasan]

In graph theory, this problem can be stated as "In $K_{17}$, every edge is colored by red, green or blue. Prove that there exists a monochromic triangle."

We proceed indirectly. Assume the statement is wrong. Let $A$ be a vertex of it. From pigeon hole principle, at least 6 edges, with one endpoint at $A$ , are of same color. WLOG assume, their color is red and they join vertex $A$ with $A_1,A_2,A_3,A_4,A_5,A_6$. Note that $A_iA_j$ can't be red, because otherwise $AA_iA_j$ will be a monochromic triangle. So actually we have to color every edge of a $K_6$, $A_1A_2A_3A_4A_5A_6$ with two colors. So a monochromic triangle must exist in this $K_6$ graph, (This is pretty well-known and can be proved using similar arguments.) and so will in original $K_{17}$.