مساله ی تلویزیون ، مرحله ۲ دوره ۱۸

تلویزیون

ایستگاه راه‌آهن شهر المپیادی‌ها n سالن انتظار دارد و در هر سالن یک تلویزیون برنامه پخش می‌کند. می‌دانیم صدا و سیمای کشور المپیادی‌ها دارای n شبکه‌ی تلویزیونی است. در اولین روز سال ۱۳۸۷ در تلویزیون هر سالن انتظار٬ یکی از این شبکه‌ها پخش می‌شود٬ به طوری که هر یک از این n شبکه بر روی دقیقاً یکی از این n تلویزیون دیده می‌شود. می‌دانیم راه‌آهن ترتیب پخش شبکه‌ها روی این n تلویزیون را به ترتیب خاصی در پایان هر روز تغییر می‌دهد.

یک تعریف: یک ترتیب نوشتن اعداد ۱…تا n در یک ردیف را یک جای‌گشت از این اعداد گوییم. مثلاً <۴٫۵٫۲٫۱٫۳> (از چپ به راست) یک جای‌گشت از اعداد ۱ تا ۵ است و ۲ عدد سوم این جای‌گشت است.

راه‌آهن یک جای‌گشت سرّی به نام π از اعداد ۱ تا n دارد که ما از آن بی‌اطلاعیم. البته می‌دانیم که به ازای هر i٬ اگر تلویزیونی در یک روز شبکه‌ی iام را نشان دهد٬ در روز بعد حتماً شبکه‌ی شماره‌ی πi (یعنی عدد iام از جای‌گشت π) را نشان خواهد داد.

متأسفانه ما هر روز مجازیم تنها یکی از سالن‌های انتظار (و در نتیجه فقط تلویزیون آن سالن) را به انتخاب خود ببینیم و به این ترتیب شماره‌ی شبکه‌ای که در آن پخش می‌شود را متوجه شویم.

روشی برای انتخاب سالن انتظار در هر روز و دیدن تلویزیون آن ارائه کنید تا به کمک آن در حداکثر 2n−1 روز به جای‌گشت π دست پیدا کنیم و در نتیجه روند تغییر پخش شبکه‌ها در تلویزیون‌ها را بفهمیم.

اگر همچین سوالی بیاد باید به نوشتن روش اکتفا کنیم ؟ اثبات اینکه روش درسته ، هم لازمه ؟‌