Processing math: 60%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

جدولی n×n داریم که سطرهای آن از بالا به پایین و ستون‌های آن از چپ به راست با اعداد 1 تا n شماره‌گذاری شده‌اند. خانه‌ی واقع در سطر i و ستون j را با (i,j) نشان می‌دهیم. می‌خواهیم از خانه‌ی (1,1) به خانه‌ی (n,n) برویم. حرکت‌های مجاز به صورت زیر هستند:

  • حرکت از (i,j) به (i+1,j) با هزینه‌ی j.
  • حرکت از (i,j) به (i,j+1) با هزینه‌ی i.

چند مسیر مجاز دارای کم‌ترین هزینه هستند؟

  1. \binom{2n-2}{n-1}
  2. \binom{2n}{n}
  3. 2
  4. n
  5. \frac{1}{2}\binom{2n}{n}

پاسخ

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

ادعا می‌کنیم تمام مسیرها هزینه‌ی یکسانی دارند. برای خانه‌ی (i,j) پتانسیل i\cdot j را تعریف می‌کنیم. توجه کنید در هر حرکت دقیقاً به اندازه‌ی هزینه‌ی آن مرحله به مقدار پتانسیل اضافه می‌شود. در ابتدا مقدار پتانسیل 1 و در انتها مقدار پتانسیل n^2 می‌رسد. بنابراین همه‌ی راه‌ها دارای هزینه‌ی n^2-1 هستند.


ابزار صفحه