Thread: 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?

Hello,

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

Yes

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

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 , the dud can be found in a maximum of 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..

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.

Originally Posted by Moo

Hello,



Yes

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

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 , the dud can be found in a maximum of 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?

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.

There's a very clear solution to the weighing problem at Weighing 12 coins from Interactive Mathematics Miscellany and Puzzles, and a more advanced discussion at Definitive solution to the counterfeit coin problem - Wikipedia, the free encyclopedia.

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

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.