سوال ۷
دیوار زیر را در نظر بگیرید:
این دیوار از تعدادی آجر تشکیل شده است. به جز آجرهای سطر پایین، زیر هر کدام از آجرها دو آجر کوچک‌تر وجود دارد که آن‌ها را فرزندان آجر گفته شده می‌نامیم. در هر یک از شرایط زیر، گوییم آجر $X$ به آجر $Y$ راه دارد:
- $Y$ فرزند $X$ باشد.
- هر دو آجر در یک سطر بوده و مرز مشترک داشته باشند.
- هر دو آجر در یک سطر بوده و یکی در انتها و دیگری در ابتدای سطر باشد.
حال می‌خواهیم از آجر بالای دیوار شروع کنیم، هر مرحله به یک آجر که به آن راه داریم، برویم و کار را در یکی از آجرهای سطر پایین تمام کنیم. ممکن است در این مسیر، چند آجر از سطر پایین ببینیم و لزومن به محض رسیدن به سطر پایین، کار را تمام نمی‌کنیم. هم‌چنین تنها دنباله‌ی آجرها در مسیر مهم است و نحوه‌ی رفتن آن‌ها به یک‌دیگر مهم نیست. برای مثال دو آجر سطر دوم (از بالا) را در نظر بگیرید. این دو هم به دلیل شرط (۲) و هم به دلیل شرط (۳) به هم راه دارند. حال اگر در مسیری، از یکی از آن‌ها به دیگری برویم، مهم نیست از شرط (۲) استفاده کرده‌ایم یا شرط (۳). هم‌چنین با توجّه به شرایط گفته شده، امکان حرکت رو به بالا وجود ندارد. چند مسیر به شکل گفته شده وجود دارد، طوری که از هر آجر حداکثر یک بار بگذریم؟
- $3255 \times 2^4$
- $3255 \times 2^5$
- $2^{17}$
- $3255 \times 2$
- $2^{14}$
پاسخ
گزینه (۲) درست است.
فرض کنید به یک سطر با $k$ آجر وارد شده‌ایم و می‌خواهیم تعداد روش‌های رفتن به سطر پایین را محاسبه کنیم. یک حالت این است که از همان آجری که به آن وارد شدیم، مستقیمن به پایین برویم. حالت دیگر این است که یکی از $(k-1)$ آجر دیگر را انتخاب کرده و به دو طریق به آن برویم (راست‌گرد یا چپ‌گرد)؛ البتّه سطر دوم از موضوع گفته شده استثناست و راست‌گرد یا چپ‌گرد بودن مسیر تفاوتی در دنباله ایجاد نمی‌کند. در انتها نیز پس از مشخّص شدن آجری که باید از آن پایین برویم، به دو حالت آجر پایینی انتخاب می‌شود. پس پاسخ برابر است با: $$2 \times (1+1) \times 2 \times (1 + 2 \times 3) \times 2 \times (1 + 2 \times 7) \times 2 \times (1 + 2 \times 15) = 3255 \times 2^5$$