Preface

While surfing the internet at full intensity, I stumbled upon this problem. After receiving guidance from an OI expert and help from CSDN, I finally came up with a solution.

The Problem

You have 100 bottles of potion, all mixed up, and exactly one of them is poison. You have 7 rats. A rat that drinks the poison will die; otherwise, it won't. Your task is to design a scheme using these 7 rats to identify the poison based on which rats die.

Assume each rat can drink an unlimited amount of potion, and no bottle will be emptied. During the process, you cannot know the current status—that is, you cannot decide what to do next based on whether a previous rat died or not.

The Difficulty

The hardest part of this problem is that we can only know the result after all steps are completed. We cannot adjust our actions based on the survival of earlier rats.

When discussing with classmates, everyone leaned toward using binary search, narrowing down step by step. But even ignoring the difficulty above, with binary search alone, we'd likely run out of all 7 rats before finding the poisoned bottle.

At this point, the standard math methods we learn in high school are no longer enough. So what do we do?

The Binary Method

Binary is the language of computers. Let's take a rough look at binary.

We normally use decimal, which means we carry over to the next digit when we reach 10. When we write the eleventh number, it's 11, not something else—just as the eleventh number in hexadecimal is represented by a. Binary works the same way: it carries over at 2, so when we write the third number, binary uses 11.

001 # 1
002 # 2
011 # 3
100 # 4
101 # 5

After # is the decimal number, before # is the binary number, aligned to three digits. A leading 0 on the left has no actual meaning.

Now that we understand binary, let's re-examine the problem. With 7 rats and 100 bottles, I wrote a binary conversion algorithm in Python and listed the binary representations of all numbers from 1 to 100.

x=0
for i in range(0,100):
    x=x+1
    y = x
    b=""
    while(y>=1):
        b=str(num%2)+b
        num=num//2
    print(b)

We find that 100 in binary is 1100100, which happens to be exactly seven digits. This means that every number up to 100 has a binary representation with no more than seven digits, and each decimal number corresponds to exactly one binary number. Since we have exactly 7 rats, we can use this property to solve the problem.

Read the seven digits from left to right, each corresponding to one rat. When the digit is 1, that rat drinks this bottle. For example, to test bottle 35, we first convert 35 to binary and align it to seven digits. The binary for bottle 35 is 0100011. From left to right, the 2nd, 6th, and 7th digits are 1, so we have rats 2, 6, and 7 drink it. If all three rats die, then this bottle is the poison. If none die, or only some die, then it's not the poison, because those rats might also drink other bottles, so we can't be sure.

That's the explanation—now let's put it into practice.

Practical Simulation

We'll use Excel for the tally, essentially a table. Using the Python binary algorithm, we get the binary representations of 1–100 and import them into Excel. We number the seven rats and have them drink the corresponding bottles.

Let's assume bottle 84 is poisoned, and run the simulation.

We can see that only when all rats in a group die can we identify that group as the poison—that is, bottle 85.

Thinking Differently

When I was writing the table, I realized that if we don't use mathematical thinking, we can view it as biological inheritance: only when several genes are all dominant can the phenotype be dominant. But we must understand that the binary solution is a key point. Without binary,