Introduction#
While I was intensely surfing the internet, I stumbled upon this problem. Finally, 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 there is exactly one bottle that contains poison. 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 poisoned bottle 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 of the previous mouse.
Difficulty#
The most challenging aspect of this problem is that we can only know the result after completing all steps, and we cannot determine subsequent actions based on the survival 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 poisoned bottle even after all seven mice have died.
At this point, our conventional high school mathematical methods can no longer 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 we carry over at 10. 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, we carry over at 2, 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 the # is the decimal number, and the number before the # is the binary number, aligned in three digits. If the number to the left of 1 is 0, it has no practical significance.
Having understood binary, let's revisit the problem. With 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 result 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. Since we have 7 mice, 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 should 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 poisoned. If they do not die or not all die, then it is not poisoned, as these mice may need to drink other potions, and we cannot determine.
Explanation complete, 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 poisoned, we proceed with the simulation.
We can see that when all mice in a group die, we can determine that this group contains the poison, which is bottle number 85.
Changing Perspective#
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