المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:تئوری نهایی اول:سوال ۱

سوال ۱

یک گراف ساده‌ی جهت‌دار بدون دور داریم. رأس‌ها به ترتیبی نامشخص، در یک ردیف از چپ به راست چیده شده‌اند. در هر مرحله، به طور تصادفی، یک یال انتخاب می‌شود که جهت آن به سمت چپ باشد؛ سپس جای این دو رأس در ترتیب عوض می‌شود. ثابت کنید پس از متناهی گام، به وضعیتی خواهیم رسید که جهت تمام یال‌ها به سمت راست باشند.

پاسخ

فرض کنید گراف دارای $n$ راس می‌باشد،ابتدا ثابت می‌کنیم برای هر $n$ می‌توانیم اعداد یک تا $n$ را به رئوس گراف طوری نسبت دهیم که هر یال از راسی با عدد متناظر کم‌تر به راسی با عدد متناظر بیش‌تر متصل باشد: با استقرا روی $n$ حکم را ثابت می‌کنیم: برای $n=1$ که حکم واضح است ، حال فرض کنید حکم برای $n$ برقرار باشد حکم را برای $n+1$ ثابت می‌کنیم:

با شروع از یک راس و رفتن از آن به یکی از رئوسی که به این راس مورد نظر یال دارند و ادامه این حرکت با توجه به اینکه گراف فاقد دور است به راس تکراری نمی‌رسیم و با توجه به اینکه گراف متناهی راس دارد باید به راسی برسیم که هیج یال ورودی ندارد،حال به این راس عدد 1 را نسبت می‌دهیم و با استفاده از فرض استقرا به بقیه رئوس می‌توان اعداد 2 تا $n-2$ را به گونه ای نسبت داد که حکم مسئله برقرار باشد.

حال داریم اگر به جای رئوس اعداد متانظرشان را در ترتیب ذکر شده قرار دهیم،با هر حرکت تعداد نا به جایی ها (دوتایی هایی که عدد کوچک‌تر در ترتیب مورد نظر پس از عدد بزرگ‌تر آمده است) دقیقا یک واحد کم میشود،دلیل این امر این است که در هر مرحله با تعویض مکان دو عدد مانند $a$ و $b$ هر دوتایی که هر دو زوج آن مخالف $a$ یا $b$ هستند که هیچ تغییر وضعیتی نمیدهد و به طبع آن تغییری در تعداد نابه‌جایی‌ها نمی‌دهد،ضمنا هر دوتایی که دقیقا یکی از دو زوج آن برابر $a$ یا $b$ است با دو تایی که عضو غیر $a$ و $b$ آن با عضو دیگر $a$ و $b$ میسازند با هم در مجموع تغییری در تعداد نابه‌جایی هاایجاد نمی‌کنند و دو تایی $a$ و $b$ هم دقیقا یک تغییر ایجاد می‌کنند.

حال داریم تعداد نابه جایی ها متناهی است زیرا تعداد رئوس گراف متناهی است بنابراین بعد از متناهی حرکت دیگر نمی‌توان حرکتی انجام داد زیرا در هر حرکت تعداد نابه‌جایی‌ها دقیقا یک واحد کاهش می‌یابد.


ابزار صفحه