ایده حل

هر بار توزین سه نتیجه (سنگین تر بودن کفه اول، کفه دوم یا مساوی) دارد. پس نتیجه سه بار توزین $3^3=27$ حالت ممکن خواهد بود. از طرفی ۱۲ سکه داریم که هر یک از آنها میتواند در دو حالت (سبک تر یا سنگین تر) تقلبی باشد، پس ۲۴ نتیجه محتمل را باید گزارش کنیم. چون ۲۷>۲۴ مشکلی از این بابت نیست. اما در طول فرایند هم باید این موضوع را چک کنیم. مثلا اگر در اولین توزین تنها دو سکه را مقایسه کنیم و برابر باشند، در ادامه سکه تقلبی میتواند از بین ۱۰ سکه باقیمانده، و سبک تر یا سنگین تر باشد (۲۰ حالت) ولی دو توزین باقیمانده تنها $3^2=9$ حالت تولید میکند، یعنی بعضی از حالتها توسط دوبار توزین قابل تعیین نیست. لذا شروع کار با مقایسه دو سکه نادرست است.

راه حل

سکه ها را به سه دسته ۴ تایی به نام A، B و C تقسیم میکنیم. قدم اول: A را با B مقایسه کن.

• اگر دو کفه مساوی بودند سکه تقلبی در C است. در قدم دوم سکه های ۱ تا ۳ از C را با سکه های ۱ تا ۳ از A مقایسه میکنیم.

  • اگر مساوی بودند سکه ۴ از C تقلبی است و با مقایسه آن با یک سکه از A می فهمیم سبک تر یا سنگین تر است.
  • اگر کفه سکه های C سنگین تر بود سکه تقلبی بین یکی از این سه سکه و سنگین تر از اصل است. کافی است دوتا از آنها را مقایسه کنیم، اگر یکی سنگین تر بود تقلبی است و اگر مساوی بودند سکه سوم تقلبی است، اگر کفه سکه های C سبک تر بود هم مشابه همین حالت است.

• اگر کفه A سنگین تر بود (مشابه همین استدلال را میتوان برای وقتی کفه A سبک تر باشد در نظر گرفت) در آن صورت یا یکی از سکه های A تقلبی و سنگین تر از اصل است، و یا یکی از سکه های B تقلبی و سبک تر از اصل است، و در هر حال سکه های C اصل هستند. در قدم دوم سکه های ۱ تا ۲ از A را به همراه سکه های ۱ تا ۲ از B در کفه اول ترازو، و سه سکه از C را به همراه سکه ۳ از B در کفه دوم ترازو میگذاریم.

  • اگر دو کفه مساوی بودند همه سکه های مقایسه شده اصل هستند، پس سکه تقلبی یکی از سکه های ۳ یا ۴ از A یا سکه 4 از B است. کافی است سکه ۳ و ۴ از A را مقایسه کنیم، اگر یکی سنگین تر بود تقلبی است و اگر مساوی بودند سکه ۴ از B تقلبی و سبک تر از اصل است.
  • اگر کفه اول سبک تر بود تنها سکه های ۱ و ۲ از B میتوانند تقلبی باشند، چرا که میدانیم سکه های A نمیتوانند سبک تر از اصل باشند و سکه ۳ از B که در کفه دوم است نمیتواند سنگین تر از اصل باشد. کافی است این دو سکه را مقایسه کنیم و سکه سبک تر را به عنوان تقلبی اعلام کنیم.
  • اگر کفه اول سنگین تر بود یکی از دو سکه ۱ و ۲ از A تقلبی و سنگین تر از اصل، و یا سکه ۳ از B تقلبی و سبک تر از اصل می باشد. برای یافتن تقلبی کافی است دو سکه ۱ و ۲ از A را مقایسه کنیم، اگر یکی سنگین تر بود تقلبی است و اگر مساوی بودند سکه ۳ از ‌B را تقلبی اعلام میکنیم.