المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۸

امروز تولد آیدا، یکی از ساکنین کشور سه‌سوسا است. در این کشور عدد سه بسیار باارزش تلقی می‌شود. طبق یک رسم دوستانه قدیمی، دوستانش قرار است برای او بسته‌های حاوی کلوچه کادو بیاورند. میدانیم شکل ظاهری کلوچه‌های موجود در یک بسته کاملا شبیه هم است اما وزن آن‌ها ممکن است با هم متفاوت باشد. هم‌چنین وزن کلوچه‌ها یک عدد طبیعی است.

یک آیین قدیمی می‌گوید که اگر فرد $A$ به‌عنوان کادوی تولد برای فرد $B$ یک بسته حاوی $K$ عدد کلوچه بیاورد و مجموع وزن این $K$ کلوچه مضربی از ۳ گرم باشد، آن‌گاه $A$ یک ( دوست واقعی) $B$ است! برای تشخیص دوستان واقعی، آیدا به بازار می‌رود تا ترازو بخرد. او متوجه می‌شود که ترازوهای موجود در بازار همگی یک کفه‌ای هستند و به‌جای عقربه یا صفحه دیجیتال، تنها فقط یک چراغ دارند که در صورتی که مجموع وزن اشیاء روی کفه ترازو مضربی از ۳ گرم باشد چراغ روشن می‌شود! علاوه بر این، ترازوهای موجود دارای محدودیت جالبی در حجم کفه هستند. به این معنی که در بازار ترازوهای مدل $W_۱$، مدل $W_۲$، مدل $W_۳$ و مدل $W_۴$ وجود دارند که ترازوی مدل $W_i$ تنها درصورتی کار می‌کند که روی آن دقیقا $i$ تا کلوچه ( و نه کمتر یا بیشتر ) قرار بگیرد.

متاسفانه آیدا نمی‌داند که هر یک از دوستانش ممکن‌ست چندتا کلوچه برایش بیاورند و برای همین باید با خرید یک یا چند ترازو و چندین بار استفاده ار آن‌ها، بتواند مضرب ۳ بودن مجموع هر بسته کلوچه را تشخیص دهد. یک مجموعه از ترازوها را کامل می‌گوییم اگر بتوانیم با کمک ترازوهای موجود در آن مجموعه، برای هر بسته کلوچه حاوی بیش از ۳ کلوچه، با کمک آن ترازوها و استفاده از قدرت تحلیل و استدلال تشخیص بدهیم که مجموع وزن این بسته کلوچه بر ۳ بخش‌پذیر است یا نه؟ از بین مجموعه‌های {$W_۱,W_۲$}٬ {$W_۱,W_۳$}٬ {$W_۲,W_۳$} و {$W_۱,W_۴$} چندتایشان کامل هستند؟

  1. ۰
  2. ۱
  3. ۲
  4. ۳
  5. ۴

ابزار صفحه