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
0 Comments:
Post a Comment
<< Home