$n$ chemicals. One is magic, turning lead into gold in one day. You may (i) mix multiple chemicals with lead in one flask; (ii) add one chemical to multiple flasks. You have $p$ flasks, and an unlimited supply of lead and of each of the $n$ chemicals. What is the smallest number of days you need to guarantee you find the magic chemical?
-
- Bob choosse a letter randomly from the English alphabet. You may question a range (e.g. from ‘a’ to ‘o’ inclusively) and he will tell you whether the letter is within the range. You want to guess as few questions as possible. How many guesses do you need in the worst case?
-
How many chemicals can you distinguish in a single day with
$p=1$flask? -
How could you distinguish 2 chemicals with only one flask? And why would it be possible?
-
What’s the maximum number of chemicals you can distinguish in a single day using
$p$flasks? -
Remember rule (ii): you can add the same chemical to multiple flasks.
-
For
$p=3,$we can distinguish up to$8$chemicals. -
How would you extend this approach to
$d$days? -
In other words, if we can distinguish
$k$chemicals in one day with$p$flask, how many chemicals can we distinguish in$d$days? -
We can do much better than
$kd$chemicals. -
For up to
$n=16$and$p=2,$it can be done in two days. -
Try writing out the integers from
$0$to$15$as 4-digit binary numbers.
-
We could start by asking: “What’s the maximum number of chemicals I can distinguish in a single day using
$p$flasks?". That number then grows exponentially with the number of days. Hence the number of flasks$p$necessary to distinguish$n$chemicals grows logarithmically.You should also realise that you can leave one chemical aside, which would be the gold’ing chemical if none of the other flasks turn to gold. Then, you should ask how many combinations there are, such that each flask can reveal a single gold’ing chemical. This leads to binary counting and exponentiation.
For example, for
$p=3$we can find the gold’ing chemical in a single day from$n=8$chemicals:Day 1 Flask 1 Flask 2 Flask 3 0 1 x 2 x 3 x x 4 x 5 x x 6 x x 7 x x x The
$0^{th}$chemical is left unused. If only flask 2 turns to gold, then it’s the$1^{st}$chemical. If only flasks 2 and 3 turn to gold, then it’s the$3^{rd}$chemical and so on. If none turn to gold, then it’s the$0^{th}$chemical.If we can afford
$d$days, then we can do powers of$2^p$each day, and therefore can distinguish$n=2^{pd}$chemicals. We can get the answer for the reverse question (how many days) by rearranging to get$d=\lceil \log_{2^p} n\rceil$.For
$n=16$and$p=2,$we can find the gold’ing chemical as follows:Day 2 Flask 1 Flask 2 Day 1 Flask 1 Flask 2 0 0 1 1 x 2 2 x 3 3 x x 4 x 4 5 x 5 x … 15 x x 15 x x For example, if on both days, flask 2 turns to gold, then the
$5^{th}$chemical is the gold’ing chemical and so on. If none turn to gold, then it’s the$0^{th}$chemical.