All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Many coins - one fake (Posted on 2003-05-14)
Given a balance scale that is sure to break after X weighings, find an equation for the largest number of coins N, from which you can determine a fake coin that has the wrong weight if

A: You know whether the fake is lighter or heavier

B: You do not know whether the fake is lighter or heavier

(Assume only one of the N coins is fake)

 See The Solution Submitted by Jonathan Waltz Rating: 3.7143 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution for A; thoughts on B | Comment 1 of 20
Every weighing gives one of three results: the pans are balanced, the right pan is heavier, the left pan is heavier. As such it provides the equivalent of a base-3 digit, and so multiplies the number of possibilities covered by 3. So the solution to part A is N = 3^X.

The specific procedure for part A is to take one third of the set of coins and place it on the first pan, and another third on the second pan. If one side goes down, you know in which of these two pans the bad coin is located. If neither side goes down, the third that wasn't weighed has the bad coin. Continue as before with the set reduced to 1/3 its size.

Part B presumably needs only one more bit of information and one additional weighing supplies even more than that (a base-3 digit rather than a base-2 digit). Based on information theory you could have N = [(X^3)/2], where the square brackets indicate the floor function, or truncated quotient. As to a specific general strategy for any X, I can't think of any.
 Posted by Charlie on 2003-05-14 09:17:00
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information