المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۲۲

سؤال ۲۲

یک قورباغه روی نقطه‌ی صفر محور مختصات نشسته است. این قورباغه می‌تواند به سمت جلو بجهد، ولی طول پرش آن در $i$امین جهش به‌ دلخواه خودش $i$ یا $i+1$ واحد است. او پس از چند جهش می‌تواند به نقطه‌ی ۱۳۸۱ برسد؟ و چند جهش دیگر لازم است تا از آن‌جا به نقطه‌ی ۲۰۰۳ برسد؟

  1. ۵۲ و ۱۱
  2. ۵۲ و ۱۲
  3. ۵۲، نمی‌تواند برسد
  4. ۳۷ و ۹
  5. به هیچ‌کدام نمی‌تواند برسد.

پاسخ

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

اگر تصور کنیم که در حرکت $i$ام به اندازه $i$ واحد به جلو بجهد آن‌گاه خواهیم داشت:

$$1+2+3+...+n<1381<1+2+3+...+(n+1)$$

$$\Rightarrow \frac{n(n+1)}{2}<1381 \Rightarrow n(n+1)<2762 \Rightarrow n<53$$

به ازای $n=52$ و در حالتی که قورباغه در حرکت $i$ام به اندازه $i$ واحد بجهد به نقطه $\frac{52\times53}{2}$ یعنی ۱۳۷۸ خواهد رسید. بنابراین کافی است برای رسیدن به نقطه ۱۳۸۱ در ۵۲ حرکت٬ فقط در سه جهش از ۵۲ جهش به‌جای $i$ واحد جهیدن٬ به اندازه $i+1$ واحد بجهد.

اگر تصور کنیم که قورباغه از حرکت ۵۲ به بعد در هر حرکت کم‌ترین مقدار ممکن را بجهد آن‌گاه بعد از ۱۰ حرکت به نقطه ۱۹۵۶ خواهد رسید زیرا:$(1381)+53+54+55+...+62=1956$. و اگر قورباغه در هر حرکت بیش‌ترین مقدار ممکن را بجهد آن‌گاه بعد از ۱۰ حرکت به نقطه ۱۹۶۶ خواهد رسید که عقب‌تر از نقطه ۲۰۰۳ می‌باشد. اما نقطه مقصد بعد از ۱۱ حرکت به ترتیب در حالاتی که قورباغه کم‌ترین مقدار و نیز بیش‌ترین مقدار را بجهد برابر ۲۰۱۹ و ۲۰۳۰ می‌شود. به این معنا که رسیدن به نقطه ۲۰۰۳ از نقطه ۱۳۸۱ با شرایط اشاره شده غیر ممکن است.


ابزار صفحه