المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۶:سوال ۷

المپیادها

فرض کنید که $n$ دانش‌آموز و $n$ المپیاد داریم و قرار است در هر المپیاد یک دانش‌آموز پذیرفته شود. تمام دانش‌آموزان در تمام المپیاد‌ها شرکت می‌کنند و هیچ دو دانش‌آموزی در یک المپیاد نمره‌ی مساوی نمی‌گیرند. هر دانش‌آموز یک فهرست اولویت $n$ تایی برای $n$ امپیاد (یعنی یک جایگشت از $n$ المپیاد) پر می‌کند و علاقه‌مندی خود را به ترتیب مشخص می‌کند.

یک گزینش پایدار را به این صورت تعریف می‌‌کنیم که هر دانش‌آموز در یک المپیاد انتخاب شده باشد و هیچ دو زوج (دانش‌آموز ,المپیاد) مانند $(O,S)$ و $(O',S')$ وجود نداشته باشد به قسمی که دانش‌آموز $S$ در المپیاد $O'$ نمره‌ای بیش‌تر از دانش‌آموز $S'$ در المپیاد $O'$ داشته باشد و نیز علاقه‌اش به المپیاد $O'$ بیش‌تر ازعلاقه‌اش به المپیاد $O$ باشد.

الگوریتم زیر را در نظر بگیرید:

  1. در ابتدا، هیچ دانش‌آموزی در هیچ المپیادی رد نشده است.
  2. هر یک از دانش‌آموزان با توجه به فهرست الویت خود، اولین المپیادی را انتخاب می‌کند که در آن رد نشده باشد و برای آن درخواست می‌دهد. در صورتی که چنین المپیادی وجود نداشته باشد، کار پایان می‌یابد.
  3. در هر کدام از المپیادها، از میان دانش‌‌آموزان درخواست دهنده برای آن المپیاد، دانش‌آموزی که در آن المپیاد نمر‌ه‌ی بالاتری آورده باشد پذیرفته می‌شود و سایر دانش‌آموزان درخواست‌دهنده، در صورت وجود، در آن ‌المپیاد رد می‌شوند.
  4. اگر در هر المپیاد یک دانش‌آموز پذیرفته شده باشد، الگوریتم پایان می‌یابد. در غیر این صورت، دوباره به مرحله‌ی ۱ برمی‌گردیم.

الف)ثابت کنید که الگوریتم فوق وقتی پایان می‌یابد که در هر المپیاد یک دانش‌آموز پذیرفته شده باشد.

ب) ثابت کنید که وقتی الگوریتم فوق پایان می‌یابد، یک گزینش پایدار به‌دست آمده است.

پاسخ

برای اثبات هر دو قسمت مسئله از لم زیر که اثبات آن با توجه به الگوریتم بدیهی است، استفاده می‌کنیم:

لم: در صورتی که در یک دور از اجرای الگوریتم، دانش‌آموز $S$ در المپیاد $O$ پذیرفته شد، در دورهای بعد، در هر دور لااقل یک نفر به المپیاد $O$ درخواست می‌دهد و نمره‌ی کسی که در این المپیاد پذیرفته می‌شود بیش‌تر یا مساوی با نمره‌ی $S$ در این المپیاد است.

اثبات: چون دانش‌آموز $S$ در المپیاد $O$ پذیرفته شده است، پس در این دور اجرای الگوریتم تغییری در لیست المپیادهایی که $S$ در آن‌ها حذف شده است، به وجود نمی‌آید. پس در دور بعدی نیز $S$ باز به $O$ درخواست می‌دهد. بنابراین تنها در صورتی ممکن است $S$ در $O$ پذیرفته نشود که یک دانش‌آموز که در $O$ نمره‌ای بیش از $S$ کسب کرده است، برای این المپیاد درخواست‌ دهد و در آن پذیرفته گردد. بنابراین در هر دور اجرای الگوریتم لااقل یک نفر در این المپیاد پذیرفته می‌شود که نمره‌ی او از نمره‌ی $S$ بیش‌تر است.

الف) با توجه به الگوریتم دیده می‌شود که در هر دور اجرای الگوریتم، حداقل یک دانش‌آموز در یک المپیاد رد می‌شود. بنابراین الگوریتم حداکثر $n^2$ دور می‌تواند طول بکشد و نهایتا متوقف خواهد شد. برای اثبات این که الگوریتم تنها زمانی پایان می‌یابد که در هر المپیاد یک دانش‌آموز پذیرفته شده باشد، کافی است ثابت کنیم که هیچ‌گاه شرط خاتمه‌ی بند ۱ الگوریتم برقرار نمی‌شود؛ یعنی هیچ‌گاه ممکن نیست که یک دانش‌آموز در همه‌ی المپیاد‌ها رد شده باشد. اگر یک دانش‌آموز مانند $S$ در یک دور در همه‌ی المپیاد‌ها رد شده باشد، باید یک المپیاد مانند $O$ وجود داشته باشد که هیچ‌کس به آن دخواست نداده است. (چون در غیر این صورت به هر یک ا ز المپیاد‌ها باید دقیقا یک درخواست داده شده باشد.) ولی چون $S$ در $O$ رد شده است، ئس باید یک بار به $O$ درخواست داده باشد. ولی بنا به لم، در این صورت باید در این دور هم لااقل یک نفر به $O$ درخواست داده باشد. این تناقض ثابت می‌کند که دانش‌آموزی که در همه‌ی المپیاد‌ها رد شده باشد، وجود ندارد.

ب) دو زوج مانند $(O,S)$ و $(O',S')$ در نظر می‌گیریم. فرض کنیم که علاقه‌ی $S$ به $O'$ بیش از علاقه‌ی او به $O$ است. بنابراین چون در نهایت $S$ در $O$ پذیرفته شده است، پس باید یک بار به $O'$ هم درخواست داده باشد. در نتیجه بنا به لم باید پس از این درخواست در هر دور دانش‌آموزی در $O'$ پذیرفته شود که نمره‌ی او از نمره‌ی $S$ در $O'$ بیش‌تر باشد. بنابراین نمره‌ی $S'$ هم باید از نمره‌ی $S$ در $O'$ بیش‌تر باشد. بنابراین با توجه به تعریف گزینش پایدار، گزینش به‌دست آمده توسط الگوریتم یک گزینش پایدار است.


ابزار صفحه