المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۰

۱۳۸۶ وزنه با وزن‌های متفاوت و یک ترازو در اختیار داریم. در هر مرحله می‌توانیم وزن دو وزنه را با ترازو مقایسه کنیم. با حداقل چند بار مقایسه می‌توانیم با اطمینان اولین و دومین وزنه را از لحاظ سبکی پیدا کنیم؟

  1. ۱۳۸۵
  2. ۲۷۷۲
  3. ۱۳۸۶
  4. ۱۳۹۶
  5. ۲۷۶۹

پاسخ

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

در هر مقایسه بین ۲ عدد، عدد بزرگ‌تر قطعن کوچک‌ترین عدد نیست. پس می‌توان در هر بار مقایسه یکی از اعداد را حذف کرد.

در هر مرحله اعداد را دوبه‌دو باهم مقایسه می‌کنیم و نصف اعداد حذف می‌شوند. پس در $⌈log_2 1386 ⌉=11$ مرحله به کوچک‌ترین عدد می‌رسیم. با این روش، ۱۳۸۵ مقایسه انجام داده‌ایم (با استقرا ثابت کنید برای پیدا کردن کوچک‌ترین عدد در بین $n$ عدد $n-1$ مقایسه لازم و کافی است).

دراین‌صورت دومین کوچک‌ترین عدد، در مقایسه با کوچک‌ترین عدد حذف شده است. کوچک‌ترین عدد، با ۱۱ عدد در ۱۱ مرحله مقایسه شده است. کوچک‌ترین عدد از بین این ۱۱ عدد را با ۱۰ مقایسه پیدا می‌کنیم. در هر روش از مقایسه‌ها حداقل ۱۱ وزنه با کوچک‌ترین وزنه مقایسه می‌شوند.(چرا؟)

پس در مجموع با $1385+10=1395$ مقایسه به دو عدد کوچک‌تر می‌رسیم. این عدد در گزینه‌ها وجود ندارد ولی نزدیک‌ترین گزینه به آن (د) یعنی ۱۳۹۶ است.


ابزار صفحه