منو
 کاربر Online
825 کاربر online

اعداد رمزی

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


اعداد رمزی

مثال 1

در بین هر 6 نفر، همیشه می توان 3 نفر یافت که دو به دو با هم دوست باشند یا هیچ دو تایی با هم دوست نباشند.
مسأله فوق در مسابقهُ ریاضی کورشاک در سال 1947 ارائه شد، همچنین در سال 1953 در مسابقهُ ریاضی پاتنام نیز از این مسأله استفاده شده است. بعدها این مسأله توسط گلیسن وگین وود تعمیم داده شد.

مثال 2

هفده دانشمند در یک کنفرانس علمی شرکت دارند و موضوع های مطرح شده در کنفرانس سه شاخهُ در کنفرانس سه شاخهُ هندسه، جبر و ترکیبیات می باشد. می دانیم که هر دو تایی از آنها دقیقاً در مورد یک شاخه با هم مباحثه دارند، نشان دهید سه دانشمند وجود دارند به طوری که هر سه تایی آنها در مورد یک شاخه با هم مباحثه داشته اند.

مثال 3

به تعداد نقطه در فضا داده شده اند. هر جفت از نقاط توسط یک خط به هم وصل شده اند و هر خط با یکی از رنگ داده شده رنگ شده است. نشان دهید حداقل یک مثلث (با سه رأس از این نقاط) با اضلاع هم رنگ وجود دارد. ( عدد نپر می باشد و نشان دهندهُ جزء صحیح می باشد.)

مثال 4

در یک کنفرانس بین المللی از 6 کشور مختلف شرکت کننده وجود دارد. اسامی شرکت کنندگان 1978 نام است که به وسیلهُ اعداد 1978,…,2,1 شماره گذاری شده اند. نشان دهید یک شرکت کننده وجود دارد به طوری که شماره اش برابر مجموع شماره های دو شرکت کنندهُ هموطنش یا دو برابر شمارهُ یک هموطن می باشد.



مثال 1 را می توان به شکل زیر مدلسازی نمود. 6 نقطه در صفحه در نظر بگیرید (هیچ سه تایی بر یک استقامت نباشند) که هر نقطه متناظر با یک شخص است حال پاره خط های میان هر دو نقطه را با رنگ آبی یا قرمز رنگ کنید با رعایت این قاعده که اگر دو شخص متناظر آن دو نقطه با هم دوست بودند این پاره خط را قرمز و در غیر این صورت آبی کنید. حال حکم مثال 1 به این تبدیل می شود که حتماً یک مثلث با اضلاع تک رنگ وجود دارد. (اگر اضلاع قرمز باشند سه نفر دو به دو با هم دوست و اگر اضلاع آبی باشند سه نفر دو به دو با هم دوست نیستند.)
مثال 2 را نیز می توان به وسیله 17 نقطه و پاره خط های بین آنها تعبیر کرد ولی این بار برای رنگ کردن پاره خط ها از سه رنگ استفاده می شود. رابطهُ بین مثال 4 و 2 را بعداً بیان خواهیم کرد، سعی کنید رابطهُ بین این دو مثال را پیدا کنید.
قبل از اینکه به سراغ حل این مثال ها برویم چند تعریف و نماد را بیان می کنیم، p نقطه در نظر بگیرید که هیچ سه تایی از آنها هم خط نباشند و هر جفت از آنها را به وسیلهُ یک خط (یا خم) به هم وصل کنید، شکل به دست آمده را گراف کامل می نامیم و آن را با نشان می دهیم، این گراف رأس، یال (پاره خط) و مثلث دارد. اگر هر یال از با یکی از رنگ داده شده رنگ شده باشد می گوییم یک رنگ آمیزی از داریم، اگر شامل یک مثلث با اضلاع یک رنگ باشد آن مثلث را تک رنگ می نامیم و گوییم شامل یک تک رنگ است.

حل مثال 1

یال های با دو رنگ آبی و قرمز رنگ شده اند. یکی از 6 رأس را در نظر بگیرید و آن را بنامید. طبق اصل لانه کبوتری حداقل 3 تا از 5 تا خطی که از خارج می شوند از یک رنگ هستند مثلاً فرض کنید این رنگ قرمز باشد. حال فرض کنید ، و نقاط انتهایی این 3 خط قرمز باشند (شکل 1)
img/daneshnameh_up/a/a5/com0031a.jpg

