سوال ۳۳
۸ کارت بر روی هم قرار دارند. بر روی این کارت‌ها اعداد ۰ تا ۷ به ترتیب از بالا به پایین نوشته شده است (کارت ۰ روست). دو نوع بُر زدن داریم که در شکل مقابل آمده است. یکی «تعویض» که کارت‌ها را از رو دو به دو با هم تعویض می‌کند. دیگری «بر کامل» است که کارت را از رو به دو دسته‌ی ۴ کارتی تقسیم می‌کند و به صورت کامل دو دسته را با هم بُر می‌زند تا یک دسته کارت ۸تایی به دست آید. ترتیب قرار گرفتن کارت‌ها پس از یک بُر کامل و نیز یک تعویض در شکل نشان داده شده است. می‌خواهیم با حداقل تعداد بُر زدن‌ها (عددِ $B$) کاری کنیم که در نهایت کارت با یک عدد دل‌خواه به روی دسته‌کارت بیاید. بیش‌ترین مقدار $B$ چه‌قدر است؟
- ۳
- ۴
- ۵
- ۶
- ۷
پاسخ
گزینه (?) درست است.
اگر اعمال «تعویض» و «بر کامل» را به ترتیب با $f$ و $g$ نمایش دهیم٬ آن‌گاه کوتاه‌ترین راه برای رساندن اعداد از ۱ تا ۷ به‌رو به ترتیب به شکل زیر می‌باشد که در بین آن‌ها عدد ۷ بلندترین طول مسیر را دارد که طول آن برابر ۵ می‌باشد.
$1 \xrightarrow{f} 0$
$2 \xrightarrow{g} 4 \xrightarrow{g} 1 \xrightarrow{f} 0$
$3 \xrightarrow{f} 2 \xrightarrow{g} 4 \xrightarrow{g} 1 \xrightarrow{f} 0$
$4 \xrightarrow{g} 1 \xrightarrow{f} 0$
$5 \xrightarrow{f} 4 \xrightarrow{g} 1 \xrightarrow{f} 0$
$6 \xrightarrow{g} 5 \xrightarrow{f} 4 \xrightarrow{g} 1 \xrightarrow{f} 0$
$7 \xrightarrow{f} 6 \xrightarrow{g} 5 \xrightarrow{f} 4 \xrightarrow{g} 1 \xrightarrow{f} 0$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
