صورت سوال در کتاب ترکیبیات (تالیف آقای علیرضا علی پور، انتشارات فاطمی):

مسئله 7.2.5 هر یک از ضلع ها و قطر های شش ضلعی $ABCDEF$ را با یکی از دو رنگ آبی و قرمز رنگ کرده ایم. منظور از مثلث رنگی، مثلثی است که رأس هایش، رأس های شش ضلعی باشند و هر سه ضلع آن همرنگ باشند.مثلا در شکل 2.5 مثلثهای $ABE$ و $ACD$ رنگی اند. ثابت کنید رنگ آمیزی به هر صورتی که باشدحداقل یک مثلث رنگی در شش ضلعی ایجاد می شود.

راه حل. پنج پاره خط از رأس $A$ خارج شده است. چون هر یک از این پاره خط ها به یکی از دو رنگ آبی و قرمز است، پس حداقل 3 تا از آن ها همرنگ اند. می توانیم فرض کنیم پاره خطهای $AB$، $AC$ و $AD$ به رنگ آبی اند (شکل 2.5 را ببینید). اگر یکی از پاره خطهای $BD$، $BC$ یا $CD$، مثلا $BD$ به رنگ آبی باشد، آنگاه $ABD$ مثلثی رنگی است و در غیر این صورت هر سه پاره خط به رنگ قرمز اند و در نتیجه $BCD$ مثلثی رنگی است. (شکل 4.5 را ببینید). پس در هر صورت مثلثی رنگی در شش ضلعی وجود دارد.

این پرسش در دوره ی تابستانه ی المپیاد ریاضی هم مطرح شده. (کلاس ترکیبیات، به تاریخ 2/4/1392)

صورت سوال:

6 نفر دانش آموز مفروض اند، بین هر دو دانش آموز یک رابطه ی دوستی، وگرنه یک رابطه ی دشمنی وجود دارد. روابط توضیع پذیر نیستند (مثلا اگر $A_1$ با $A_2$ و $A_2$ با $A_3$ دوست باشد، آنگاه $A_1$ حتما با $A_3$ دوست نیست.). ثابت کنید 3 نفر از این شش نفر وجود دارند که هر سه باهم دوست یا هر سه با هم دشمن اند.

حل:

گریزی به نظریه ی گراف می زنیم. هر فرد را یک رأس و هر رابطه را یک یال در نظر می گیریم. میان دو فرد $A_x$ و $A_y$ یال کامل می کشیم اگر و تنها اگر با هم دوست باشند و میانشان یال را به صورت خط چین می کشیم فقط و فقط اگر با هم دشمن باشند.

(حتما روی کاغذ گراف را رسم کنید تا نحوه ی حل را ببینید)

فرد $A_1$ را در نظر بگیرید، او با 5 نفر دیگر؛ یعنی $A_2$ تا $A_6$ رابطه ی دوستی یا دشمنی دارد. طبق اصل لانه کبوتری 3 تا از این رابطه ها یکسان اند، فرض می کنیم این سه رابطه ی یکسان از نوع دوستی هستند (شما می توانید فرض کنید از نوع دشمنی اند. این لطمه ای به اثبات نمی زند)

پس تا این جا، $A_1$ با $A_x$ و $A_y$ و $A_z$ دوست است، حال $A_x$ و $A_y$ را در نظر بگیرید. اگر آن دو با هم دوست باشند که مسئله حل است! لذا آن ها با دشمن اند. پس $A_y$ و $A_z$ را در نظر بگیرید. اگر با هم دوست باشند مثلث دوستی پدید می آید پس آن ها با هم دشمن اند.

حال $A_x$ و $A_z$ را در نظر بگیرید. اگر آن دو با هم دوست باشند، مثلث دوستی و اگر با هم دشمن باشند، مثلث دشمنی پدید می آید. پس حکم مسئله ثابت شد.

فیلم جلسه ی اول دوره ی تابستانه ی المپیاد ریاضی را می توانید از اینجا دیده و دریافت نمایید. در دقیقه ی 56:45 می توانید حل سوال بالا را به صورت تصویری ببینید.

یکی از نقاط مثل x را در نظر میگیریم، طبق اصل لانه کبوتری، 3 یال همرنگ از این راس خارج میشوند($5/3$). فرض کنید این رنگ، A باشد و آن سه یال، به رئوس a, b, c وصل شده باشند
حالا میگیم اگر یال بین دو تا از رئوس a,b,c به رنگ A باشند، مثلا یال بین رئوس a و b، ان وقت مثلثی که سوال میخواهد، مثلث xab است
در غیر این صورت اگر چنین یالی بین سه راس a, b, c نباشد، یعنی هر سه سال، به رنگ B هستند و مثلثی که سوال میخواهد، مثلث abc خواهد بود
+توی آنالیز ترکیبی علیپور بود این سوال. اگر خواستی اصلاح کن

حالت خاص از قضیه رمزی

تصور کنید که یال‌های یک گراف کامل با ۶ راس با دو رنگ آبی و قرمز رنگ آمیزی شده باشد. حال یک راس مثلاً راس v را انتخاب کنید. ۵ یال به v متصل هستند و از این رو بنابر اصل لانه کبوتری حداقل ۳ تا از آن‌ها باید همرنگ باشند. بدون کاسته شدن از کلیت مساله می‌توان فرض کرد که حداقل ۳ یال که از راس v به راس‌های r,s،t متصل اند آبی هستند (در غیر این صورت جای رنگ‌های قرمز و آبی عوض می‌شود.) اگر هر یک از یال‌های (r, s), (r, t), (s, t) نیز آبی باشد آن گاه ما یک مثلث از یال‌های آبی داریم. در غیر این صورت یعنی اگر هیچ یک از یال‌های ذکر شده آبی نباشند هر سهٔ این یال‌ها قرمز خواهند بود و ما یک مثلث به رنگ قرمز خواهیم داشت.