رنگ آمیزی اعداد طبیعی

M_Sharifi · 1389/6/5

ِیه سوال:
برای هر عدد اول

$p$

ثابت کنید می توان مجموعه ی اعداد طبیعی را با

$p-1$

رنگ طوری رنگ آمیزی کرد که برای هر عدد طبیعی

$a$

، اعضای مجموعه ی

$\{a,2a,\ldots,(p-1)a\}$

دو به دو ناهمرنگ باشند.

mousavi · 1389/6/5

به این شیوه رنگ میکنیم:ابتدا رنگها را شماره گذاری میکنیم,

$1,2,3,...,p-1$

,اگر عددی بر p بخشپذیر نباشد به پیمانه p میبریم وشماره رنگش را عدد باقیمانده اش انتخاب میکنیم.
اگر بر p بخشپذیر باشد ابتدا ان عدد را بر بزرگترین توان عامل p تقسیم میکنیم بعد پیمانه p و...
حال حکم را ثابت میکنیم:اگر

$a\neq pk$

برای مجموعه در مسئله اگر دو عدد همرنگ باشند باید به پیمانه p همنهشت باشند که نیستند( دستگاه مخفف ماندها)
اگر

$a=p^\alpha k(k\neq px)$

برای مجموعه در مسئله اگر دو عدد همرنگ باشند باید بعد از تقسیم بر

$p^\alpha$

به پیمانه p همنهشت باشندولی باید به ازای i و j داشته باشیم:

$(j-i)k\equiv 0(mod p)$

این هم نمیشه.

رنگ آمیزی اعداد طبیعی

M_Sharifi

راهبر ریاضی

mousavi

New Member