زمان کنونی: ۰۵ دى ۱۴۰۳, ۱۰:۱۸ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

لانه کبوتری

ارسال:
  

imanmomo پرسیده:

Lightbulb لانه کبوتری

سلام دوستان ...
ممنون میشم این سئوال رو شما اساتید گسسته بمن جواب بدید Exclamation
۳۵۴ ورزشکار از ۵ کشور با اعداد ۱ تا ۳۵۴ شماره گذاری شده اند
ثابت کنید حداقل ۱ ورزشکار وجود دارد که شماره ی او یا برابر مجموع شماره های دو هموطنش است یا ۲ برابر یکی از هموطنانش
۱ تا ۳۵۴ را به ۵ زیر مجموعه ی A,B,C,D,E,F افراض کنید سپس اصل لانه کبوتری را اعمال کنید Huh

۰
ارسال:
  

Jooybari پاسخ داده:

لانه کبوتری

سلام. یه راه حل دارم که بنظرم درسته.
میخواهیم اعداد ۱ تا ۳۵۴ رو به ۵ زیرمجموعه افراز کنیم بطوری که هیچ عضوی از هیچ مجموعه ای وجود نداشته باشه که مجموع دو مقدار از مجموعه یا دوبرابر یک مقدار از مجموعه باشه. اگه بشه این افراز رو انجام داد فرض سوال بالا نقض میشه و اگه نشه فرض سوال درسته.
مجموعمون ۳۵۴ عضو داره. در بهترین شرایط میشه [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 پیدا کرد که شرط مسئله رو نقض نکنه.

۰
ارسال:
  

imanmomo پاسخ داده:

لانه کبوتری

ماشالله حل ..... ممنون رفیق

سبک حلت جالب بود ... مرورش میکنم ... بازم دمتگرم

۰
ارسال:
  

Jooybari پاسخ داده:

لانه کبوتری

خواهش میکنم. با لانه کبوتری نتونستم. افرازش سخته. عضو ۱ و ۲ توی یک مجموعه نمیتونن باشن ولی ۳ میتونه توی هر مجموعه ای باشه. ۴ نباید با ۲ همگروهی باشه و همینطور با ۳و۱ باهم. احتمال شرطیش خیلی میشد. باید تا ۳۵۴ میرفتیم.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  اصل لانه کبوتری ss311 ۰ ۱,۲۶۳ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۰ ب.ظ
آخرین ارسال: ss311
  اصل لانه ی کبوتری - تعداد بازی های تیم بسکتبال در تعدادی از روزهای متوالی Doctorwho ۱ ۲,۲۴۳ ۱۳ آبان ۱۳۹۲ ۱۲:۳۱ ق.ظ
آخرین ارسال: Jooybari
  سوال از لانه ی کبوتری - اطمینان خارج شدن توپ های همرنگ Doctorwho ۱ ۲,۲۵۲ ۱۱ آبان ۱۳۹۲ ۰۲:۱۲ ق.ظ
آخرین ارسال: SnowBlind
  سوال از اصل لانه کبوتر Morris ۶ ۳,۶۲۸ ۲۳ مرداد ۱۳۹۲ ۱۰:۲۶ ب.ظ
آخرین ارسال: farhud
  سوال از اصل لانه کبوتری rad.bahar ۲ ۲,۵۲۲ ۲۹ تیر ۱۳۹۲ ۰۴:۵۸ ب.ظ
آخرین ارسال: Jooybari
Lightbulb سوال از اصل لانه کبوتری freaphea@emeil.in ۵ ۵,۵۸۷ ۰۲ تیر ۱۳۹۱ ۰۲:۱۷ ق.ظ
آخرین ارسال: ihelpu
  بررسی مثال ۵۹، اصل لانه کبوتر(فصل دوم کتاب پوران) reyhaneh64 ۱ ۳,۲۱۹ ۲۸ آذر ۱۳۹۰ ۱۲:۱۷ ق.ظ
آخرین ارسال: Jooybari
  سوال در مورد زبان منظم با استفاده از اصل لانه کبوتر desatir7316 ۴ ۳,۸۰۹ ۲۶ شهریور ۱۳۹۰ ۱۱:۵۳ ق.ظ
آخرین ارسال: fateme66

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close