# Practice Paper 4 Question 19

There are \(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?

## Related topics

## Warm-up Questions

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

## Hints

- Hint 1How many chemicals can you distinguish in a single day with \(p=1\) flask?
- Hint 2How could you distinguish 2 chemicals with only one flask? And why would it be possible?
- Hint 3What's the maximum number of chemicals you can distinguish in a single day using \(p\) flasks?
- Hint 4Remember rule
*(ii)*: you can add the same chemical to multiple flasks. - Hint 5For \(p=3,\) we can distinguish up to \(8\) chemicals.
- Hint 6How would you extend this approach to \(d\) days?
- Hint 7In other words, if we can distinguish \(k\) chemicals in one day with \(p\) flask, how many chemicals can we distinguish in \(d\) days?
- Hint 8We can do much better than \(kd\) chemicals.
- Hint 9For up to \(n=16\) and \(p=2,\) it can be done in two days.
- Hint 10Try writing out the integers from \(0\) to \(15\) as 4-digit binary numbers.

## Solution

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.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.[email protected]. Please do not write to this address regarding general admissions or course queries.