اگر یکی از اضلاع مثلث قرمز باشد، آنگاه یک مثلث با اضلاع قرمز خواهیم داشت، در غیر این صورت یک مثلث آبی رنگ خواهد بود، پس در هر دو حالت یک مثلث تک رنگ داریم. شکل 2 نشان می دهد که اگر به جای 5 نقطه، 6 نقطه داشته باشیم که پاره خط های بین آنها با دو رنگ، رنگ شده باشند لزومی ندارد که یک مثلث تک رنگ داشته باشیم.

حل مثال 2



یال های با سه رنگ قرمز، آبی و سبز رنگ شده اند. فرض کنید یکی از 17 رأس آن باشد. حداقل شش تا از 16 خطی که از خارج می شوند از یک رنگ مثلاً قرمز هستند، فرض کنید نقاط انتهایی این 6 پاره خط باشند. اگر حداقل یک جفت از این 6 نقطه توسط پاره خطی قرمز به هم وصل باشند آنگاه یک مثلث قرمز خواهیم داشت. وگرنه پاره خط های میان این 6 نقطه به وسیلهُ آبی و سبز رنگ شده اند، حال با توجه به مثال قبل حداقل یک مثلث تک رنگ در میان این 6 نقطه داریم. بد نیست بدانید که یال های گراف را می توان طوری با سه رنگ قرمز، آبی و سبز رنگ کرد که در آن مثلث تک رنگ وجود نداشته باشد.

حل مثال 3

می دانیم ، و اگر به شیوهُ حل مثال 2 با استفاده از مثال 1 توجه کرده باشید خواهید دید که را نیز می توان محاسبه کرد، به این صورت که باید کوچکترین عددی باشد که در هر رنگ آمیزی گراف کامل رأسی به وسیلهُ 4 رنگ در هر رأس بتوان 17 یال به رنگ یکسان پیدا کرد، با کمی توجه خواهیم داشت . به طور مشابه و و در حالت کلی داریم:


اگر قرار دهیم ، داریم

یا

از این رابطه نتیجه می شود:

اما طبق تعریف اگر به سمت بینهایت برود عبارت داخل پرانتز برابر یعنی عدد نپر خواهد بود پس

که



(تساوی سمت راست با توجه به فرمول تصاعد هندسی نامتناهی با قدر نسبت کمتر از یک به دست آمده است.)
بنابراین داریم: ، یعنی درنتیجه .

حالت خاص قضیهُ رمزی برای گراف و رنگ به شرح زیر است:
اگر اعدادی صحیح باشند آنگاه عددی مانند وجود دارد به طوری که اگر و یال های گراف را با رنگ به دلخواه رنگ کنیم آنگاه:
ای بین 1 تا وجود دارد به طوری که شامل یک با یال های یک رنگ است، در ضمن کمترین عدد با این خاصیت است، اعداد اعداد رمزی نامیده می شوند.
به عنوان نمونه تعبیر مثال 1 این است که یا مثال 13 یعنی . همچنین به راحتی می توان دریافت که img/daneshnameh_up/9/91/com0031b.jpgرا برای اختصار با نیز نشان می دهند، در مثال 3 دیدیم که .
همچنین معلوم شده است که ، ، ، ، و . عدد رمزی آخر در سال 1993 پیدا شده است.
حال به سراغ مثال 4 می رویم، با کمی توجه به این مثال می بینیم که باید این حکم را ثابت کنیم که مجموعهُ را نمی توان به 6 مجموعهُ «خالی از جمع» افراز کرد. (مجموعه ای از «خالی از جمع» نامیم که جمع هیچ دو عضوی از آن (حتی جمع یک عضو با خودش) در آن نباشد.) نشان می دهیم اگر 1978 با 1957 عوض شود باز هم حکم درست است. پس فرض کنید یک افراز از به 6 زیرمجموعهُ خالی از جمع مانند موجود باشد. طبق اصل لانه کبوتری یکی از این 6 مجموعهُ مثلاً حداقل یعنی 327 عضو دارد مانند که



