سلام دوستان ...
ممنون میشم این سئوال رو شما اساتید گسسته بمن جواب بدید
۳۵۴ ورزشکار از ۵ کشور با اعداد ۱ تا ۳۵۴ شماره گذاری شده اند
ثابت کنید حداقل ۱ ورزشکار وجود دارد که شماره ی او یا برابر مجموع شماره های دو هموطنش است یا ۲ برابر یکی از هموطنانش
۱ تا ۳۵۴ را به ۵ زیر مجموعه ی A,B,C,D,E,F افراض کنید سپس اصل لانه کبوتری را اعمال کنید
سلام. یه راه حل دارم که بنظرم درسته.
میخواهیم اعداد ۱ تا ۳۵۴ رو به ۵ زیرمجموعه افراز کنیم بطوری که هیچ عضوی از هیچ مجموعه ای وجود نداشته باشه که مجموع دو مقدار از مجموعه یا دوبرابر یک مقدار از مجموعه باشه. اگه بشه این افراز رو انجام داد فرض سوال بالا نقض میشه و اگه نشه فرض سوال درسته.
مجموعمون ۳۵۴ عضو داره. در بهترین شرایط میشه [tex][\frac{354 1}{2}]=177[/tex] عضو از مجموعمون رو توی مجموعه اولمون بریزیم که فرض مسئله رو نقض نکنه. به تبعش حداکثر میشه [tex]177 [\frac{177 1}{2}]=266[/tex] عضو رو توی دو مجموعه قرار داد بطوری که توی هر مجموعه شرط مسئله صدق کنه. با این کار ۸۸ عضو باقی مونده داریم. با استفاده از مجموعه های سوم تا پنجم، در بهترین شرایط باز هم ۱۱ عضو در هیچ مجموعه ای نیستن که هرکدام از این ۱۱ عضو در هریک از مجموعه ها قرار بگیرن شرط مسئله نقض میشه. این ۱۱ عضو باید عضو ۵ زیر مجموعه باشن پس نمیشه افراز رو بدون نقض شرط مسئله انجام داد.
نمونه ای از این تقسیم:
مجموعه ی A شامل اعداد فرد {۳۵۳,...,۱,۳,۵}
مجموعه B شامل {۳۵۴,...,۲,۶,۱۰,۱۴}
مجموعه C شامل {۳۴۸,...,۴,۱۲,۲۰,۲۸}
مجموعه D شامل {۳۴۴,...,۸,۲۴,۴۰}
مجموعه E شامل {۳۳۶,...,۱۶,۴۸,۸۰}
مجموعه باقی مونده {۳۲,۶۴,۹۶,۱۲۸,۱۶۰,۱۹۶,۲۲۴,۲۵۶,۲۸۸,۳۲۰,۳۵۲}
نمونه ای دیگه میتونه از ۱۷۸ تا ۳۵۴ برای A و ۸۹ تا ۱۷۷ برای B و ۴۵ تا ۸۸ برای C و ۲۳ تا ۴۴ برای D و ۱۲ تا ۲۲ برای E باشه. ۱ تا ۱۱ هم انتخاب نشده هستن. اگه جوابم اشکال داشته باشه باید بشه یک زیر مجموعه بیشتر از [tex][\frac{n 1}{2}][/tex]عضوا از مجموعه اعداد ۱۱ تا n پیدا کرد که شرط مسئله رو نقض نکنه.
ماشالله حل ..... ممنون رفیق
سبک حلت جالب بود ... مرورش میکنم ... بازم دمتگرم
خواهش میکنم. با لانه کبوتری نتونستم. افرازش سخته. عضو ۱ و ۲ توی یک مجموعه نمیتونن باشن ولی ۳ میتونه توی هر مجموعه ای باشه. ۴ نباید با ۲ همگروهی باشه و همینطور با ۳و۱ باهم. احتمال شرطیش خیلی میشد. باید تا ۳۵۴ میرفتیم.