This is more complicated for me, please refer to:
-
Purpose and thinking
This paper studies the typical problem of "thinking nesting"-guessing numbers, analyzes the essence of the problem, avoids the apparent "thinking nesting" and greatly improves the efficiency of solving problems.
manufacturing process
First of all, I became interested in the prototype of the problem. After a series of in-depth thinking, I expressed the descriptive solving process as a strict mathematical proof. At the same time, I found that the problem can continue to be promoted, combined with computer-aided research, the problem was promoted twice, and finally the problem was solved satisfactorily.
scientificity
Using strict mathematical methods, after detailed discussion, a series of conclusions are drawn.
progress
Using elementary mathematics to study a large-scale logical reasoning problem, the proof method adopted is also quite creative.
feasibility
This kind of problem is of great significance in mathematical logic and computer science, and this new idea of solving logical reasoning problems will have an impact on the solution of this kind of problem.
innovate
Abandoning the conventional thinking of logical reasoning, this paper analyzes the essence of the problem of "thinking nesting" and proves several important conclusions. In the process of proof, the concepts of multivariate array and grouping are used to describe the situation in the reasoning process, and mathematics is used to prove the abstract reasoning process, which is a theoretical leap.
In logical reasoning, there is a special problem-"thinking nesting", that is, in C's mind, we should consider how B thinks A's thoughts. This kind of problem is usually abstract, with many considerations and complicated ideological process, and the analysis effect with general methods is extremely poor.
First, the prototype of the problem
A logic professor has three students A, B and C who are good at reasoning and mental arithmetic. One day, the professor gave the three of them a question: the professor put a note on everyone's forehead and told them that everyone had written an integer greater than 0 on the note, and the sum of some two numbers was equal to the third. As a result, each student can see the whole numbers posted on the heads of the other two students, but he can't see his own numbers.
The professor asked A, B and C in turn: Can you guess the number on his head? After a few questions, when the professor asked others again, he suddenly showed a smug smile and accurately reported the figures posted on his head.
Our problem is to prove whether anyone can guess the number on his head. If anyone can guess, count the numbers on his head at the earliest question.
Let's analyze a simple example and observe how people reason.
Suppose there are three people, A, B and C, and the numbers on their heads are L, 2 and 3 respectively.
Ask a length first.
At this time, A can see that the numbers on the heads of B and C are 2 and 3 respectively. A will find that his avatar can only be 3+2=5, or 3-2= 1. But whether it is L or 5, A can't judge and can only answer "No".
Ask b again
B will find that his avatar can only be 3+ 1=4, or 3- 1=2. But whether it is 2 or 4, B can only be analyzed from A's answer: (The following is the analysis in B's mind)
If you have a 2 on your head. Then A can see that the numbers on the heads of B and C are 2 and 3 respectively, and A will find that it can only be 3+2=5 or 3- 2= 1. Whether it's L or 5, A can't judge and can only answer "No". This is the same as A's actual answer, not contradictory, so B can't rule out this situation.
If you have a 4 on your head. Then A can see that the numbers on the heads of B and C are 4 and 3 respectively, and A will find that it can only be 4+3=7 or 4-3= 1. Whether it's L or 7, A can't judge and can only answer "No". This is the same as A's actual answer, which is not contradictory, so B can't rule out this situation.
B can't judge, but can only answer "no".
Ask c again
C will find that his avatar can only be 2+ 1=3, or 2-1= L. But whether it is L or 3. C can only be analyzed from the answers of A or B: (The following is the analysis in C's mind)
If your avatar is 1.
A will find that his avatar can only be 2+l=3, or 2- 1= 1. But I can't judge whether it is L or 3, so I can only answer "No". This is the same as A's actual answer, not contradictory.
B will find that its header can only be 1+ 1=2 (because the header of B is an integer greater than 0, the header of B cannot be 1-l=0). B should answer "yes". But this contradicts B's actual answer. C can rule out the case that the head is 1.
If we continue to analyze the case that the C header is 3, we will find that it is not contradictory (consistent with the actual situation).
C will accurately judge that the number on the top is 3, so answer "yes". So in the third question, someone guessed the number on the head.
From everyone's point of view, we analyzed the situation that the number one person is L, 2 and 3. This method is also a common method for us to solve simple logical reasoning problems. But if we enlarge the scale of the problem, we will find that the complexity of the problem will rise sharply, and almost one more inference will double the complexity of the problem.
Such complicated reasoning can't solve the problem well. The reason is that there are a lot of "thinking nesting". That is, in C's mind, we should consider what B thinks of A. In addition, this method can't reach a general conclusion. Let's solve this problem in different ways.
We use the first, second and third students to represent A, B and C respectively.
It can be inferred that no matter how the three numbers change, no matter who starts asking questions, it must be the person with the largest number on his head who guesses the number on his head first.
From the above conclusions, we can see that for (a 1, a2, a3, K), the recursive formula of f(a 1, a2, a3, K) can be defined as:
When k= 1
When a2=a3, F (A 1, a2, a3, 1) = 1.
When a2 > a3, f (a 1, a2, a3, 1) = f (a2-a3, a2, a3, 2)+2.
When a2 < a3, f (a 1, a2, a3, 1) = f (a3-a2, a2, a3, 3)+ 1.
When k=2
When a 1=a3, f(a 1, a2, a3,2) = 2.
When a2 > a3, f (a 1, a2, a3,2) = f (a1,a1-a3,a3, 1)+ 1.
When a2 < a3, f (a 1, a2, a3,2) = f (a1,a3-a 1, a3,3)+2.
When k=3
When a 1=a2, f(a 1, a2, a3, 3)=3.
When a 1 > a2, f(a 1, a2, a3,3) = f (a1,a2, a 1-a2, 1)+2.
When Al < a2, f(a 1, a2, a3, 3)=f(a 1, a2, a2-a 1, 2)+ 1.
Since we only consider (a 1, A2, a3, k)∈= S3, k can be directly determined by a 1, A2, a3, so F (A 1, a2, k) can be simplified as F (A 1, a2.
Using the above formula, this problem can be solved by computer programming.
Because of the linear recursive relationship, the exponential growth of the problem scale with the number of problems is avoided, and the problem is effectively solved. The solution is based on an in-depth analysis of the problem. Now let's sum up the main idea of solving the problem:
Refine the important preconditions → consider what kind of situation is the "ending situation" → establish the equivalence relation of non-ending situation reasoning → consider what kind of situation can be attributed to "ending situation" → discuss and prove it in different situations → draw a conclusion and rewrite the equivalence relation → draw a formula.
The whole process starts with analyzing the essence of the problem, rather than simply starting from everyone's ideas, and deduces a general conclusion. Analyzing the problem from a global perspective avoids the most complicated "thinking nesting" and makes the scale of the problem change from exponential to linear.
Second, the first promotion
A logic professor has n(n≥3) students who are very good at reasoning and mental arithmetic. One day, the professor gave them a question: the professor put a note on everyone's forehead and told them that everyone had written an integer greater than 0 on the note, and a certain number was equal to the sum of other n- 1 numbers. As a result, every student can see the integers posted on the heads of other n- 1 students, but he can't see his own numbers.
The professor asked the students in turn if they could guess the numbers on their heads. After asking a few questions, when the professor asked someone again, the person suddenly showed a smug smile and accurately reported the numbers posted on his head.
Our problem is to prove whether anyone can guess the number on his head. If anyone can guess, calculate the number on his head on the earliest question, analyze the whole reasoning process and summarize the conclusion.
It can be inferred that no matter how the number of n changes, no matter who starts asking questions, it must be the person with the most heads who guesses the number on his head first.
From the above conclusions, for (a 1, a2…, an, k), we can define the recurrence formula of f ((a 1, a2…, an, k):
When 2W-M≤0, f((a 1, a2…, an, k) = k.
When 2W-M & gt；; O time
Let ai'=ai, where i≠k, AK' = 2w-m.
When v < k, f (a 1, a2 …, an, k) = f (a 1', a2' …, an', v)+k-v.
When v > k, f (a 1, a2 …, an, k) = f (a 1', a2' …, an', v)+n-k+v.
Since we only consider (a 1, a2…, an, k)∈=S3, k can be directly determined by the number of n, so f(a 1, a2…, an, k) can be simplified as f(a 1, a2…, an).
Using the above formula, this problem can be solved by computer programming.
At this point, the first promotion situation is solved. It can be found that the proof of the situation when n=3 provides a good contrast for solving the general situation and makes it easier for us to solve the problem, which is actually based on the analysis of the situation when n=3.
Third, the second promotion
A logic professor has n(n≥3) students who are very good at reasoning and mental arithmetic. One day, the professor gave them a question: the professor posted a note on everyone's forehead, telling them that everyone had written an integer greater than 0 on the note and divided them into two groups (one group had m students, (m ≥ n/2), and the students didn't know how to group them), and the sum of the numbers on the heads of the two groups was equal. Therefore, every student can see the integers posted on the heads of other N- 1 students, but he can't see his own numbers.
The professor asked the students in turn if they could guess the numbers on their heads. After a few questions, when the professor asked someone again, the person suddenly showed a smug smile and accurately reported the number posted on his head.
Our problem is to prove whether anyone can guess the number on his head. If anyone can guess, count the numbers on his head at the earliest question.
Because when n=3, m can only be 2, which is the prototype of the problem, and for m=n- 1, this is the first generalization. So we only discuss the case where n > 3 and m < n- 1.
For everyone to judge the number on the head, the number on the head may be different according to different grouping situations.
For (A 1, A2, …, An, k), the kth student can see the numbers on the heads of all students except himself. Assuming that under certain grouping conditions, the sum of the numbers on the heads of different groups of students can be calculated, and according to the topic condition that the sum of the numbers on the heads of two groups of students is equal, the number on his own head can be calculated. Because there are Cmn kinds of grouping situations, there are Cmn kinds of numbers on the corresponding header (which may also include some repeated numbers and non-positive integers).
Through reasoning, no one can guess the possibility of the head, because there is no situation, and the number of four is always decreasing in the process of reasoning, so after a limited number of reasoning, it will inevitably reach the "ending situation."
For the first generalization, that is, n=4 and m=3, someone must be able to guess the number on his head. Therefore, in all cases where n=4, someone must be able to guess the number on his head.
Because the current reasoning may still have various considerations under the condition of strengthening judgment. So the reasoning is not linear, and the whole reasoning process will become a tree structure.
Due to various grouping situations And complicated judgment methods, it is impossible to calculate the value of f(A 1, A2, …, an, k) by manpower at this time, but we can use the conclusions of the above proof and rely on the powerful calculation function of the computer to help solve the problem.