سوال ۳۳
یک جدول $۱ \times ۷$ خالی داریم که به خانه‌های آن از سمت چپ به راست، شماره‌های ۰ تا ۶ را نسبت داده‌ایم. می‌خواهیم عناصر $a$٬ $b$ تا $g$ را به آن اضافه کنیم و برای هر کدام، یک مکان اولیه مطابق جدول روبه‌رو در نظر گرفته‌ایم.
عناصر مذکور به ترتیب دل‌خواه برای درج به جدول وارد می‌شوند. اگر مکان اولیه‌ی عنصر $x$ برابر $k$ باشد (مثلا برای $a$ این مقدار برابر ۳ است)، به ترتیب مکان‌های $k$, mod ۷ ($k+1$), mod ۷ ($k+2$), تا mod ۷ ($k+6$), را بررسی می‌کنیم و $x$ را در اولین مکان خالی قرار می‌دهیم. می‌دانیم $j$ mod $i$ باقی‌مانده‌ی تقسیم صحیح عدد $i$ بر عدد $j$ است. به ازای ترتیب‌های مختلف اضافه کردن عناصر $g$,…, $b$,$a$ به جدول، کدام‌یک از حالت‌های زیر نمی‌تواند حاصل شود؟
- هیچ‌کدام، تمام موارد می‌توانند باشند
پاسخ
گزینه (۲) درست است.
در مورد گزینه (ب)٬ چون $a$ در مکان ۶ قرار گرفته است معلوم می‌شود که قبل از آن مکان‌های ۴٬۳ و ۵ پر بوده است که یکی از آن‌ها یعنی مکان ۴ توسط $f$ پر شده است٬ بنابراین $f$ قبل از $a$ وارد جدول شده است.
از طرف دیگر مکان اولیه‌ی $f$ خانه ۶ می‌باشد که هنگام ورود به جدول در صورت پر بودن آن خانه به یک خانه دیگر می‌رود. لحظه ورود عنصر $f$ به جدول٬ خانه ۶ خالی بوده است و لزومی نداشت که به خانه‌ی دیگر برود.
ترتیب ورود حروف به جدول در مورد گزینه‌های الف٬ ج و د به ترتیب به شکل زیر می‌تواند باشد:
الف: $$a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e \longrightarrow f \longrightarrow g$$
ج: $$a \longrightarrow c \longrightarrow e \longrightarrow g \longrightarrow b \longrightarrow d \longrightarrow f$$
د: $$a \longrightarrow d \longrightarrow e \longrightarrow f \longrightarrow c \longrightarrow g \longrightarrow b$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
