المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۰

۱۳۸۲ وزنه‌ی یک شکل و با وزن‌های متمایز داریم که وزن هرکدام توانی از ۲ است. یک ترازوی دو کفه‌ای در اختیار داریم. در هر بار «توزین» می‌توانیم تعدادی از وزنه‌ها را در یک کفه و بقیه‌ی وزنه‌ها را در کفه‌ی دیگر قرار دهیم (همه‌ی وزنه‌ها باید در دو کفه‌ی ترازو قرار گیرند) و مجموع وزن وزنه‌های موجود در دو کفه را با هم مقایسه کرد. با حداقل چند بار توزین می‌توان سنگین‌ترین وزنه را پیدا کرد؟

  1. ۱۱
  2. ۲۲
  3. ۶۹۱
  4. ۱۳۸۱
  5. این کار ممکن نیست.

پاسخ

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

باتوجه به ‌این که $2^1 +2^2+...+2^{i-1}=2^i-2$، بنابراین وزن سنگین‌ترین وزنه از مجموع اوزان بقیه وزنه‌هایش بیش‌تر است٬ بنابراین سنگین‌ترین وزنه در هر مرحله در کفه‌ای قرار دارد که سنگین‌تر است. بنابراین در مرحله اول ۶۹۱ وزنه را در یک کفه و ۶۹۱ وزنه دیگر را رد کفه دیگر قرار می‌دهیم بر روی وزینه‌های کفه‌ای که سنگین‌تر باشد را یک علامت می‌زنیم٬ وزنه مورد نظر در وزنه‌های علامت‌دار قرار دارد. ۳۴۵ وزنه علامت‌دار را در همان کفه نگه داشته و مابقی(۳۴۶ تا) را در کفه دیگر و در کنار ۶۹۱ وزنه قبلی قرار می‌دهیم. کفه‌ای که سنگین‌تر باشد وزنه مورد نظر را شامل است. بر روی وزنه‌های آن کفه علامت جدیدی می‌گذاریم. یقینا وزنه مورد نظر در بین وزنه‌هایی که شامل دو علامت هستند قرار دارد که تعداد این وزنه‌ها حداکثر برابر۳۴۶ می‌باشد. اگر این روند را تا انتها ادامه دهیم به این ترتیب که در هر مرحله در یک کفه فقط نصف وزنه‌ها با ماکزیمم علامت را قرار داده و مابقی وزنه‌ها را در کفه دیگر قرار دهیم بعد از ۱۱ مرحله وزنه مورد نظر به‌دست می‌آید با این توضیح که در هر مرحله حداکثر تعداد وزنه‌های با ماکزیمم علامت به شکل زیر می‌باشد.

$$691 \rightarrow 346 \rightarrow 173 \rightarrow 87 \rightarrow 44 \rightarrow 22 \rightarrow 11 \rightarrow 6 \rightarrow 3 \rightarrow 2 \rightarrow1$$


ابزار صفحه