انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
ثابت کنید تعداد درخت هایی که دو راس دارند که اختلاف جمع فاصله هایشان دقیقا 1 است فرد است
ثابت کنید این گراف دارای مولفه ای به اندازه ی n+1 هست که یال های یه رنگ دارند
پیدا کردن راسی در درخت که دارای فاصله ی مینیمم است
برابری خطوط عمودی و افقی دور هامیلتوی در جدولی $8×8$
مشکل در فهمیدن قضیه ماتریس درخت کیرشهف
پیدا کردن گراف دوبخشی کامل یکرنگ
حداکثر تعداد یال‌های گراف بدون مثلث
نگهبانان می خواهند دزدی را که به قصر سلطان بغداد وارد شده بود، دستگیر کنند. برای گرفتن دزد، نگهبان باید با او در یک اتاق باشد. قصر دارای 1000 اتاق است که به وسیله در ها به هم مربوط اند. طرح ساختمان قصر به گونه ای است که از یک اتاق به اتاق مجاور، جز از طریق دری که آنها را به هم وصل کرده است(و تنها یک در) نمی توان وارد شد. نکته: اگر در یک راهرو دزد و نگهبان باشند، دزد دستگیر می شود. ثابت کنید، هر طرحی که قصر داشته باشد، 10 نگهبان می توانند با برنامه ریزی، دستگیری دزد را تضمین کنند. قسمت دوم ( جدید): ثابت کنید 5 نگهبان قادر به انجام این کار نیستند. قسمت سوم (جدید): ثابت کنید 6 نگهبان قادر به انجام این کار اند.
میشه یکم بیشتر توضیح بدی سوال نا مفهمومه اگه میشه به جای داستان از تعاریف ریاضی استقاده کنید که یکم دقیق تر باشه ممنون.
2015-04-22 02:45:52 -0500 احمدرضاسوال دقیقا همینه که از روی کتابی است ( نمی دانم کدام کتاب!) در ضمن المپیاد کامپیوتر فرمول نیست، تفکر و استدلاله! اگر کسی جواب رو می دونه بگه لطفا!
2015-04-22 10:29:24 -0500 متد محمدمرکز درخت: تو یک درخت $n$ راسی، یک راس وجود داره که اگه حذفش کنیم، سایز تمام مولفه های همبند ایجاد شده، حداکثر برابر $\lfloor \frac{n}{2} \rfloor$ میشه. اثباتش سادست ازش صرف نظر میکنم.
حالا اگه سوال رو تبدیل به گراف کنیم(که تبدیل به درخت میشه)، با استقرا ثابت میکنیم که برای یک درخت $n$ راسی، $\lceil log_2^n \rceil$نگهبان برای دستگیر کردن دزد کافیه.
پایه که برای n = 1, 2, 3 سادست هیچی. فرض کنید برای مقادیر کوچکتر از n هم درست باشه و ما میخوایم n رو ثابت کنیم.
یک نگهبان میره روی مرکز درخت می ایسته. میدونیم مولفه های ایجاد شده توسط حذف این راس، حداکثر $\lfloor \frac{n}{2} \rfloor$ راسی اند. پس طبق فرض استقرا، $\lceil log_2^n \rceil - 1$ کافیه برای پیدا کردن دزده تو این زیردرخت ها. همونجوری که یه نگهبان روی مرکزه درخته، بقیه $\lceil log_2^n \rceil - 1$ نگهبان میرن تو این زیردرخت ها و یکی یکی جستجوشون میکنن و دزد هم نمیتونه ازین زیردرختها خارج شه چون مرکز درخت اشغال شده. پس با $\lceil log_2^n \rceil$ نگهبان دزد رو گرفتیم.
الان اگر سوال مرحله 2 بوود کامل نمیشدی چون n=1 جوابش صفر نیست ! و باید جدا مطرحش کنی !
2015-04-22 12:59:56 -0500 طوفانمعذرت میخوام ولی هر چی فکر میکنم متوجه نمیشم چرا میگید گراف سوال درخته !
2015-04-23 04:28:25 -0500 قدیمیدوست عزیز، سقف لگاریتم 1 در مبنای 2، صفره! و واضحه که با صفر تا نگهبان نمیشه دزد رو دستگیر کرد. پس پایه ی استقرایی که دارید می زنید باید 2 باشه. همون طور که تو قسمت نظرات پاسخ عطا گفتم، باید حالت تک رأس رو توی اثبات گام استقرا جداگانه حل کنید.
2015-04-23 07:32:35 -0500 م زمانیثابت می کنیم که برای هر n با m نگهبان می توان دزد را گرفت به طوری که دو به توان m بزرگتر از n باشه: روی n استقرا می زنیم : پایه که برای n=2 معلومه گام استقرا:یه راس دلخواه رو در نظر می گیریم اگر همه ی بچه هاش دارای زیر درخت به اندازه حداکثر n/2 بودند یه نگهبان می زاریم رو اون راس بعد برای هر بچه و زیر درختش طبق فرض با بقیه نگهبان ها می گردیم اگر هم نبود یه بچه رو که زیر درختش بیشتر از n/2 تا داشت رو می گیریم و جایگزین این راسه می کنیم با این کار حتما یه جایی به خواستمون می رسیم
جوب داره! اولا بهتر بود به جای اینکه بنویسی "دو به توان m از n بزرگتر باشه"، راحت بگی سقف log n. چون از حرفت این برداشت میشه که m بزرگتر مساوی سقف log n ه. در ضمن جوب اصلیت اینه که اگر یه زیر درختی از زیر درختای رأسی که در نظر گرفتی تک رأس باشه، نمی تونی از فرض استقرا استفاده کنی.
2015-04-22 12:04:35 -0500 م زمانیدلیلشم اینه که استقرات از n = 2 شروع میشه. و همچنین نمی تونی از n = 1 شروعش کنی. چون حکم به ازای n = 1 غلطه! پس باید حالتی که زیر درخت تک رأسی باشه رو جداگانه در نظر بگیری و بگی که در آخر نگهبانا رو می فرستیم تا اون تک رأسیا رو هم بررسی کنن.
2015-04-22 12:13:49 -0500 م زمانینه m بزرگتر از log n ه چون برای n=2 نمی تونی با 1 دونه پیدا کنی بعدشم اگر یکی باشه بازم مشکل نداره چون این یارو رو زمانی که یه نگهبان گذاشتیم روش بازم یه نگه بان دیگه هست چون این یارو با بچش هست و حداقل 2 تا هستند
2015-04-22 13:14:37 -0500 عطانه منم نگفتم اثبات شما کلا غلطه. فقط گفتم این حالت رو باید جداگانه در نظر بگیرید. در ضمن فراموش کردم این رو بگم که این فرض باید به صورت سؤال اضافه بشه که اگر یکی از نگهبانا تو راه رسیدن به یه اتاق دیگه دزد رو ببینه هم دزد دستگیر میشه. یعنی حرفی که شما زدی درسته چون صورت سؤال ناقصه.
2015-04-23 07:19:22 -0500 م زمانیولی از طرفی شما اثبات کردی که حداقل تعداد نگهبان مورد نیاز سقف log n ه. ولی اثبات نکردین که تو هر حالتی با دقیقا سقف log n تا نگهبان میشه دزد رو دستگیر کرد. در واقع اگر اون فرضی رو که تو نظر قبلی گفتم به صورت سؤال اضافه نکنیم، نمیشه اثباتش کرد.
2015-04-23 07:24:44 -0500 م زمانی