Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۴:سوال ۲

سوال ۲

بردیا می‌خواهد در جدول زیر از خانه‌ی A به خانه‌ی B برود. در خانه‌هایی از این جدول که با هاشور مشخص شده‌اند، مانع وجود دارد. او در هر مرحله می‌تواند به یکی از خانه‌های مجاورِ ضلعی‌ِ خانه‌ی فعلی‌اش برود، ولی نمی‌تواند وارد خانه‌ای شود که قبلا در آن حضور داشته یا در آن مانع هست. بردیا به چند روش می‌تواند این مسیر را طی کند؟

  1. 96
  2. 48
  3. 104
  4. 80
  5. 64

پاسخ

گزینه (1) درست است.

در شکل زیر، ۴ بخش در جدول به وجود می‌آید که در هرکدام از آن‌ها تعدادی ضربدر وجود دارد که با خط‌چین به هم متصل شده‌اند. برای رفتن از هریک از ضربدرهای موجود در هر بخش به سمت دیگر خط‌چین آن، دقیقاً ۲ حالت وجود دارد. همچنین با رفتن به هریک از ضربدرها، باید به یکی از خط‌چین‌های مجاور آن برویم تا بتوانیم از آن ناحیه خارج شویم. برای خارج شدن از ناحیه‌ی اول، 2×2=4 حالت وجود دارد. 2 حالت برای ضربدری که از آن خارج می‌شویم وجود دارد، که ما به تقارن فرض می‌کنیم از ضربدر بالا خارج می‌شویم. 2 حالت هم برای نحوه رسیدن به ضربدر بالا وجود دارد.

و برای رسیدن به نقطه‌ی پایان در ناحیه‌ی نهایی نیز 2 حالت (با فرض مشخص بودن ضربدر ورود به ناحیه‌ی نهایی) وجود دارد. در نتیجه پاسخ مضربی از 8 است. با مشخص کردن تعداد بخش‌های مختلف دیده شده در حین مسیر (صفر، یک یا دو) می‌توانیم تعداد حالات مطلوب را بشماریم:

- 0 ناحیه: کافی است مشخص کنیم از کدام طرف وارد ناحیه‌ی نهایی شویم. در نتیجه این بخش مجموعاً ۲ حالت دارد.

- 1 ناحیه: با مشخص کردن ناحیه، مسیر حرکت تا ورود به آن ناحیه مشخص می‌شود. در ادامه تنها کافی است به ناحیه‌ی نهایی وارد شویم که در صورتی که در ابتدا به ناحیه‌ی بالا چپ رفته باشیم، 2 حالت و در غیر این صورت، 1 حالت دارد. در نتیجه این بخش در مجموع (2×2)+2=6 حالت دارد.

- 2 ناحیه: در این حالت ابتدا باید وارد ناحیه‌ی بالا چپ و سپس وارد ناحیه‌ی پایین راست شویم. باقی مسیر بین نواحی به صورت یکتا مشخص می‌شود. در نتیجه این بخش در مجموع 2×2=4 حالت دارد.

در نتیجه، در مجموع تعداد حالات برابر با 8×(2+6+4)=8×12=96 است.


ابزار صفحه