Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

روی یک برکه مانند شکل زیر، 10 برگ در یک ردیف، از چپ به راست، در جایگاه‌های 1 تا 10 قرار دارند. در سمت چپِ این برکه‌، 10 قورباغه با شماره‌های 1 تا 10 حضور دارند و می‌خواهند با عبور از روی برگ‌ها، به سمت راست برکه بروند که می‌توان آن را جایگاه یازدهم در نظر گرفت. در هر لحظه، حداکثر یک قورباغه می‌تواند روی هر برگ بنشیند، و بعد از جهیدنِ یک قورباغه از روی برگی که بر آن نشسته، آن برگ به زیر آب می‌رود و دیگر قابل استفاده نیست. هر قورباغه قدرت جهش مخصوص به خود را دارد؛ قورباغه‌ی شماره‌ی i (برای 1i10) می‌تواند در هر حرکت، حداکثر i جایگاه به سمت راست بجهد. مثلاً قورباغه‌ی شماره‌ی 2، مطابق شکل زیر، می‌تواند در یک حرکت از ابتدای برکه به روی یکی از برگ‌های اول یا دوم بجهد. با توجه به شرایط گفته‌شده، حداکثر چند قورباغه می‌توانند با جهیدن روی برگ‌ها، از برکه رد شوند؟

  1. 5
  2. 6
  3. 7
  4. 8
  5. 9

پاسخ

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

برای اثبات نیاز به نشان دادن دو نکته وجود دارد: اول اینکه 7 قورباغه می‌توانند از روی برکه عبور کنند و دوم اینکه 8 قورباغه نمی‌توانند. عبور 7 قورباغه به شکل زیر انجام‌پذیر است:

  1. لیست‌های مرتبقورباغه چهارم با پرش از روی برگ‌های 4 و 8 به سمت راست برکه می‌رسد.
  2. قورباغه پنجم با پرش از روی برگ 5 به سمت راست برکه می‌رسد.
  3. قورباغه ششم با پرش از روی برگ 6 به سمت راست برکه می‌رسد.
  4. قورباغه هفتم با پرش از روی برگ 7 به سمت راست برکه می‌رسد.
  5. قورباغه هشتم با پرش از روی برگ 3 به سمت راست برکه می‌رسد.
  6. قورباغه نهم با پرش از روی برگ 2 به سمت راست برکه می‌رسد.
  7. قورباغه دهم با پرش از روی برگ 1 به سمت راست برکه می‌رسد.

برای نشان دادن اینکه 8 قورباغه نمی‌توانند به سمت راست برکه برسند، کافی است توجه کنیم که هر قورباغه باید از روی حداقل چند برگ بجهد.

  • لیست‌های بدون ترتیبقورباغه‌های دهم تا ششم باید از روی یک برگ بجهند.
  • قورباغه‌های پنجم و چهارم باید از روی دو برگ بجهند.
  • قورباغه‌ی سوم باید از روی سه برگ بجهد.
  • قورباغه‌ی دوم باید از روی پنج برگ بجهد.
  • قورباغه‌ی اول باید از روی همه‌ی 10 برگ بجهد.

حال برهان خلف می‌گیریم که 8 قورباغه به سمت راست برکه رسیده‌اند. بنابراین برای رسیدن این 8 قورباغه به سمت راست برکه، حداقل تعداد برگ‌های به زیر آب رفته به صورت زیر است: 1+1+1+1+1+2+2+3=12

با این حال ما تنها 10 برگ داریم و در نتیجه برهان خلف رد می‌شود. ثابت می‌شود که حداکثر 7 قورباغه می‌توانند از روی برکه عبور کنند.


ابزار صفحه