جدولی n×n داریم که سطرهای آن از بالا به پایین و ستونهای آن از چپ به راست با اعداد 1 تا n شمارهگذاری شدهاند. خانهی واقع در سطر i و ستون j را با (i,j) نشان میدهیم. میخواهیم از خانهی (1,1) به خانهی (n,n) برویم. حرکتهای مجاز به صورت زیر هستند:
چند مسیر مجاز دارای کمترین هزینه هستند؟
پاسخ
گزینه (۱) درست است.
ادعا میکنیم تمام مسیرها هزینهی یکسانی دارند. برای خانهی (i,j) پتانسیل i\cdot j را تعریف میکنیم. توجه کنید در هر حرکت دقیقاً به اندازهی هزینهی آن مرحله به مقدار پتانسیل اضافه میشود. در ابتدا مقدار پتانسیل 1 و در انتها مقدار پتانسیل n^2 میرسد. بنابراین همهی راهها دارای هزینهی n^2-1 هستند.