Math Is Fun Forum

mikau

Member

Registered: 2005-08-22

Posts: 1,504

two see-saw problems

here's a problem my first programming teacher gave in class which is similar to the apple problem on this website. I'm not sure what the answer is, but maybe you guys will know.

The first problem, say you have 8 coins. 1 of them is heavier than the rest. And you have a balance beam to use as a scale. Whats the smallest amount of times you can use the scale to find the heaviest coin?

I raised my hand and proposed we simply divide the coins in half, and weigh each half to narrow down our search exponetially. He replied 'and is that THE fastest way to do it?'
another guy said "yeah!" and he yelled "would you bet your house?" lol. and none of us were willing.
I think we all suspected their WAS a better way based on his attitude but i'm sure he could have just been trying to trick us.

So is my solution the fastest way? Or is their some sacred technique that can actually beat this method?

The other question is, what if the one coin is either lighter, or heavier but we don't know which? Whats the fastest way to find it?

Last edited by mikau (2007-05-12 16:56:58)

---

A logarithm is just a misspelled algorithm.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: two see-saw problems

This is all assuming the problem is not a trick question.  It depends.  What do you mean by fastest?  In the worst case?  Best case?  Average case?

If it's the average case, this algorithm is faster:

Measure 2 v 2 coins.  If they are equal, then you know the heavier coin is not in there.  If such is the case, measure the other 2v2 coins.  Once you've got it narrowed down to 2 coins, just measure them against each other.

It can be that you only have to make 2 measurements.  But in the worst case, you'll still have to make 3.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: two see-saw problems

On the other hand... what do you consider a measurement?  If you place one coin on each side at a time, are these each individual measurements?  If not, then simple place a coin on the left, coin on the right, left, right... and once there are an equal amount of coins but unequal weight, one of the last two you added is the heavier coin.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: two see-saw problems

okay, best case, not average case. But I suppose, an algorithm thats at least as good if not better than another would be considered a better algorithm even in the non average case. So yes! Thats a better way of doing it, right? :-)

I suppose you would consider checking an existing quantity on a scale to be taking a measurement, and whenever you change the quantity, or objects on the scale, you are taking another measurement.

Last edited by mikau (2007-05-12 18:33:03)

---

A logarithm is just a misspelled algorithm.

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,713

Re: two see-saw problems

As a general principal (ignoring "8" or "10" coins) how about splitting into 3 groups?

Put 2 either side of the balance. The result will be Left Heavy, Right Heavy or Equal. If Equal it is the "unmeasured" group.

Split that group again as necessary.

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman