A puzzle and orthogonal arrays

• Apr 26th 2008, 03:59 AM
chopet
A puzzle and orthogonal arrays
I came across this puzzle which goes as follows:

There are 12 weights, 11 of which are gold and 1 is a dud (it could either be lighter or heavier). How can you determine which is the one with only 3 weighs?

Then I came across the concept of orthogonal arrays, which is used in designing fractional factorial experiments, and I wonder if the puzzle above can be explained with orthogonal arrays?
• Apr 26th 2008, 04:42 AM
Moo
Hello,

Quote:

and I wonder if the puzzle above can be explained with orthogonal arrays
Yes :D

Why ?
I don't know and I don't even know the exact definition of an orthogonal array :D

The thing :
«If we know that a coin is lighter (it may go the same way if it's heavier) than the N other coins, and if $3^{n-1} \leq N < 3n$, the dud can be found in a maximum of $n$ weighs.»

The thing to do is to divide the set of coins into 3 subsets, 2 will have the same number of coins, which we are going to put in the balance, and the third one (which has less or as many coins as the other sets) aside.

A weigh lets us know in which of the subsets there is the dud.

And so on..
• Apr 26th 2008, 04:43 AM
chopet
maybe i should elaborate this further.

For the 12 stones, the most straightforward algorithm is to weigh them 11 times.
1 v 2
1 v 3
1 v 4
1 v 5
...

until we come to an answer.
or we can do:
1 v 2, 3 v 4, 5 v 6, 7 v 8, 9 v 10, 11 v 12 for 6 times.
say, 5 is heavier than 6. But we still do not know if the dud is a heavier 5 or a lighter 6. We need an extra weigh for a total of 6+1 = 7 times.

The best algorithm out there can do it in 3 times.
• Apr 26th 2008, 04:48 AM
chopet
Quote:

Originally Posted by Moo
Hello,

Yes :D

Why ?
I don't know and I don't even know the exact definition of an orthogonal array :D

The thing :
«If we know that a coin is lighter (it may go the same way if it's heavier) than the N other coins, and if $3^{n-1} \leq N < 3n$, the dud can be found in a maximum of $n$ weighs.»

The thing to do is to divide the set of coins into 3 subsets, 2 will have the same number of coins, which we are going to put in the balance, and the third one (which has less or as many coins as the other sets) aside.

A weigh lets us know in which of the subsets there is the dud.

And so on..

Hi, how do I use the formula you quoted?
There are 12 coins. is N=11?

And how do you come up with the number 3 subsets?
• Apr 26th 2008, 04:51 AM
Moo
I can see it in 3 ways :

Compare 1-3-4-5 with 2-6-7-8 : weigh 1.

Compare 1-6-7-8 with 2-9-10-11 : weigh 2.

Compare 2-3-8-11 with 5-6-9-12 : weigh 3.

Then with the results, you'll know if the dud coin is in which set, each time you do a weigh :)

For N, yep, it's 11.
I don't really know why, it's something I've read, I copied it here :)

Concerning the historical thing : Emil Schell posted the problem (with 8 coins and one lighter than the others) to the American Mathematical Monthly in 1945. After that, generalizations have come their way.
• Apr 26th 2008, 09:03 AM
Opalg
• Apr 26th 2008, 11:59 AM
chopet
Thank you. That is very interesting.
So does the solution has anything to do with orthogonal arrays and Latin squares?
Orthogonal array - Wikipedia, the free encyclopedia
• Apr 26th 2008, 11:42 PM
chopet
Ok. To put things simply, this matrix is extracted from the solution.

0 0 0 0 1 1 1 1 2 2 2 2
0 1 2 2 0 0 0 1 2 2 1 1
1 0 2 1 0 1 0 2 0 1 0 2

Is the above matrix an orthogonal array? Why or why not?
Thanks.