Group Testing Problems (One known, One less known?)
I recently gave a talk at Yale (Thanks to Dan Spielman for hosting; harmless exposé: Ravi Kannan is a coffee afficionado.) on Compressed Sensing. In the proof outline, I described using two different parallel group testing procedures via k-selectors, one for filtering and the other for verification. I realized I do a bad job of talking about group testing problems in general: I find it easy to go to a coin-weighing puzzle and connect with the audience; but one has to map the current problem to group testing which typically involves technical details, and then I drop the ball transitioning from there to pointing out the novel group testing variant I need for my talk. IOW, I make all group testing problems look alike! While I work on that, here are two coin-weighing puzzles, one classic and the other sorta not well known?
PARTY FAVORITE: Given 12 identical coins one of which is defective--may be heavy/light wrt to the good coins---use at most 3 pan balance weighings (ie only comparison of weights of sets of coins) to find the defective coin. Show that with 14 coins, one needs more than 3 weighings. Show that with 13 coins, one needs more than 3 weighings, but 3 weighings will suffice if one has an *extra* good coin.
All these claims can be generalized to roughly (3^w)/2 coins and w weighings.
LESS KNOWN: We have three coins (a,b,c) with respective partners (a',b',c'). Each coin is Heavy or Light; if a coin is Heavy, its partner is Light and vice versa. All Heavy coins weigh the same and likewise all Light coins. Using at most 2 pan-balance weighings find the state of each of the coin.
Extra credit: Impossible to solve in 2 weighings if none of the coins are provided with a partner; an adaptive procedure will work if any one coin has a partner; a non-adapative procedure will work if any two coins have partners; the puzzle has redundant information because all three coins have partners.
RESEARCH: Generalize the puzzle above to n coins, w weighings and gets precise bounds.
PARTY FAVORITE: Given 12 identical coins one of which is defective--may be heavy/light wrt to the good coins---use at most 3 pan balance weighings (ie only comparison of weights of sets of coins) to find the defective coin. Show that with 14 coins, one needs more than 3 weighings. Show that with 13 coins, one needs more than 3 weighings, but 3 weighings will suffice if one has an *extra* good coin.
All these claims can be generalized to roughly (3^w)/2 coins and w weighings.
LESS KNOWN: We have three coins (a,b,c) with respective partners (a',b',c'). Each coin is Heavy or Light; if a coin is Heavy, its partner is Light and vice versa. All Heavy coins weigh the same and likewise all Light coins. Using at most 2 pan-balance weighings find the state of each of the coin.
Extra credit: Impossible to solve in 2 weighings if none of the coins are provided with a partner; an adaptive procedure will work if any one coin has a partner; a non-adapative procedure will work if any two coins have partners; the puzzle has redundant information because all three coins have partners.
RESEARCH: Generalize the puzzle above to n coins, w weighings and gets precise bounds.
posted by metoo at 2:54 AM
2 Comments:
Hello,
Without much luck, I was searching for blogs about Toys & Hobbies when I happened across yours. It's a cool blog. Evidently you like telling it like it is! I have a really great ebay website that is easy to use that you may like. If you get a chance, check it out www.licensedbrandsclub.com.
If you have fallen prey to obesity and would like to trigger off weight loss as soon as possible, then you should opt for diet pills such as Phentermine and Adipex that are extremely popular for inducing rapid weight loss among people across the world. You will find the relevant details of weight loss pills at http://www.weight-loss-truths.com that inform you that Phentermine is to be taken only after procuring a Phentermine prescription and also in accordance with the instructions of the doctor. So, get hold of a Phentermine prescription, administer the drug properly and transform your weight loss dreams into reality.
Post a Comment
<< Home