Preface#
While surfing the internet intensively, I stumbled upon this problem and, after guidance from an OI expert and help from CSDN, I came up with a solution.
Problem#
You have 100 bottles of mixed potions in front of you, and only one of them is poisonous. You have 7 mice; the mouse that drinks the poison will die, while the others will not. Please design a plan using these 7 mice to identify the poisonous potion based on the survival status of the mice.
Assume each mouse can drink an unlimited amount of potion, and each bottle of potion will not be emptied. During the implementation of the plan, you cannot know the current execution status, meaning you cannot decide subsequent actions based on the survival status of the previous mouse.
Difficulty#
The most challenging aspect of this problem is that we can only know the result after completing all steps; we cannot determine subsequent actions based on the survival status of the previous mouse.
During discussions with classmates, everyone leaned towards using the binary method, continuously approaching the solution without considering the difficulties mentioned above. Just focusing on the binary method, we might not find the poisonous potion even after all seven mice have died.
At this point, our conventional high school math methods are no longer sufficient to solve this problem. So what should we do?
Binary Method#
Binary is the language of computers; let’s briefly understand binary.
We usually use decimal, which is base 10, meaning every 10 counts as 1. When we write the eleventh number, it is 11, not something else. For example, in hexadecimal, the eleventh number is represented by 'a'. Similarly, in binary, every 2 counts as 1, so when we write the third number, binary uses 11 to represent it.
001 # 1
002 # 2
011 # 3
100 # 4
101 # 5
The number after # is the decimal number, and the number before # is the binary number, aligned in three-digit format. If the number to the left of 1 is 0, it has no practical significance.
Having understood binary, let’s revisit the problem: 7 mice and 100 bottles of potion. I wrote a binary conversion algorithm in Python to list 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 the binary conversion of 100 is 1100100, which is exactly a seven-digit number. This means that the binary representation of numbers less than 100 will never exceed seven digits, and each decimal number corresponds to exactly one binary number. We have 7 mice, and we can use this property to solve the problem.
From left to right, each of the seven digits corresponds to a mouse. When the corresponding digit is 1, that mouse must drink from that bottle. For example, if we drink from bottle 35, we first calculate the binary representation of 35 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 let mice 2, 6, and 7 drink from it. If all three mice die, then that bottle is poisonous; if they do not die or not all die, then it is not poisonous, as these mice may need to drink other potions, and we cannot determine.
Explanation finished, let’s start the practice.
Practical Simulation#
We use Excel for statistics, essentially creating a list. Using Python's binary algorithm, we obtain all binary numbers from 1 to 100 and import them into Excel. We number the seven mice and have them drink the corresponding potions.
Assuming potion number 84 is poisonous, we proceed with the simulation.
We can see that when all mice in a group die, we can determine that this group is poisonous, which is bottle number 85.
Thinking from a Different Angle#
While creating the table, I realized that if we do not use mathematical thinking, we can view it as biological inheritance. Only when all these genes are dominant can the phenotype be dominant. However, we must understand that the binary solution is a key point; without binary,
This article is synchronized and updated by Mix Space to xLog. The original link is https://fmcf.cc/posts/technology/Python-Rat-Poison-Solution