Question

می خواهیم اعداد طبیعی را طوری رنگ آمیزی کنیم که اولاً هر دو عدد متوالی ناهمرنگ باشند و ثانیاً برای هر دو عدد ناهمرنگ a و b، یا باقیمانده a و b بر 11 متفاوت باشد یا باقیمانده a و b بر 17. کمترین تعداد رنگ ها چقدر است؟

Answer 1

به نام خدا. پاسخ بنده به شکل زیر است. ممنون می شوم اساتید تأیید کنند.

نکته: اگر باقیمانده تقسیم دو عدد a,b بر عدد c یکسان و تقسیم دو عدد a,b بر d یکسان بود، آنگاه باقیمانده تقسیم هر دو عدد a,b بر cd نیز یکسان خواهند بود.

اثبات این نکته راحت است.

با توجه به شرط دوم مسئله، اعدادی که تقسیم بر $11×17=187$ بشوند و باقیمانده یکسانی بدهند آن گاه همرنگ خواهد بود. اگر به طور فرضی از دو رنگ استفاده شود، آنگاه نتیجه نادرست ناهمرنگ بودن اعداد1 و 188 بدست می آید. حال اعداد را در دسته های 187 تایی قرار می دهیم:

$ A_1$ ={$1,2,...,187$}

$A_2$ ={$188,189,...,374$}

$A_3$ ={$375,376,...,561$}

.

.

.

حال نباید عضو های اول هر مجموعه ناهمرنگ باشند و همینطور عضو های دوم و..تا عضو ها 187 ام، پس باید همرنگ باشند. فرض کنیم که سه رنگ $R،G،B$ را در اختیار داریم. برای رنگ آمیزی می توان ابتدا تمام عضو های اول هر مجموعه را با رنگ G رنگ آمیزی کنیم. سپس عضو های هر مجموعه را به ترتیب از عضو دوم تا آخرین عضو، یکی درمیان با رنگ های R,B رنگ کنیم.