Three businessmen each took a follower across the river by boat. A small boat can only accommodate two people, who row by themselves. The followers reached a secret agreement. On one side of the river, there used to be more followers than businessmen. They would kill people and steal goods. But how to cross the river by boat is in the hands of businessmen, and how can businessmen cross the river safely?

It needs to be solved by mathematical methods, one is to give an example of modeling, and the other is because this model solves a wide range of problems and is easier to popularize than the result of logical thinking.

Now that the problem has been idealized, there is no need to make a hypothesis. The problem of crossing the river safely can be regarded as a multi-step decision-making process. Every step, that is, the ship sails from this shore to the other shore or returns to this shore from the other shore, must make decisions for the people on board, and let all people cross the river in a limited number of steps under the premise of ensuring safety.

Using state variables to represent the personnel state of a certain shore and decision variables to represent the personnel state of the ship can find out the law of the state changing with the decision. The problem is transformed into determining the decision of each step within the allowable range of the state, so as to achieve the purpose of crossing the river.

Over-exploitation of the model:

Remember that before crossing the river for the k th time, the quotient of this bank is xk, and the number of followers is yk, k = 1, 2, ..., xk, yk, k= 1, 2, ..., and the two-dimensional vector sk=(xk, yk) is defined as the state.

The state set under the condition of crossing the river safely is called the allowable state set, and it is not difficult to write it as S.

S={(x，y)|x=0，y=0， 1，2，3； x=y= 1，2} - ( 1)

Let's remember that the number of businessmen at the k-th ferry is uk and the number of followers is vk. We define the two-dimensional vector dk = (uk, vk) as decision, and we record the allowed decision set as D. According to the capacity of the ship,

D={(u，v)| u + v = 1，2 }- (2)

Because when k is odd, the ship sails from one shore to the other, and when k is odd, the ship sails back from the other shore to this shore, so the law of state sk changing with decision dk is as follows:

sk+ 1 = sk + (- 1) k d k - (3)

(3) This formula is called the law of state transition, so making a safe crossing scheme can be summed up as the following multi-step decision-making problem:

Find the decision dk ∈ d (k = 1, 2, ... n), and make the state sk∈S reach the state sn+1= (0,0) from the initial state s1= (3,3) after a limited number of steps.

Model solving

According to (1)~(3), it is feasible to use computer to write programs to solve multi-step decision-making problems, but it is more convenient to use graphical method to solve this model when there are not many businessmen and followers.