شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

آخرین مطالب
بایگانی

شب 6

يكشنبه, ۲۳ دی ۱۳۹۷، ۱۲:۵۲ ق.ظ

سلام شاز.

اول راه سوال شب 5 رو میگم. اگه نمیخواین اسپویل شه این قسمتو اسکیپ کنین.

فرض کنین میز 2n+1 نفری باشه. با استقرا ثابت میکنیم به ازای هر k بین 1 تا n+1، بعد از گذشت یه تعداد حرکت، یا 2k تا کارت با شماره 1 تا k هیچ کدوم دوتاشون دست یه نفر نیست (دقیقن 2k تا جا اشغال کردن) یا اینکه حکم سوال (دوتا کارت با شماره برابر دست یه نفر باشن) نتیحه شده. به ازای k=1 حکم درسته، چون یا دوتا کارت 1 دست یه نفرن، یا اینکه دست دو نفرن :3

حالا برای k ثابت میکنیم. طبق فرض استقرا روی k-1، بعد از یه تعداد حرکت یا حکم نتیجه شده که حله یا اینکه تمام کارت های 1 تا k-1 دست آدمای مختلفه. این کارتای 1 تا k-1 هر مرحله دقیقن یکی شیفت سمت راست میخورن؛ چون از بقیه کارتا اکیدن کوچیکترن و به هم دیگه هم برخورد نمیکنن چون فاصله هاشون حفظ میشه. حالا یه کارت k رو در نظر بگیرید. آدمی که این کارته رو داره اول یه تعداد کارت 1 تا k-1 میان پیشش و میرن و بالاخره یا کارت k دیگه میاد پیشش که حله، یا اینکه یه کارت بزرگتر از k میاد پیشش. در اینصورت آدمه کارت k اشو میده بغلی و این کارت k عه هر دفعه به بغلی داده میشه؛ چون آدم کناری طبق فرض استقرا نهایتن یه دونه کارت کمتر از k داره که توی اون حرکت پاسش میده به بغلی خودش و اون یکی کارتش حتمن یا k عه که حله یا بزرگتر از k عه و بازم این پاس دادن ادامه پیدا میکنه. به این ترتیب اون همه 2k تا کارت 1 تا 2k هم دقیقن 2k تا آدم اشغال میکنن و گام استقرا ثابت میشه.

حالا طبق چیزی که اثبات کردیم به ازای k=n+1، چون نمیشه همه 2n+2 تا کارت دست آدمای مختلف باشه، پس حالت دیگه درسته که یعنی حکم مسئله ثابت شده :#


حالا سوال امشب :

G یه گراف دوبخشی کامله که هر بخشش n تا راس دارن. F یه گراف دو بخشیه که بخش بالا n تا راس داره بخش پایین 2n-1 راس که راس i ام از بخش بالا به راس های 1 تا 2i-1 از پایین وصله. ثابت کنید به ازای هر x از 1 تا n، تعداد تطابق های x یالی تو G و F برابره.


نویسنده : امید آزادی (سوال امشب از کلباسه)

  • ۹۷/۱۰/۲۳
  • طلاهای دوره ۲۸

نظرات  (۵)

ممنون از وقتی که میزارید
این سوالات رو تو لخش امتحانات و سوالات لطفا بذارید
با ناوردا هم فکر کنم حل میشه سوال. 
از بین دوتا کارتی که دست یه آدمه اونی که شمارش بیشتر هست رو در نظر بگیرین. این مقدار کم نمیشه هیچ وقت. حالا زمانی رو در نظر بگیرین که سیگمای این اعداد ماکسیمم به یه عددی رسیده و دیگه بیشتر نمیشه (میدونیم واسه مقدار زیاد شدنشم یه باندی هست دیگه) در این صورت کارتا از این به وقتی به یه نفر میرسن همون کارتو پاس میده به نفر بعد و یه سری کارت مشخص هستن که دارن دوری جا به جا میشن. از اونجایی که تعداد فرده یه کارت x هست حداقل که کارتی که شمارش مثل اونه توی این دور نیست و ماکسیمم کارت یه آدمیه که قرار نیست ماکسش تغییر کنه. خلاصه این کارتا که دوری میچرخن بلاخره این دوتا x با هم تو یه دست قرار میگیرن.
درسته؟ 
پاسخ:
سلام. بله درسته :)))
راه جالبی بودش. مرسی از مشارکتتون. امیدوارم بقیه هم مثل شما مشارکت داشته باشن D:
سلام
 تطابق x یالی چیه؟ 
پاسخ:
ایکس تا یال از گرافه که دو به دو راس مشترک ندارن. واسه تعریفای اینشکلی تو گراف میتونید از ویکی پدیا کمک بگیرید. 
وبلاگ خوبی دارید :)
پاسخ:
مرسی :*

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی