Han Xin ordered the soldiers.
Han Xin ordered soldiers, also known as Chinese remainder theorem. According to legend, Emperor Gaozu Liu Bang asked General Han Xin how many soldiers he commanded, and Han Xin replied that every three men 1 or more, five men 2 or more, seven men 4 or more, and 13 men 6 or more. Liu bang was at a loss and didn't know its number.
Let's consider the following questions first: Suppose the number of soldiers is less than 10,000, and there are only three people left for every five, 13, 17, so how many soldiers are there?
First find the least common multiple of 5,9, 13 and 17 (note: because 5,9, 13 and 17 are pairwise coprime integers, the least common multiple is the product of these numbers), and then add 3 to get 9948 (person).
There is a similar question in China's ancient mathematical work Sun Tzu's Art of War: "There are things today, I don't know their numbers, three or three numbers, two, five or five numbers, three or seven numbers, two, ask about the geometry of things? 」
A: "Twenty-three"
Technically, it says: "The number of three and three leaves two, take one hundred and forty, the number of five and five leaves three, take sixty-three, the number of seven and seven leaves two, take thirty, get two hundred and thirty-three, and then subtract two hundred and ten. Where the number of three is one, the number of seventy-five is one, the number of twenty-one is one, and the number of seventy-seven is one and fifteen, that's all. 」
The beauty of mathematics is not only reflected in beautiful conclusions and exquisite proofs, but also in unsolved mathematical problems. Different from Goldbach conjecture and Riemann hypothesis, some unsolved problems are very interesting, and their "mathematics" is very weak. At first glance, they don't touch profound mathematical theories. This seems to be an interesting math problem, which can be killed in an instant, which makes math lovers "unhappy because they can't find a clever solution" But surprisingly, they are as difficult as those famous mathematical conjectures, and may be more torturous than mathematical puzzles in various fields.
This article is very long, so you might as well mark it in your favorite way and read it a little every day.
Angels and demons.
Angels and demons play games on an infinite chessboard. Every time the devil can dig out any grid on the chessboard, the angel can land by flying 1000 steps on the chessboard; If the angel falls on the dug grid, the angel loses.
Question: Can the devil trap the angel (dig a hole with a thickness of 1000 around the angel)?
This is another classic puzzle of Conway Daniel. People who often read this blog will find that Conway Daniel's appearance rate is extremely high. But this time, Conway really broke the brains of many mathematicians. As a very "normal" combination game, the problem of angels and demons has not been solved. At present, it has been concluded that if the angel can only walk step by step, the devil will surely win. However, as long as an angel can fly two steps at a time, it seems invincible. Of course, the devil's advantage is not small-he doesn't have to worry about "problems", and every extra hole dug is beneficial to him.
On the other hand, Conway himself still seems to believe that angels can win-he offered a reward of $65,438+$0,000 for the devil to win, but only $65,438+$0,000 for the angel to win.
3x+ 1 problem
Starting from any positive integer, repeat the following operations: if this number is even, divide it by 2; If this number is odd, expand it to three times and add 1. Will the sequence eventually become 4,2, 1, 4,2, 1, …
This problem can be said to be a "pit"-at first glance, the problem is simple and there are many breakthroughs, so mathematicians have jumped into it; Little did they know that going in was easier than coming out, and many mathematicians did not solve the problem until their death. Numerous mathematicians have been recruited, which can be seen from various aliases of 3x+ 1 problem: 3x+ 1 problem is also called Collatz conjecture, Syracuse problem, Kakutani problem, Hasselblad algorithm, Ulam problem and so on. Later, because the naming was so controversial, we simply didn't let anyone get involved, so it was called 3x+ 1.
The problem of 3x+ 1 is not generally difficult. Here is an example to illustrate how irregular the convergence of a sequence of numbers is. From 26th, step 10 fell into "42 1 trap":
26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, …
However, counting from 27, the number will soar to thousands, and you may once think that it is out of the "42 1 trap"; However, after hundreds of operations, it still fell back:
27, 82, 4 1, 124, 62, 3 1, 94, 47, 142, 7 1, 2 14, 107, 322, 16 1, 484, 242, 12 1, 364, 182, 9 1, 274, 137, 4 12, 206, 103, 3 10, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1 186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 25 1, 754, 377, 1 132, 566, 283, 850, 425, 1276, 638, 3 19, 958, 479, 1438, 7 19, 2 158, 1079, 3238, 16 19, 4858, 2429, 7288, 3644, 1822, 9 1 1, 2734, 1367, 4 102, 205 1, 6 154, 3077, 9232, 46 16, 2308, 1 154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 6 1, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, …
Longest common subsequence of random 0 1 string
If the series B can be obtained by deleting some numbers from the series A, we say that B is a subsequence of A ... For example, 1 10 is a subsequence of 0 100 10, but it is not 001/kloc-0. There are many "common subsequences" of the two sequences, and the longest one is called "longest common subsequence".
Randomly generate two 0 1 sequences with length n, where the probability of number 1 is p and the probability of number 0 is 1-p, and Cp(n) is used to represent the length of their longest common subsequence and the limit value of Cp (n)/n.
There is a clever proof about the existence of Cp; But this proof only shows the existence of Cp, and does not bring any useful hints to the calculation of Cp at all.
Even the value of C 1/2, no one can successfully calculate it. Michael steele's conjecture c1/2 = 2/(1+√ 2) √ 0.8427. Later, V. Chvátal and D. sankoff proved that 0.77911< c1/2 <; 0.837623, it seems that michael steele's guess is probably right. In 2003, George Luc proved 0.7880.
To make matters worse, "Cp reaches the minimum when P is 1/2" seems to be a very reliable thing, but no one can prove this conclusion.
The inscribed square of a curve
Prove or disprove that there are always four points on any simple closed curve on the plane, and they can just form a square.
There are always four points on any convex polygon that can form a square; This conclusion can be extended to concave polygons by improving the proof method. At present, it seems that a positive conclusion has been reached for completely smooth curves; But for any curve, this is still an unsolved problem. There are all kinds of curves on the plane, so it is hard to say that we can really construct weird curves that do not meet the requirements.
Circular runway problem
There is a circular runway with a total length of 1 unit. N people started from the same position on the runway and ran clockwise along the runway. Everyone's speed is fixed, but different people have different speeds. Prove it or overthrow it, for everyone, there will always be a moment when the distance between him and others is greater than1/n.
At first glance, this problem is no different from other very clever elementary combinatorial mathematics problems, but strangely, this problem has not been solved yet. At present, the best result is that when n ≤ 6, the conclusion holds. Intuitively, for a larger n, the conclusion should also hold, but it has not been proved.
Enhanced version of sorting problem
There are n boxes numbered 1, 2, …, n from left to right. Put two balls numbered n in the box of 1, put two balls numbered n- 1 in the second box, and so on. Put two balls numbered 1 in the box of n. Each time, you can take a small ball in two adjacent boxes and exchange their positions. How many times do you change all the balls in the box on the right?
In order to illustrate the trap behind this problem, we might as well take the case of n = 5 as an example. First of all, if there is only one ball in each box, the problem becomes a classic sorting problem: only adjacent elements can be exchanged. How to change 5,4,3,2, 1 into 1, 2,3,4,5 as quickly as possible? If a certain number in front of a sequence is greater than a certain number in the back, we say that these two numbers are "reverse order pairs". Obviously, in the initial case, all pairs are inverse pairs, and when n = 5, there are 10 inverse pairs * *. Our goal is to reduce this number to zero. But swapping two adjacent numbers can only eliminate one reverse pair, so it needs 10 swapping.
However, there are two balls in each box in the title. Is it necessary to exchange them 20 times? No! The following methods can miraculously complete sorting in 15 steps:
55, 44, 33, 22, 1 1
54, 54, 33, 22, 1 1
54, 43, 53, 22, 1 1
54, 43, 32, 52, 1 1
54, 43, 32, 2 1, 5 1
54, 43, 2 1, 32, 5 1
54, 3 1, 42, 32, 5 1
4 1, 53, 42, 32, 5 1
4 1, 32, 54, 32, 5 1
4 1, 32, 42, 53, 5 1
4 1, 32, 42, 3 1, 55
4 1, 32, 2 1, 43, 55
4 1, 2 1, 32, 43, 55
1 1, 42, 32, 43, 55
1 1, 22, 43, 43, 55
1 1, 22, 33, 44, 55
It seems incredible at first, but when you think about it carefully, you will understand that being able to put two numbers in the same box has really opened up many new possibilities. If a number in the left box is greater than a number in the right box, we say that these two numbers form an inverse pair; But if two different numbers are in the same box, we regard them as semi-reverse pairs. Now let's see how many reverse pairs can be eliminated at most in one exchange. Assuming that ab and cd become ac and bd after a certain exchange, the best case is that bc is completely eliminated, AC and BD are eliminated by half, and AB and CD are also eliminated by half, then at most three reverse pairs can be eliminated at one exchange. Because the two identical numbers in each box will be separated at the beginning at some time in the middle and then merged together, we can regard these two identical numbers as an inverse pair at the beginning. In this way, every two numbers are reverse pairs at first, and C(2n, 2) reverse pairs will be generated in N boxes. Naturally, we need at least C(2n, 2)/3 steps to complete the sorting. When n = 5, C(2n, 2)/3 = 15, which shows that the sorting scheme given above with n = 5 is the best.
This analysis is so ingenious that it is really amazing. Unfortunately, this lower limit is not always reached. When n = 6, the lower limit of the above analysis is 22 steps, but the computer exhaustively finds that it is impossible to exchange without 23 steps. In this way, this problem has become an attractive pit, which has not been filled up so far.
Polyhedral expansion
Prove or overthrow, you can always cut a convex polyhedron along the edge and expand it into a simple plane polygon.
This is a seemingly "natural" problem, and perhaps everyone has already thought about it when playing with various paper packaging boxes. Now, people have found a concave polyhedron that does not meet the conditions, that is to say, the existence of a concave polyhedron makes it inevitable to get a planar polygon that overlaps with itself no matter how it is unfolded. At the same time, there are some convex polyhedrons. After expanding them in a certain way, you will get a plane polygon that overlaps with yourself. However, for a convex polyhedron, there is no way to expand it into a plane, which seems impossible; However, this has never been proved in mathematics.
A polygon composed of plane mirrors.
Prove or disprove that there can always be a point in any polygon whose inner wall is covered with mirrors, so that the light source at that point can illuminate the whole polygon.
This is a very creative question, but unfortunately the earliest source of the problem has disappeared. The interesting problem is that the condition of "polygon" is necessary: if curves are allowed, we can construct a plane figure composed of mirrors (left), in which each point cannot illuminate the whole figure.
For the case of polygons, Tokaski gives a room with 26 sides (right) in 1995. If the light source is placed on one of the points, it will not shine on the other point (assuming that the vertex does not reflect light). So, there is only one question left: Is there a polygon that cannot be illuminated by a light source at any position?
Thrackle conjecture
If every edge of a graph intersects all other edges exactly once, the graph is called a chromatic cycle graph. Q, is there a thrackle graph with more edges than vertices?
Give you a chance to guess who put forward this conjecture! Yes, it's john conway again. This is obviously another pit. Everyone wanted to try this problem when they saw it, and then they all collapsed. Conway offered a reward of $65,438+0,000, which shows how difficult this problem is. The best result known at present is that the number of edges of a color ring will not exceed twice the number of vertices minus 3.
Traverse all "intermediate subsets"
To prove or disprove, all subsets of the set {1, 2, …, 2n+ 1} with the size of n or n+ 1 can be traversed by adding or deleting one element at a time.
After reading this line, I can imagine that you have an irresistible impulse, pick up a pencil, draft paper and computer, and start looking for the law when n is not big. This can be said to be the biggest pit of all the problems in this paper-this question is very tempting. When you first see this problem, you will think that there is a structural solution applicable to all n, so everyone jumps into the pit one by one and can't stop.
No one thinks this conjecture is wrong. Simple computer enumeration shows that with the increase of n, the number of schemes traversing these subsets not only increases, but also grows very fast. On a certain n, the number of schemes suddenly drops to 0, which is obviously an extremely unlikely thing. However, after decades, no one can prove it!
On venn diagram
Accustomed to drawing three episodes of venn diagram, many people think that drawing four circles in the same shape as a flower is the venn diagram of four episodes. In fact, this is not the case-four circles can only produce 14 areas, while four sets will hand over 16 situations. If the four circles are arranged like the middle picture, two areas are missing: the area belonging to the lower left corner and the upper right corner, and the area belonging to the upper left corner and the lower right corner.
So, can't you draw four sets of venn diagram? Not exactly. If you are not a perfectionist, you can expand three groups of venn diagram into four groups as shown on the right. Although it looks ugly, from the perspective of topology, as long as the logic is correct, who cares if it is round?
You will naturally think of a question: Can the graph on the right continue to expand into a venn diagram with five sets? More generally, can the venn diagram of any n sets be generalized to n+ 1 sets?
Incredibly, this problem has not been solved! In fact, the study of venn diagram who meets all kinds of conditions is an enduring topic, and there is more than one conjecture related to venn diagram.
Elements that appear more than half the time.
Let U be a finite set, and S 1, S2, …, Sn are all nonempty sets of U, and the sum of any number of sets they satisfy is still in these sets. It is proved that an element must be found and it appears in at least half of the set.
Incredibly, even the most basic and discrete mathematical research object-finite set contains unsolved problems that make people collapse.
In 1999, Piotr Wojcik proved in a very clever way that there is an element in the set of at least n/log2n. However, this is still a long way from the goal.