بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 19: ترازو و وزن کردن Weighing with a Balance

یک ترازوی دوکفه‌ای سه جواب دارد، پس هر بار وزن کردن مشکوک‌ها را تا یک‌سوم کم می‌کند. ۲۷ سکه با ۳ بار، سکه‌ی سبک‌تر، کمترین تعدادِ وزن کردن، و یک ترازوی عددی با یک بار وزن کردن.

در این جلسه یاد می‌گیری

درس

۲۷ سکه، یکی سنگین‌تر، ۳ بار وزن کردن. ترازو زرنگ است و تا جایی که بتواند مشکوک‌ها را زیاد نگه می‌دارد. نقشه‌ات را امتحان کن!

چرا سه دسته؟ ترازو سه جواب دارد: چپ سنگین‌تر، راست سنگین‌تر، صاف. اگر مشکوک‌ها را به سه دسته‌ی تقریباً مساوی کنی (دو دسته روی کفه‌ها، یکی بیرون)، هر جوابی بیاید فقط یک دسته مشکوک می‌ماند: ⁦۲۷ ← ۹ ← ۳ ← ۱⁩.
کمتر نمی‌شود: با k بار وزن کردن فقط ۳ به توان k الگوی جواب داریم؛ اگر سکه‌ها بیشتر باشند، دو سکه الگوی یکسان پیدا می‌کنند و از هم جدا نمی‌شوند. پس ۲۸ سکه با ۳ بار نمی‌شود.

اگر سکه‌ی تقلبی سبک‌تر باشد، همه چیز همان است، فقط این بار کفه‌ای که «بالا» می‌رود مشکوک است. با ۸ سکه و ۲ بار امتحان کن ⁦(۸ ≤ ۹)⁩:

ترازوی عددی (که وزن را با عدد نشان می‌دهد) فرق دارد. معمای معروف: ۹ کیسه سکه داریم؛ سکه‌های یکی از کیسه‌ها همه تقلبی‌اند و هر کدام ۱۱ گرم است، به‌جای ۱۰ گرم. با یک بار وزن کردن: از کیسه‌ی ۱ یک سکه، از کیسه‌ی ۲ دو سکه، … از کیسه‌ی ۹ نُه سکه بردار. اگر همه درست بودند ۴۵۰ گرم می‌شد؛ هر گرمِ اضافه یعنی یک سکه‌ی تقلبی. اگر ترازو ۴۵۶ نشان دهد، کیسه‌ی ۶ تقلبی است! به این «برچسب زدن با تعداد» می‌گویند.

چالش‌ها

  1. Eighty-One Coins (آسان)
  2. Ten Coins (آسان)
  3. Twenty-Seven Coins (متوسط)
  4. The Lighter Coin (متوسط)
  5. Five Weighings (سخت)
  6. Nine Bags, One Weighing (سخت)

← جلسه‌ی 18: فرایندها و الگوریتم‌ها جلسه‌ی 20: مرتب‌سازی و مقایسه →