2

Problem

$N$ coins, $N-1$ equal coins and one heavier counterfiet coin. With a balance beam given we want to find the counterfeit coin. We have two different goals:

  • minimise the expected number of weighings
  • minimise the maximal number of required weighings

I have no idea on how to develop a search algorithm for each of the two goals, I hope someone can help me finding it!

Nedellyzer
  • 1,174

1 Answers1

1

The full solution to this problem can be found in the book linked: http://www.scribd.com/doc/7360109/The-USSR-Olympiad-Problem-Book

It is Question 4 b) in the Introductory Problems (Page 7). The solution can be found in pages 84-86 of the book.

tcmtan
  • 1,883