روی یک برکه مانند شکل زیر، 10 برگ در یک ردیف، از چپ به راست، در جایگاههای 1 تا 10 قرار دارند. در سمت چپِ این برکه، 10 قورباغه با شمارههای 1 تا 10 حضور دارند و میخواهند با عبور از روی برگها، به سمت راست برکه بروند که میتوان آن را جایگاه یازدهم در نظر گرفت. در هر لحظه، حداکثر یک قورباغه میتواند روی هر برگ بنشیند، و بعد از جهیدنِ یک قورباغه از روی برگی که بر آن نشسته، آن برگ به زیر آب میرود و دیگر قابل استفاده نیست. هر قورباغه قدرت جهش مخصوص به خود را دارد؛ قورباغهی شمارهی i (برای 1≤i≤10) میتواند در هر حرکت، حداکثر i جایگاه به سمت راست بجهد. مثلاً قورباغهی شمارهی 2، مطابق شکل زیر، میتواند در یک حرکت از ابتدای برکه به روی یکی از برگهای اول یا دوم بجهد. با توجه به شرایط گفتهشده، حداکثر چند قورباغه میتوانند با جهیدن روی برگها، از برکه رد شوند؟
پاسخ
گزینه (3) درست است.
برای اثبات نیاز به نشان دادن دو نکته وجود دارد: اول اینکه 7 قورباغه میتوانند از روی برکه عبور کنند و دوم اینکه 8 قورباغه نمیتوانند. عبور 7 قورباغه به شکل زیر انجامپذیر است:
برای نشان دادن اینکه 8 قورباغه نمیتوانند به سمت راست برکه برسند، کافی است توجه کنیم که هر قورباغه باید از روی حداقل چند برگ بجهد.
حال برهان خلف میگیریم که 8 قورباغه به سمت راست برکه رسیدهاند. بنابراین برای رسیدن این 8 قورباغه به سمت راست برکه، حداقل تعداد برگهای به زیر آب رفته به صورت زیر است: 1+1+1+1+1+2+2+3=12
با این حال ما تنها 10 برگ داریم و در نتیجه برهان خلف رد میشود. ثابت میشود که حداکثر 7 قورباغه میتوانند از روی برکه عبور کنند.