۰
subtitle
ارسال: #۱
  
لانه کبوتری
سلام دوستان ...
ممنون میشم این سئوال رو شما اساتید گسسته بمن جواب بدید
۳۵۴ ورزشکار از ۵ کشور با اعداد ۱ تا ۳۵۴ شماره گذاری شده اند
ثابت کنید حداقل ۱ ورزشکار وجود دارد که شماره ی او یا برابر مجموع شماره های دو هموطنش است یا ۲ برابر یکی از هموطنانش
۱ تا ۳۵۴ را به ۵ زیر مجموعه ی A,B,C,D,E,F افراض کنید سپس اصل لانه کبوتری را اعمال کنید
ممنون میشم این سئوال رو شما اساتید گسسته بمن جواب بدید
۳۵۴ ورزشکار از ۵ کشور با اعداد ۱ تا ۳۵۴ شماره گذاری شده اند
ثابت کنید حداقل ۱ ورزشکار وجود دارد که شماره ی او یا برابر مجموع شماره های دو هموطنش است یا ۲ برابر یکی از هموطنانش
۱ تا ۳۵۴ را به ۵ زیر مجموعه ی 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 پیدا کرد که شرط مسئله رو نقض نکنه.
میخواهیم اعداد ۱ تا ۳۵۴ رو به ۵ زیرمجموعه افراز کنیم بطوری که هیچ عضوی از هیچ مجموعه ای وجود نداشته باشه که مجموع دو مقدار از مجموعه یا دوبرابر یک مقدار از مجموعه باشه. اگه بشه این افراز رو انجام داد فرض سوال بالا نقض میشه و اگه نشه فرض سوال درسته.
مجموعمون ۳۵۴ عضو داره. در بهترین شرایط میشه [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 پیدا کرد که شرط مسئله رو نقض نکنه.
۰
ارسال: #۳
  
لانه کبوتری
ماشالله حل ..... ممنون رفیق
سبک حلت جالب بود ... مرورش میکنم ... بازم دمتگرم
سبک حلت جالب بود ... مرورش میکنم ... بازم دمتگرم
۰
ارسال: #۴
  
لانه کبوتری
خواهش میکنم. با لانه کبوتری نتونستم. افرازش سخته. عضو ۱ و ۲ توی یک مجموعه نمیتونن باشن ولی ۳ میتونه توی هر مجموعه ای باشه. ۴ نباید با ۲ همگروهی باشه و همینطور با ۳و۱ باهم. احتمال شرطیش خیلی میشد. باید تا ۳۵۴ میرفتیم.
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
اصل لانه کبوتری | ss311 | ۰ | ۱,۲۶۳ |
۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۰ ب.ظ آخرین ارسال: ss311 |
|
اصل لانه ی کبوتری - تعداد بازی های تیم بسکتبال در تعدادی از روزهای متوالی | Doctorwho | ۱ | ۲,۲۴۳ |
۱۳ آبان ۱۳۹۲ ۱۲:۳۱ ق.ظ آخرین ارسال: Jooybari |
|
سوال از لانه ی کبوتری - اطمینان خارج شدن توپ های همرنگ | Doctorwho | ۱ | ۲,۲۵۲ |
۱۱ آبان ۱۳۹۲ ۰۲:۱۲ ق.ظ آخرین ارسال: SnowBlind |
|
سوال از اصل لانه کبوتر | Morris | ۶ | ۳,۶۲۸ |
۲۳ مرداد ۱۳۹۲ ۱۰:۲۶ ب.ظ آخرین ارسال: farhud |
|
سوال از اصل لانه کبوتری | rad.bahar | ۲ | ۲,۵۲۲ |
۲۹ تیر ۱۳۹۲ ۰۴:۵۸ ب.ظ آخرین ارسال: Jooybari |
|
سوال از اصل لانه کبوتری | freaphea@emeil.in | ۵ | ۵,۵۸۷ |
۰۲ تیر ۱۳۹۱ ۰۲:۱۷ ق.ظ آخرین ارسال: ihelpu |
|
بررسی مثال ۵۹، اصل لانه کبوتر(فصل دوم کتاب پوران) | reyhaneh64 | ۱ | ۳,۲۱۹ |
۲۸ آذر ۱۳۹۰ ۱۲:۱۷ ق.ظ آخرین ارسال: Jooybari |
|
سوال در مورد زبان منظم با استفاده از اصل لانه کبوتر | desatir7316 | ۴ | ۳,۸۰۹ |
۲۶ شهریور ۱۳۹۰ ۱۱:۵۳ ق.ظ آخرین ارسال: fateme66 |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close