Results 1 to 8 of 8

Math Help - A puzzle and orthogonal arrays

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    145

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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 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..
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2007
    Posts
    145
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2007
    Posts
    145
    Quote Originally Posted by Moo View Post
    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 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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2007
    Posts
    145
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Oct 2007
    Posts
    145
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Comparing two arrays of data
    Posted in the Statistics Forum
    Replies: 0
    Last Post: March 7th 2012, 02:05 AM
  2. Using imagesc to visualize arrays in Octave
    Posted in the Math Software Forum
    Replies: 0
    Last Post: September 13th 2011, 09:54 PM
  3. Big Fractions and Big Arrays
    Posted in the LaTeX Help Forum
    Replies: 3
    Last Post: May 12th 2011, 02:13 AM
  4. Arrays, indices problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 19th 2009, 08:05 AM
  5. Mapping arrays to use negative indexes
    Posted in the Math Software Forum
    Replies: 5
    Last Post: June 14th 2009, 11:05 AM

Search Tags


/mathhelpforum @mathhelpforum