با توجه به فرض مسأله هیچ کدام از اعداد در قرار ندارند زیرا خالی از جمع است. پس این اعداد در مجموعه های تا قرار دارند. یکی از این مجموعه ها مثلاً شامل حداقل یعنی 66 تا از این تفاضل ها است که آنها را با ترتیب صعودی بنامید. اعداد نه در و نه در قرار دارند زیرا و هر دو خالی از جمع اند، پس در مجموعه های تا قرار دارند. مشابه بحث فوق یکی از این مجموعه ها مثلاً شامل حداقل 17 تا از این اعداد مانند می باشد. حال 16 عدد را در نظر بگیرید این 16 عدد متعلق به هیچ کدام از مجموعه های ، و نیستند پس در ، یا قرار دارند، یکی از این مجموعه ها مثلاً شامل حداقل 6 تا از این تفاضل ها می باشد، مانند است. حال 5 عدد در ، ، و نیستند، پس مثلاً شامل 3 تا از آنها می باشد، مانند . حال دو عدد در مجموعه های تا قرار ندارند پس در قرار دارند، حال در هیچ کدام از مجموعه های تا قرار ندارد و این تناقض است زیرا مجموعهُ را افرازکرده اند.
رابطه ای نزدیک بین مثال های 3 و 4 وجود دارد که آن را بیان خواهیم کرد. یک زیرمجموعه مانند از اعداد طبیعی «خالی از جمع» می باشد هرگاه معادلهُ به ازای فاقد جواب باشد، توجه کنید که مجموعهُ جواب معادله شامل نیز می باشد. در سال 1916 ایسایی شور در رابطه با حدس (قضیه) فرما، مسأله زیر را مطرح کرد:

بزرگترین عدد طبیعی مانند به طوری که مجموعهُ را بتوان به زیرمجموعهُ خالی از جمع افراز کرد چیست؟
تابع به تابع شور مشهور است، این تابع تنها برای چهار مقدار مشخص شده است. تساوی های ، و به راحتی قابل اثبات اند. بامرت در سال 1961 با کمک کامپیوتر نشان داد . در حقیقت افراز خالی از جمع به شکل زیر است




شور نامساوی های زیر را ثابت کرد



برای اثبات نامساوی سمت راست کافی نشان دهیم هر طور که مجموعهُ را به مجموعه افراز کنیم معادلهُ در یکی از این زیرمجموعه جواب دارد.
فرض کنید

یک افراز باشد. یک گراف کامل به نام در نظر می گیریم که رئوس آن اعداد باشند. یال های گراف را با رنگ رنگ می کنیم به این شکل که به یال (پاره خط میان ) رنگ را نسبت می دهیم هرگاه . طبق مثال 2 گراف یک مثلث تک رنگ دارد یعنی اعداد صحیح و مثبت موجودند به طوری که و یال های ، و رنگ یکسانی مانند دارند یعنی

از طرفی بنابراین خالی از جمع نیست، پس مجموعهُ با مجموعه های بزرگتر از آن را نمی توان به زیرمجموعهُ خالی از جمع افراز کرد بنابراین خصوصاً ، این نامساوی اثباتی ساده تر برای مثال 4 را به دست می دهد.
حال تعریف را به یاد بیاورید، این عدد کوچکترین عدد طبیعی است به طوری که هر طور یال های گراف کامل رأسی را با رنگ کنیم، یک مثلث تک رنگ موجود خواهد بود. در مثال های قبل نشان دادیم . نامساوی را نیز می توان مشابه روش فوق اثبات کرد. فرض کنید این نامساوی درست نباشد و مثلاً

فرض کنید یک افراز خالی از جمع از باشد وفرض کنید یک گراف کامل با رئوس باشد. یال های را با اعداد 1 تا به این شکل رنگ می کنیم. به یال رنگ را نسبت می دهیم هرگاه .
بنابراین طبق نامساوی یک مثلث تک رنگ داریم یعنی اعداد وجود دارند به طوری که .
از طرفی و این خلاف خالی از جمع بودن افراز است، بنابراین فرض خلف باطل است و نامساوی ثابت می شود.
دریکی از مسأله ها نشان می دهیم . بنابراین رابطهُ زیر ثابت می شود

که از آن داریم

با توجه به نتیجهُ بامرت نامساوی بدست می آید که بهتر از نتیجهُ بالا است. در 30 سال اخیر رابطهُ نیز ثابت شده است

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0056.pdf

همچنین ببینید





تعداد بازدید ها: 25567


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..