مساله ۱۵. یافتن سکه تقلبی ۲

ده دستگاه سکه‌ساز‌ داریم که هر کدام سکه های ۱۰ گرمی تولید میکنند. یکی از دستگاه‌ها خراب شده و به جای‌سکه ۱۰ گرمی سکه ۹ گرمی تولید میکند. ما یک ترازوی دیجیتال داریم و میخواهیم با فقط یک بار استفاده‌از آن دستگاه خراب‌ را پیدا کنیم. حداقل چند سکه برای این کار باید تولید کنیم؟

اگر بتوانیم دو بار از ترازو استفاده کنیم چطور؟

توضیح. تو یه بار استفاده از ترازو می‌تونیم هر ترکیبی از سکه‌های دستگاه‌های مختلف رو وزن کنیم و هر چندتا سکه هم از دستگاه بخواهیم می‌تونیم بگیریم. به عنوان مثال می‌تونیم ۱۰ سکه از دستگاه اول، ۱۲ سکه از دستگاه دوم، ۱۰۰۰ سکه از دستگاه سوم، ... رو یه جا روی ترازو بذاریم و وزن کل این ترکیب رو حساب کنیم.

لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1679741266786144257

پاسخ بخش اول ۴۵ و پاسخ بخش دوم ۱۳ است.

بخش اول. اگر فقط یک وزن‌کشی مجاز باشه، تعداد هر سکه باید متفاوت از بقیه سکه‌ها باشه، و کمترین حالت برای ۱۰ تعداد غیرمساوی ۰+۱+۲+...+۹ است که جمعا برابر با ۴۵ میشه.

بخش دوم. اگر دو وزن کشی مجاز باشه، کمترین تعداد سکه لازم ۱۳ ه. ۲ استراتژی برای وزن‌کشی اول وجود داره که در مجموع تعداد سکه‌هاشون حداکثر ۱۳ بشه:

  • استراتژی ۱. صفر تا از ۳ ماشین، یکی از ۴ ماشین، و دوتا از ۳ ماشین
  • استراتژی ۲. صفر تا از ۴ ماشین، یکی از ۵ ماشین، و دوتا از ۱ ماشین

مثلا در استراتژی اول اگه در وزن‌کشی اول بفهمیم سکه خراب از دسته یک تایی‌هاست، در وزنکشی دوم ۴ تا کاندیدا باقی مونده، که از هر کدوم به ترتیب ۰+۱+۲+۳ سکه میزاریم که چون از هر نوع یکی در مرحله اول برداشته بودیم، فقط ۰+۰+۱+۲ تاش جدیده و کل دو مرحله میشه ۱۳ سکه (۱۰ سکه مرحله اول، ۳ سکه جدید مرحله دوم). بقیه حالت‌ها هم به همین ترتیب.

لینک راه‌حل در توویتر: https://twitter.com/Riazi_Cafe/status/1681197786795220997