====== سوال ۴ ======




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


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


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



  - $\binom{2n-2}{n-1}$
  - $\binom{2n}{n}$
  - 2
  - $n$
  - $\frac{1}{2}\binom{2n}{n}$


 



<پاسخ>
گزینه (۱) درست است.

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

</پاسخ>


  * [[سوال ۳|سوال قبل]]
  * [[سوال ۵|سوال بعد]]