معمای کیسه های سکه

آشنایی با معماهای مشهور و تلاش برای حل آن‌ها یکی از راهکارهای مفید برای تقویت مهارت حل مسأله به شمار می‌رود. اگر مایلید این مهارت کاربردی در برنامه نویسی و طراحی الگوریتم را در خود تقویت کنید یا به عنوان فردی عادی می‌خواهید با یک معمای فکری آشنا شوید و یا برای استخدام در یک شرکت به مصاحبه دعوت شده‌اید بد نیست با معمای کیسه های سکه آشنا شوید.

شرح معمای کیسه های سکه

فرض کنید 10 کیسه دارید و هر کیسه حاوی 1000 سکه است. صرفا یکی از کیسه ها با سکه های تقلبی پر شده است و مابقی سکه ها واقعی هستند. با این حال شما فراموش کرده‌اید کدام کیسه حاوی سکه های تقلبی است. اگر هرکدام از سکه های واقعی 1 گرم باشند و هرکدام از سکه های تقلبی 1.1 گرم باشند چگونه می‌توانید با یک بار وزن کردن (یا به عبارت بهتر سنجش جرم با ترازو)، کیسه حاوی سکه های تقلبی را شناسایی کنید؟

پاسخ معما

ابتدا کیسه ها را به ترتیب از 1 تا 10 شماره‌گذاری کنید. سپس از کیسه اول 1 سکه، از کیسه دوم 2 سکه، از کیسه سوم 3 سکه و به همین ترتیب از کیسه دهم 10 سکه بیرون بیاورید.

حالا تمام سکه هایی که از کیسه ها بیرون آورده‌اید را وزن کنید. اگر تمام سکه ها واقعی بودند جرم مجموع این سکه ها 1+2+3+…+10=55 گرم می‌شد.

حال که چنین نیست اگر جرم سکه ها 55.1 گرم باشد واضح است که تنها یکی از سکه ها تقلبی بوده است. از طرفی می‌دانیم فقط سکه های یکی از کیسه ها تقلبی است. همچنین تمام سکه های داخل هر کیسه یا واقعی هستند یا تقلبی. بنابراین سکه تقلبی متعلق به کیسه اول است و تمام سکه های این کیسه تقلبی هستند.

اگر برای مثال، جرم سکه ها 55.6 گرم باشد پس 6 گرم نسبت به حالت عادی اضافی است. به عبارت بهتر 6 سکه تقلبی در سکه های برداشته شده قرار دارد و کیسه ششم حاوی سکه های تقلبی است.

بر این اساس اگر جرم سکه ها 55.n گرم باشد (که n یکی از ارقام 1 تا 9 است) کیسه n ام حاوی سکه های تقلبی است. اگر هم جرم سکه ها 56 گرم باشد کیسه دهم حاوی سکه های تقلبی بوده است.