Wednesday, August 12, 2009

Nice coin problem

Tanya Khovanova has posted a very nice fake coin weighing problem on her math blog.

It goes beyond the usual coin problem by introducing the concept of a "revealing coefficient." The idea is to solve the coin weighing problem in a way that gives away as little information as possible about the identity of which particular coins are fakes.

I've found one solution, which I've posted as a comment to her blog. It gives a revealing coefficient of about 78%. I suspect it's possible to do better, because I didn't think for very long before I came up with my solution. If you want to see if you can get a solution with a lower revealing coefficient, go to her post on Unrevealing Weighings and try it for yourself.

Update: I now realize that I misread the original problem, so my originally posted "solution" does not actually solve the problem. I've now posted a new solution that I think works--but I hope someone will post a more clever one that improves the revealing coefficient that my simple approach yielded.

No comments: