شاززز

سلام خسته نباشید مرحله دوم خوب بود ؟
اینم کلیدی که قول داده بودم... (با کمک بهروز)
سوال ۱:
حقوق هر فرد را در وضعیتی که iنفر در شرکت اول بروند Pi و در وضعیتی که به شرکت دوم بروند Fi می نامیم... برهان خلف می زنیم... فرض کنیم وضعیت جواب نداریم
اگر nنفر به شرکت اول بروند،   F1 > Pn است، (وگرنه وضعیت جواب بود)، ‌حالا اگر n-1 نفر به شرکت اول بروند Pn-1

تناقض است. ‍‍‍پس این بین یکی از نامساوی ها غلط بوده و حالت جواب بوده.
//=================================================
سوال ۲:
گراف جایگشت را می کشیم،‌طوری که از i به πi یالی جهت دار می کشیم. گراف افرازی از چند دور است. در هر عمل طول هر دور نصف می شود، (چرا ؟) پس از k مرحله همه دور ها طولشان یک می شود.
ب) جایگشت 2, 3, 4, ..., n-1, n, 1را در نظر بگیرید و پس از هر مرحله جای یک را بررسی کنید...
//==================================================
سوال ۳:
الف) درخت را از یک راس آویزان می کنیم،‌حالا پایین ترین یال خراب (یالی که عوارض دو سرش یکسان شده اند) را در نظر بگیرید (و آن را uv بنامید، طوری که u پدر v باشد.) یکی از بچه‌های v مانند w را انتخاب می‌کنیم. عوارض یال vw را عوض می‌کنیم. با این حساب uv دیگر خراب نیست. از طرفی ممکن است چند یال مانند vx یا wy خراب شده باشند. (که همگی پایین‌تر از uv هستند.) ، و ... استقرا
پایه‌ی استقرا: برگ. چون عوارض صفر نداریم، ...
ب) *ها شهرها هستند. عوارض جاده‌ها درون پرانتز نوشته شده است.
*-(a,b)-*-(0,1)-*-(a,b)-*-(0,1)-*-(a,b)-*
بررسی کنید.
//==================================================
سوال ۴:
یک «وضعیت» را برای مسئله اینگونه تعریف می‌کنیم:
«جاده‌ی خروجی هر میدان کدام است؟ و ما کجا هستیم؟»
واضح است که تعداد حالات متناهی است. پس اگر از وضعیت ابتدایی شروع کنیم، بعد از طی چند مرحله به یک وضعیت تکراری برمی‌گردیم. دور حاصل از وضعیت‌ها (در گراف وضعیت) را در نظر می‌گیریم. ادعا می‌کنیم با پیمودن این دور، از همه‌ی شهرها گذشته‌ایم.
برهان خلف: شهری را در نظر بگیرید که در گراف وضعیت بازدید شده باشد و دارای حداقل یک همسایه‌ی بازدید‌نشده باشد. (آن را v بنامید) این دور را d_v (تعداد همسایه‌های v) بار طی می‌کنیم. حتما یک بار پلیس جاده‌ی منتهی به شهر بازدید نشده را باز می‌کند. تناقض...
//==================================================
سوال ۵:
توضیح بیشتر در مورد الگوریتم داده شده:
در ابتدا n دسته‌ی ۱ عضوی داریم. هر بار، دو دسته‌ی دلخواه را انتخاب می‌کنیم، و همه‌ی اعضای دسته‌ی کوچکتر را در دسته بزرگ می‌ریزیم و به اندازه‌ی تعداد اعضای دسته‌ی کوچک پول خرج می‌کنیم (به b اضافه می‌کنیم)
الف) در هر مرحله، اگر x دسته داشته باشیم، به x/2 تا دسته ۲تایی تقسیم می‌کنیم. و دو به دو با هم تلفیق می‌کنیم.
ب) هر عدد حداکثر در k عملیات جابه‌جایی شرکت داشته. (چرا؟) پس در کل k * 2^k تا عمل انجام شده.
(برای اطلاعات بیشتر در مورد کاربرد این الگوریتم، در مورد داده‌ساختار DisjointSet تحقیق کنید. منابع: ویکی‌پدیا، CLRS، Creative و JBL)

[پس از بررسی حل خود برای تخمین بهتر کف حتما در نظرسنجی شرکت کنید.]