جلسهی 19: ترازو و وزن کردن Weighing with a Balance
یک ترازوی دوکفهای سه جواب دارد، پس هر بار وزن کردن مشکوکها را تا یکسوم کم میکند. ۲۷ سکه با ۳ بار، سکهی سبکتر، کمترین تعدادِ وزن کردن، و یک ترازوی عددی با یک بار وزن کردن.
در این جلسه یاد میگیری
- با تقسیمِ سکهها به سه دسته، سکهی تقلبی را با کمترین وزن کردن پیدا میکنی.
- میدانی با k بار وزن کردن حداکثر ۳ به توان k سکه را میشود بررسی کرد، و چرا بیشتر نه.
- ایدهی «برچسب زدن با تعداد» را برای ترازوی عددی به کار میبری.
درس
۲۷ سکه، یکی سنگینتر، ۳ بار وزن کردن. ترازو زرنگ است و تا جایی که بتواند مشکوکها را زیاد نگه میدارد. نقشهات را امتحان کن!
چرا سه دسته؟ ترازو سه جواب دارد: چپ سنگینتر، راست سنگینتر، صاف. اگر مشکوکها را به سه دستهی تقریباً مساوی کنی (دو دسته روی کفهها، یکی بیرون)، هر جوابی بیاید فقط یک دسته مشکوک میماند: ۲۷ ← ۹ ← ۳ ← ۱.
کمتر نمیشود: با k بار وزن کردن فقط ۳ به توان k الگوی جواب داریم؛ اگر سکهها بیشتر باشند، دو سکه الگوی یکسان پیدا میکنند و از هم جدا نمیشوند. پس ۲۸ سکه با ۳ بار نمیشود.
اگر سکهی تقلبی سبکتر باشد، همه چیز همان است، فقط این بار کفهای که «بالا» میرود مشکوک است. با ۸ سکه و ۲ بار امتحان کن (۸ ≤ ۹):
ترازوی عددی (که وزن را با عدد نشان میدهد) فرق دارد. معمای معروف: ۹ کیسه سکه داریم؛ سکههای یکی از کیسهها همه تقلبیاند و هر کدام ۱۱ گرم است، بهجای ۱۰ گرم. با یک بار وزن کردن: از کیسهی ۱ یک سکه، از کیسهی ۲ دو سکه، … از کیسهی ۹ نُه سکه بردار. اگر همه درست بودند ۴۵۰ گرم میشد؛ هر گرمِ اضافه یعنی یک سکهی تقلبی. اگر ترازو ۴۵۶ نشان دهد، کیسهی ۶ تقلبی است! به این «برچسب زدن با تعداد» میگویند.
چالشها
- Eighty-One Coins (آسان)
- Ten Coins (آسان)
- Twenty-Seven Coins (متوسط)
- The Lighter Coin (متوسط)
- Five Weighings (سخت)
- Nine Bags, One Weighing (سخت)
← جلسهی 18: فرایندها و الگوریتمها جلسهی 20: مرتبسازی و مقایسه →