During the summer vacation I was supposed to help Bobo prepare a book of logic and reasoning puzzles, so after coming back to Shanghai I went rummaging through the pile of Olympiad math books and recreational math books that I had kept at the bottom of my chest. I had always had the most of this kind of book, so finding several dozen problems was easy enough. Of course, for the sake of originality, I would rewrite both the problems and the solutions.
The first thing that came to mind was the classic five pirates dividing the loot problem: five pirates divide 100 gems. The five men in turn propose a distribution plan; if the plan receives support from more than half of the living pirates, it passes. If it does not pass, the pirate who proposed it is thrown into the sea and the rest continue. Everyone is sufficiently clever that, as long as they are not thrown into the sea, they will choose the greatest benefit. The question is: how many gems can the first pirate obtain at most? In this problem, the number of pirates can be changed to more than 100, or to 500, and so on; the situation then changes again…
I also thought of a recreational thought problem. Strictly speaking it cannot count as a logic puzzle, but it is quite interesting:
Three People Divide Peach Juice:
There is an ancient story of “two peaches kill three warriors”; indeed, dividing spoils among three people is not easy. Thinking in the style of a brainteaser, someone might say: why not just squeeze it into peach juice? That is certainly not a bad idea, but dividing peach juice among three people also does not seem to be an easy matter…
Without measuring instruments, relying only on visual estimation and manual division, how can we make all three people feel that the distribution is fair?
The condition is this: all three believe that their own cutting ability is guaranteed to be the fairest, but they do not trust the cutting skills of the others.
………………………………………………………………
Hint:
First refer to the idea of “two people dividing a cake”: it is very simple. Person A first divides the cake into two portions that he himself considers fair, and then lets B choose one of them. In this way both sides will feel it is fair.
………………………………………………………………
Solution:
A first divides it into three portions that he considers fair: A, B, C.
Then B comes along and re-divides the three portions. There are two cases:
Case 1: B thinks that, among A’s divisions, one portion is greater than or equal to one-third, and the other two are both less than or equal to one-third. Let us suppose B reduces A and increases B and C. At this point the three portions after B’s changes are denoted A-, B+, C+.
Then C comes to inspect. If C thinks the largest is A-, then C takes A- himself, and however the remaining two are divided between A and B, both will feel it is fair.
If C thinks the largest is B+ or C+, let us suppose C thinks the largest is B+. Then give C+ to A and A- to B, and that will do.
Case 2: B thinks that, among A’s divisions, one portion is less than or equal to one-third, and the other two are both greater than one-third. Let us suppose B reduces A and B, and increases C. At this point the three portions after B’s changes are denoted A-, B-, C+.
Then C comes to inspect. If C thinks the largest is A- or B-, let us suppose C thinks the largest is A-. Then C takes A- himself, gives C+ to A, and gives B- to B, and that will do.
If C thinks the largest is C+, then let us suppose C thinks the smallest is A-. Then give A- to B. Then, in the “two people dividing a cake” manner, put B- and C+ together, divide them again into two portions that C considers fair, and finally let A choose one of them. Since A- is even smaller than one-third as A sees it, A will think that B- and C+ together exceed two-thirds. In the end everyone will feel it is fair.
2006年8月3日
2008-12-01 18:48:30
Go on and keep forcing onto me the line of thought that originally wasn’t mine… What is the point of that? You say I drew many erroneous conclusions, but in fact, tell me, which conclusion have I actually drawn? I have drawn almost no conclusions at all. The only conclusion I gave was this: the problem is not as simple as you originally thought. That is all. The rest was just picking apart your mistakes. What false premise did I use? I was only saying that your premise is unreliable, that it is circular reasoning.
If you admit that your argument is not rigorous, then my purpose has been achieved; if you stubbornly refuse to admit it, then I have nothing to say. In any case, I have no greater ambition to solve this problem. If you sincerely want to give a complete and rigorous argument, then please do not tangle with me in this muddle: just write out the complete argument directly, and I will be glad to help you check it. Otherwise, what exactly are you arguing with me about?
Let me give you one last hint about your mistake: “once the probability table of 5 regarding these four numbers is formed, the choices of 1–4 will depend only on this table” — that is right! But the “>” and “=” in the probability table are fundamentally different! They absolutely must not be simplified into “>=”. A person’s game strategy, even if it increases the degree of bias by just a tiny bit, will undergo a qualitative change. And the key points of the scheme I proposed earlier all lie in the 50%-50% equal case. How can you cover up the “=” cases with a single >=?
You may perhaps find a new rebuttal, but I hope you will not spend all your energy entangling yourself with me, because I have always merely been pointing out your loopholes and never had any intention of giving an independent proof; I have said this again and again and again. Did you actually hear it? Did you actually acknowledge that I never intended to give an independent, complete scheme? Did you actually acknowledge that your original argument was not rigorous?
If you have already written out a complete and self-confidently impeccable argument, you can send the whole thing to me, and then I will tell you which line is wrong. Or if I cannot find any error, then I will certainly admit that you are indeed formidable. If you cannot produce the final result, then please allow me not to want to discuss this problem any further. I have long since admitted that this problem is beyond my ability, and I also do not have much enthusiasm for self-challenge. I think you should be able to allow me to lay down my arms and surrender, shouldn’t you? To allow me to stop trying to solve this problem? Why must I agree with you before I am allowed to give up?
2008-12-01 18:01:23
I remember that you spent a long stretch arguing that No. 5 must choose 16 and 17, in order to put pressure on No. 1 and leave room for himself, and also about how 16 and 17 are symmetric, etc…
I don’t seem to have pointed it out directly, but from my examples you should have been able to see that I simply do not think this is correct—I assumed you would gradually understand it yourself, but apparently not. My view is: once the probability table for No. 5 with respect to these four numbers is formed, the choices of Nos. 1–4 will depend only on that table, and have nothing whatsoever to do with the probability reasoning before it. Those four numbers are equivalent for No. 5; there is no issue of which one should be chosen first, and no issue of symmetry either. On this problem you have probably fallen too deeply into it, and so derived many wrong conclusions. Think carefully: is that premise of yours actually wrong? 🙂
2008-11-30 20:01:58
The good thing about mathematics is precisely that if you are wrong, then you are wrong, and you have no choice but to admit it. So when you proposed a better scheme for the “three people dividing peach juice” problem, I too at first was convinced that you were wrong. But then I figured it out and admitted that I had misread it—you were right. That really is nothing much.
But that has nothing to do with what is going on here. I had already pointed out myself that the scheme I gave had loopholes, and I also pointed out exactly where my scheme was not rigorous. But you insist on using your own set of faulty arguments to identify my mistakes; of course I cannot accept that.
Why did I end the discussion? Indeed, even if I am busy with homework, if it is an interesting question, I am willing to discuss it. So the real reason for ending the discussion is that this discussion has become uninteresting. I found myself repeatedly restating issues I had already mentioned, yet for you they counted for nothing at all, and you kept forcing me to repeat and repeat what I had already said.
The oversight you mentioned at the end, of course, is not what I called the mistake. Do I really need to repeat myself yet again? Then I’ll repeat it once more—I said, “your argument made an obvious mistake from the very beginning.” Note: “from the very beginning,” not waiting until some 1-a or whatever to appear. So this general argument of yours cannot help you perfect things, because the first step already failed at the outset—“and I had already hinted at this point many times as well.” I wrote it all like this, and yet you seem not to have seen it, instead imagining on your own that what I discovered was some trivial loophole like this… So in short, I feel that in the later discussion many of the things I said were said in vain, because you simply did not notice them. So I won’t say more. Say more and it’s just the same repetition over and over; you still won’t pay attention, and it will only waste energy.
I have long admitted that, in rigorously solving this problem, I am powerless. I can’t do it! So what if I can’t do it? In real life everyone will have many things they cannot do. What is a paper-and-pencil problem you cannot solve worth? But if it is because you are unwilling to admit that you have not solved it, and so you remain unwilling to end the discussion, and even insist on dragging others into endless fuss, then I think this is no longer just a matter of solving a problem; it shows that your state of mind is still not mature enough.
2008-11-30 19:00:17
I was away for two days, and thought you must have enriched the discussion a great deal; I didn’t expect that you would say the discussion had been stopped.
Perhaps it is really as you said: the teacher assigned homework; you lost interest in mathematics…
Or perhaps there is another reason: for example, you saw that the conclusion about to be reached was unfavorable to you…
Actually, with your clever mind, you could easily flesh out and perfect the proof I mentioned, extending it to the general case; or else point out its fatal loophole that cannot be repaired.
I think the overall atmosphere of our discussion was good. Although there were some heated words in the middle, we were always focused on the main line of solving the problem. After all, isn’t this just a single problem? Right or wrong—what’s the big deal? Who doesn’t make mistakes? In real life everyone makes mistakes too; what does a mistake in a paper-and-pencil problem amount to? But if it really is because you discovered your own mistake and thus ended the discussion, then I think this is no longer merely a question of whether one problem is right or wrong; it shows that your state of mind is still not mature enough. Would people from Tsinghua or Peking University never make mistakes? In fact, becoming aware of your own mistake, and helping your opponent perfect the proof of his own mistake, not only does not lower your value, it will make you admired by others—don’t you think so?
I hope that the latter reason I mentioned does not exist; then what I said above can be taken as if unsaid.
Wish you smooth sailing! 
2008-11-26 14:53:06
You’re the stubborn one. Why won’t you think one layer deeper? I have already said that 16 and 17 are not just any two numbers; the fifth person can only use the choice of 16 or 17 to threaten the first and second people. In fact, the fifth person’s threat is only effective against the first two people. If the fifth person reduces the probability of choosing 16 or 17 and increases the probability of choosing 15 or 18, then he will no longer pressure the first and second people. If the fifth person chooses 16 and 17 with 30% probability each, and chooses 18 or 15 with 20% probability each, then he cannot threaten the first and second people, because although the first person will have only an 80% survival rate if he chooses 16 or 17, his survival rate would be even lower if he chose 15 or 18, so he will not be forced to switch. And if the fifth person does not pressure the first two people, then he has no other way. In fact, the third and fourth people will not be threatened by the fifth person. Even if they know that the fifth person has set his sights on them, their survival rate is still at least 50%; and if they change their strategy, their survival rate will actually be lower than 50%, so the fifth person cannot force them to give way by threatening them. The key is that only the first and second people have a relatively large advantage; they have the chance to obtain a survival rate far above 50%, so the threat is effective. The survival rates of the third and fourth people are already around 50%; no matter how you threaten them, because of symmetry, the death rate under threat generally will not exceed 50%, so the third and fourth people are not targets of threat. Therefore the fifth person’s only method is the threat of a suicide attack, and the only possible targets on which this method can work are the first two people; and the only way this method can affect the first two people is by choosing 16 or 17 with an extremely high probability—and if he chooses 1 or 2, and so on, there is no threat to the first two people at all. So the clever first person can of course know that threatening 16 and 17 is the only method the fifth person will inevitably use. Do you understand now? If not, forget it; I won’t say any more.
Comments temporarily closed.
Correction: “If the fifth person chooses 16 and 17 with 30% probability each, and chooses 18 or 15 with 20% probability each, then he cannot threaten the first and second people, because although the first person will have only an 80% survival rate if he chooses 16 or 17, his survival rate would be even lower if he chose 15 or 18, so he will not be forced to switch.”
It should be: “If the fifth person chooses 16 and 17 with 20% probability each, and chooses 18 or 15 with 30% probability each, then he cannot threaten the first and second people, because although the first person will have only an 80% survival rate if he chooses 16 or 17, his survival rate would be even lower (70%) if he chose 15 or 18, so he will not be forced to switch.”
And at that point the first and second people will not switch, but will still choose 16 and 17; yet the third and fourth people will also not switch, because if they still choose 15 or 18, their survival rate will in fact rise to 70%, which is exactly what they want, and they absolutely cannot give way to the fifth person.
So the strategies by which the fifth person may threaten the first two people are by no means infinite; in fact they are very few. He must choose 16 or 17 with a very high probability for the threat to work; once that probability falls below a certain value, it will no longer be threatening.
So the fifth person’s strategy must first ensure that the probability of 16 or 17 is large enough to threaten the choices of the first two people, and then consider how he can maximize his own survival rate. This consideration of increasing survival rate will further screen out the optimal strategy. For example, if choosing 16 or 17 with 50% probability each can give him an x% survival rate (because of the subtlety of the fourth person, it seems not even possible to reach 50%). But if he chooses 16 or 17 with 49% probability each, and 1 with 2% probability, then although it is still enough to threaten the first two people, the survival rate the fifth person gets will certainly not be greater than x, because the extra possibility of choosing 1 has no effect on the situation; it is simply suicide.
So according to the survival rate ultimately brought to the fifth person, we can rank all the strategies of the fifth person that can threaten the first two people. Among them there must be one strategy that brings the greatest survival rate. Then this strategy is the fifth person’s optimal strategy. This strategy is uniquely determined, and any intelligent person can work it out; so there is no need for the fifth person to declare it—other intelligent people can already know the optimal strategy that the fifth person will inevitably adopt.
That’s all!
2008-11-26 13:45:05
The problem is already so clear—haven’t you realized it yet?
For example, according to your idea, we can set up countless optimal strategies for No. 5, and their results (by your reasoning) would all give No. 5 a 50% chance of survival. For example: No. 5 could have an optimal strategy 2: choose 15 and 16 respectively with 50% probability, or optimal strategy 3: choose 18 and 15 respectively with 85% and 15% probability… and so on. On what grounds do you say he must cling stubbornly to 16 and 17 and force Nos. 1 and 2 to give way?
As for your repeated mention of game theory principles and logical calculation, I imagine you must be quite well-versed in this area, but now even if you drag in the entire textbook, it still won’t save No. 5’s life, because truth becomes clearer the more it is argued over 🙂
Sorry if that came out a bit harsh; I just think you’re too stubborn 🙂
2008-11-26 09:09:03
Let me briefly summarize:
Igeli’s answer contains two conclusions.
A: The first two people will respectively choose 16 and 17 beans; the first four people will take away 15, 16, 17, and 18 beans.
B: The fifth person abandons any specific strategy and just randomly picks some number from the remaining beans.
But how are these two conclusions argued for? In fact, the argument for A requires the inevitability of B as a premise. In fact, the reasoning behind A contains something like: “B is inevitable; the first four people are intelligent; therefore the first four people know B; therefore the first four people, in the context of B, will calculate the survival rate corresponding to their own choices; therefore the first four people will certainly make such-and-such a trade-off; therefore A.”
And on the other hand, how does B come about? In fact, B also takes the inevitability of A as a premise. Its reasoning goes something like: “A is inevitable; the fifth person is intelligent; therefore the fifth person knows A; therefore the fifth person will know that he is doomed to die; therefore B.”
But this circular argument cannot really prove the inevitability of A or B. At most it only shows that they are not contradictory. In fact, “not A and not B” also does not lead to a contradiction.
If one has studied modal logic, then expressing this in the language of modal logic may make it even clearer: what Igeli proves is “□A→B” (if A is necessary, then B) and “□B→A” (if B is necessary, then A). But what I prove is “◇～A→～B/or written ～□A→～B” (if non-A is possible, then non-B); “□～B→～A” (if non-B is necessary, then non-A); and “～□B→～□A” (if B is not necessary, then A is not necessary either; in other words, if non-B is possible, then non-A is possible).
As for the fifth person, he has the capacity to choose. He can choose B as a mode of action, and he can also choose ～B. He can choose to always B, that is, □B; but he can also, in any situation, reject B, that is, □～B, by refusing to find out the remaining beans and refusing to obtain sufficient knowledge of the situation.
And the condition says that the fifth person is an extraordinarily intelligent person, so he will certainly choose the best strategy.
And for him, as long as he chooses ～□B, or even □～B, he can obtain the possibility of survival. But if he chooses □B, then he is doomed. So the intelligent him will certainly not make □B true. In this way □A no longer holds either.
The formalization of this question still needs some additional modal operators, for example using “□1, □2, □3, □4, □5” to respectively mean “the first person knows…” “the second person knows…” and so on, while the precise definition of “an intelligent person” can be: “□p→□1p” — that is, an intelligent person can know everything that is necessary. But here necessity refers to logical necessity, not factual necessity; that is to say, even when the fifth person makes his choice, he is in fact already doomed to die, he can still choose not to know this, if his actual condition of being doomed to die is not logically necessary.
In short, I can at least prove that Igeli’s proof is wrong; that is logically clear. Of course, I guess the question setter did not originally intend to make it this complicated, but that is another matter.
2008-11-25 20:53:26
You have not understood the principle of the game-theoretic problem. Anyway, now as the fifth person, the strategy I take is to pick 16 or 17; as the first person, your strategy is also to pick 16 or 17. Fine, now my strategy has reached equilibrium, because no matter how I adjust my strategy I still cannot obtain even a sliver of hope of survival, so my strategy settles on 16 or 17. But at this point, equilibrium has not yet been reached for you; you still have a better choice, so the game must continue. If you slightly adjust your strategy and increase the probability of choosing 15 or 18 a little, your winning rate will rise a little, so you will continue to adjust your strategy.
Of course, I have already said everything that needed to be said. If you still do not understand, I’m afraid it is because you are not sufficiently clear about the concept of game theory. Of course I don’t know that much either, but I think this problem does not require overly deep knowledge of game theory to understand.
If you still have questions, you can consult some authoritative institution.
Of course, some assumptions in game theory, as well as concepts like “extraordinarily intelligent” in this kind of problem, are all open to challenge. If you raise targeted objections to these concepts, I’m still willing to take another look; otherwise, let’s end this discussion here.
And don’t discuss other mathematical problems with me anymore either; at least for the time being I don’t want to keep wrangling over this.
By the way, you might as well think again about that game of “commander, sapper” versus “bomb, platoon leader.” Keep the other rules unchanged, and change one rule: namely, if the platoon leader encounters the sapper, then he has only a 50% chance of killing the other side, and a 50% chance of still being killed by the sapper. If both people are intelligent and both know that the other is intelligent, what will happen? What strategy should be adopted?
Where does the following reasoning go wrong:
If B throws out a bomb, B is dead for sure, so the intelligent B will not throw out a bomb. B will necessarily throw out platoon leader.
So if A throws out commander, A will definitely live; if A throws out sapper, there is a risk of death. Naturally the intelligent A must throw out commander.
B knows that A is extraordinarily intelligent, so B knows that A will necessarily throw out commander.
So B knows that even if he himself throws out platoon leader, he is doomed to die.
Knowing full well that both options lead to death, B has no reason to prefer either one. So B will throw out bomb or platoon leader with equal probability. (A contradiction has already appeared here.)
As a result, A will have a 50% chance of being blown up.
But the intelligent A knows that B can only throw out bomb or platoon leader with equal probability.
So A knows that if he throws out sapper, he will have a 3/4 survival rate.
3/4 is greater than 1/2. So the intelligent A must throw out sapper.
The intelligent B understands the intelligent A’s choice, so B must throw out platoon leader.
……
Where is the problem? The key is that the assumption “when one knows that both choices lead to death, one will simply pick one at random with equal probability” is questionable. The key is: what does it mean to “know one is doomed to die”? Especially if this doomed situation itself is related to the choice he will make when doomed, then how can one know clearly that one is doomed to die before deciding what choice one will make when doomed? Especially if the rules allow one to choose with eyes covered, without fully knowing information that could be known. Then before you have made your choice, how can you know full well that you are doomed to die?
You cannot additionally invoke an observer’s perspective on this problem. For the observer, when the fifth person begins to choose, the first four people’s choices of course have already become fixed facts. But the key is that the fifth person “can” “not know.” The fifth person has the right to decide to make a choice without knowing enough information. And the question is, in the reasoning you used to conclude that the first person must choose 16 or 17, you relied on the assumption that the fifth person can only pick randomly. But this assumption does not hold. The fifth person has ample reason not to pick randomly, so the reasoning that the first person must choose 16 or 17 does not hold.
That paradox in the “commander, sapper” versus “bomb, platoon leader” game is still quite interesting — if we alter the original question a bit, for example, B has two bombs and one platoon leader in hand. If B is an irredeemable idiot and cannot even distinguish the meaning of bomb and platoon leader, he will only randomly throw out one card, that is, 2/3 bomb and 1/3 platoon leader. And A knows that B is an idiot, knows that B will be randomly throwing cards around, then A will choose sapper 100% of the time to ensure the highest survival rate, namely 2/3 (if A chooses commander, then the survival rate is only 1/3). Thus the idiot B also obtains a 1/3 survival rate. But if B is not an idiot but an extraordinarily intelligent person, then he will realize that throwing a bomb is suicide no matter what, so he will never throw a bomb. And if A knows B is an intelligent person, then he knows that B will definitely only throw out platoon leader (note: this is questionable), so A will certainly throw out commander; as a result, compared with the idiot B who survives 1/3 of the time, the intelligent B instead is doomed to die. Is this what it means for intelligence to backfire? But for an intelligent person seeking survival, does he have the right to abandon his knowledge? Why is it that something an idiot can do, an extraordinarily intelligent person instead cannot do?
2008-11-25 20:26:19
I think your biggest problem is that you have imagined that No. 5 has an optimal strategy, but the first four people can see that, given the established facts, No. 5 does not have an optimal strategy. In your words: “Even if the opponent knows his strategy, he will still be helpless, because even if he knows the opponent’s strategy he cannot adjust to a new strategy to improve his winning rate; at this point the game has reached an equilibrium state.”
I think there is no need to discuss this problem any further, because all the logic is already very clear and the equilibrium point has already been solved. Under this equilibrium point, no participant can further improve his winning rate. If you have any questions about this conclusion, you can consult some authoritative institution. I think this problem is not yet complex enough to be beyond ordinary people’s understanding.
2008-11-25 19:19:48
If a game-theoretic problem has a solution, then each person’s strategy is precisely optimal, and even if the opponent knows his strategy, he will still be helpless, because even if he knows the opponent’s strategy, he cannot adjust to a new strategy to improve his winning rate; at this point the game has reached equilibrium.
For example, what is the optimal strategy in rock-paper-scissors? It is to play rock, scissors, and paper each with probability 1/3, and the winning rate at equilibrium is 50%. This equilibrium position can be understood as the equilibrium reached in infinitely repeated gambling. For example, if your initial strategy is to play rock 100% of the time, then after many rounds I discover your strategy, and then I readjust my strategy according to your move probabilities, I will increasingly increase the probability of playing paper. But after many more rounds, when you discover that I am increasingly increasing the probability of playing paper, you will increasingly increase the probability of playing scissors… thus both sides’ strategies are continuously adjusted, but this adjustment is not disordered; it has direction. You will discover that when both sides adjust their strategies in consideration of improving their winning rates, they always move closer and closer to the optimal strategy, namely 1/3, 1/3, 1/3. Finally, when both sides’ strategies all approach adjustment toward 1/3, 1/3, 1/3, the game tends toward equilibrium, and even if both sides see the other side’s strategy, they are helpless — even if I know your strategy is 1/3, I cannot find a better strategy. Of course, if I know your strategy is 1/3, then reverting to a strategy of 100% rock would also get the same winning rate, right? So how can that be called equilibrium? But there is nothing to be done; the equilibrium of a game problem is exactly what this means. This is the optimal strategy; to say that at equilibrium one can just switch back again is pure quibbling.
If the game of grabbing green beans is also understood according to the general rules of game theory, then the question is simply where this strategy’s final equilibrium lies, and whether such an equilibrium point exists. Now the fifth person takes the strategy of 16 or 17; what should the first person do? The first person will certainly adjust toward the strategy with a higher winning rate, and then the later few people, after knowing the first person’s adjusted new strategy, will in turn adjust their own strategies for a higher winning rate; after the later people adjust their strategies, if the first person still has room to improve his winning rate he will continue to adjust his strategy… In short, if there is a solution in the end, it will be an equilibrium, and at that point knowing everyone else’s strategies will be useless; it will no longer be possible to use them to improve one’s own strategy. That is the solution to the game-theoretic problem. And here, even if 16 or 17 is not the fifth person’s final equilibrium strategy, if it is an intermediate state of the game, then clearly there is no reason for his strategy to converge toward the strategy of randomly choosing at will.
2008-11-25 18:58:13
Right, he has no way to declare in advance that he will choose No. 16 with 100% probability. Because the people before him cannot predict this strategy of his, since 16 and 17 seem to have some kind of symmetry (of course I have not rigorously proven that the symmetric pair is 16 and 17; perhaps it is 15 and 16, no matter, but it is very likely 16 and 17), that is to say, the survival rate of the fifth person “if the earlier people know that the fifth person will definitely choose 16” is the same as the survival rate of the fifth person “if the earlier people know that the fifth person will definitely choose 17.” Then the earlier people cannot guess whether the fifth person will choose 16 or 17. But the effect of the fifth person choosing 16 is obviously different from his choosing 1; they are asymmetric, so the intelligent fifth person has reason to place more probability on 16 and 17.
In game-theoretic problems, the reason one side’s optimal strategy must be given in probabilistic form is that under the relevant circumstances one must increase the uncertainty of one’s own move in order to increase one’s winning rate. And if increasing the likelihood of an option will not improve one’s winning rate, then that option will not be considered. That is to say, for example, options like taking 1 bean or 2 beans will not be considered by the fifth person, because even if he increases the probability of making such a choice, it will not cause any disturbance to the opponent, and thus will not increase his own winning rate. But the options 16 and 17 can maximally disturb the opponent, thereby increasing his own winning rate, so the fifth person will certainly incline toward choosing 16 or 17. This strategy is something the first person can foresee.
Do you lack understanding of game theory? Game-theoretic problems can be transformed into gambling problems. For example, here the consequence of grabbing green beans is not a one-time loss of life, but rather that the loser loses money, and the game is repeated many times. Then if you are the first person and I am the fifth person, what strategy would you take? If you stubbornly insist on always choosing 16 or 17, then in 100 games you will only win about 50 times, whereas if you are willing to change to another plan, your winning rate will rise greatly to 75%, so that is your optimal plan. If you know there is a better strategy of 75% and stubbornly refuse to adopt it, how can you count as an intelligent person? And if I can obtain a certain winning rate in what seems like a hopeless predicament, is that not an intelligent person? Are you saying that an extraordinarily intelligent person’s winning rate would be inferior to that of an idiot who can only grab 16 or 17 beans? Then what exactly is your definition of “intelligent”?
At the time I myself had posed the simplest such game-theoretic problem: http://epr.ycool.com/post.2471508.html. Other game-theoretic problems are in fact similar as well.
igeli
2008-11-25 18:32:20 [reply]
Of course, I also did not stop to think whether this sentence — “if he has a chance to live, then whether he finds out or not it is 50%, and whether he doesn’t find out or not it is 50%” — is true. :）
igeli
2008-11-25 17:59:48 [reply]
This is obviously forced — why would No. 5 choose 16 or 17? Of course it is because he has already calculated it, and this has nothing to do with whether or not he finally finds out how many remain. That also means that No. 5 has long since known his own fate. If he could threaten the others in advance, for example by declaring that he would 100% choose No. 16, he might well have a much greater expectation of survival; unfortunately, he cannot do that.
Gu Du
2008-11-25 17:01:57 [reply]
Ha, you missed one condition!
The condition says that each person may draw out the number of remaining green beans, but it does not say that each person “must” draw out the number of remaining green beans.
The fifth person’s strategy is that as long as there are enough green beans, he draws out 16 or 17 beans, and no longer cares how many beans remain. That is the most rational approach.
The fifth person has ample reason to support not finding out the number of beans remaining, and ample reason to support choosing certain specific numbers. That is the most rational and best strategy.
Just like that commander/sapper game against bomb/platoon leader. If the condition stipulates that B must look at the cards before choosing a play, then no matter what he would never choose the bomb, that suicidal move, so B can only play platoon leader, and then A can always play commander and B cannot escape death. But if the condition allows B to blindly draw a card without looking, and A knows that B can do this, then the result of the game will be that B has a 1/4 chance of survival.
In that problem the conditions are ambiguous, so the answer is also unclear. But the conditions in the green-bean-grabbing problem are clear — I can just close my eyes and draw! If closing my eyes gives me a higher survival rate than looking first and then drawing, then I will not waste the effort to insist on looking first; that is what rationality is!
It is irrational for the fifth person to go to the trouble of finding out the number of green beans remaining, because if he is doomed, then whether he finds out or not he dies; if he has a chance to live, then whether he finds out or not it is 50%. So finding out the number of green beans remaining is meaningless, and the fifth person will not do this. And the first person knows that the fifth person is rational.
igeli
2008-11-25 13:46:59 [reply]
I think the problem should be understood this way—that would be the rational interpretation:
1) Since No. 5 has no way to communicate the distribution of his own choices to the first four people, the first four should choose in the way most favorable to themselves.
2) Once the situation becomes 17, 16, 18, 15, No. 5’s so-called revenge strategy will no longer work, because he no longer has the best strategy for escaping death; at that point, the reason for his deliberately choosing 17 or 16 no longer exists—if you insist that he will then choose 17 or 16, that would no longer be rational, but merely petulance :), and the question we are discussing does not take emotional factors into account.
3) Since all four of the others understand this, their choices are stable, thereby causing No. 5’s death and securing the greatest benefit for themselves.
This conclusion should be correct. We can discuss other issues now 🙂
Gu Wu
2008-11-25 12:51:28 [reply]
No, the first four know that the fifth person will certainly adopt the optimal strategy; that is the premise of this problem. Just as the first three know that the fourth person will inevitably adopt the optimal strategy, the first two know that the third person will inevitably adopt the optimal strategy…… Under this premise, you can infer that the first four will end up with the outcome 17, 16, 18, 15. But your reasoning does not take the fifth person’s optimal strategy into account; you think the fifth person simply despairingly gives up all strategy. But that is not the case. The fifth person is also a participant in the game. The fifth person will adopt a strategy of choosing 16 or 17 with a very high probability, a kind of suicidal attack. This strategy is always optimal for the fifth person—if death is certain, then choosing any number leads to the same result; that is to say, choosing other numbers would not be any better than choosing 16 or 17, so he always has ample reason to carry out this strategy. The first person understands this, so he has no choice but to leave the fifth person a sliver of hope.
And the reason the fifth person’s strategy must necessarily be to choose 16 or 17 with a very high probability (perhaps 16 and 15? but there are always some numbers at the center of gravity) is not that he just randomly picked two numbers. If the fifth person chooses other numbers with some probability, the equilibrium state may be broken, and he will not be able to obtain a 50% survival rate. If he wants to have any chance of obtaining a 50% survival rate, the fifth person has no other way.
In short, in this game of ultra-clever people, it is possible for the first four to know the fifth person’s probability distribution. Although I have not proved that the fifth person’s 50% survival rate is the highest possible, he at least has such a survival rate.
All right, let this problem end here.
Of course, this certainly is not the final answer. Because there is still a problem here, namely that the fourth person does not necessarily seem willing to leave the fifth person a way out. When the first three choose 18, 15, 17, the fourth person’s survival rate is 50% whether he chooses 13 or 16, and he does not seem, like the fifth person, to have any additional reason to favor a specific choice even when the survival rates are equal; moreover, even under your original line of reasoning, the fourth person’s survival rate is exactly 50%, so his situation is rather subtle. So it seems this equilibrium is still unstable. But at any rate we have seen the hope of the fifth person’s survival. Perhaps the fifth person’s optimal strategy should also include options such as 13 and 20, using subtle pressure so that the fourth person has no choice but to step aside? In any case, even if we say that when the fourth person faces equal survival rates he will choose with equal probability, there is still reason for the fifth person to consistently carry out the suicidal strategy.
igeli
2008-11-25 12:00:12 [reply]
For the first four people, since they do not know the probability distribution of the fifth person, they can only make decisions based on their own subjective judgment—that is, their beliefs—and that way the outcome will be 17, 16, 18, 15, won’t it?
Gu Wu
2008-11-25 10:23:31 [reply]
The fifth person’s optimal strategy may not be complicated; perhaps it is simply to choose 16 or 17 with equal probability (so long as enough numbers remain available). Then the first two people both know the fifth person’s optimal strategy. If the first person chooses 16 or 17, his survival rate is less than 50%, but if he chooses 15 or 18, then he will have a survival rate greater than 50%, so the first person’s optimal strategy is to choose 15 or 18, and the second person then chooses 18 or 15 according to the first person’s result. Then the third person can choose 16 or 17, which yields a 50% survival rate; or he can choose 14 or 19, in which case the final survival rate is still 50%. The fourth person, depending on the third person’s choice, if the third person chooses 16 or 17, then the fourth person must choose 14 or 19; conversely, if the third person chooses 14 or 19, then the fourth person chooses 16 or 17. In this way, the fourth person also has a 50% survival rate. The fifth person also has a 50% survival rate. If the fifth person dies, then the first and second people both survive; if the fifth person does not die, then one person among the first two will die. That is to say, the survival rate of the first two people is 75%.
Oh right, the fourth person’s strategy cannot be to choose 14 or 19, because then the fifth person will be able to calculate whether the third person chose 16 or 17. So the fourth person should choose among numbers below 13 or 14, or 19 or 20; when the third person chooses 16, the fourth person chooses 14 or 20; when the third person chooses 17, the fourth person chooses 13 or 19. This prevents the fifth person from figuring out whether 16 or 17 has been taken. Thus the survival rates remain 75%, 75%, 50%, 50%, 50%. Aside from the fifth person’s strategy being cobbled together, the other four seem compelled to choose according to this scheme; otherwise it is hard to obtain a higher survival rate.
The third person must not adopt the strategy of taking away most of the mung beans and leaving only two behind. Because then what he gets would not be a 50% survival rate, but the “revenge” of the fourth person, who is certain to die. (If the third person leaves the fourth person no way out, the fourth person will certainly drag him down with him, so the third person must leave the fourth person a way out.)
Gu Wu
2008-11-25 10:07:07 [reply]
Anyway, these past two days this problem has been messing with my sleep, so I’m giving up on continuing to tinker with it…… let’s stop discussing it here……
igeli
2008-11-25 09:58:13 [reply]
If this equilibrium point cannot be found, then I suppose the choices will become chaotic. The problem-setter perhaps never thought this much through.
igeli
2008-11-25 09:55:11 [reply]
I think the discussion is becoming a bit engrossing 🙂
Suppose No. 5 announces a table matching each remaining number with his own probabilities of choice. Then he really might survive, but the workload seems perhaps too large; I can’t think of a good way to solve this problem. Can you think of a good way to give a definite answer? 🙂
Another not-yet-mature idea:
Announcing a lookup table would, I suppose, make it easy to find an equilibrium point; but what if there is in fact no stable equilibrium point? Since the prisoners cannot communicate with one another, that is to say, it would be impossible for No. 5 to artificially create an equilibrium point (by publishing a table).
Gu Wu
2008-11-25 04:44:10 [reply]
Let me pose another simple related problem and see:
Two people, A and B, are playing a game. A has two cards in hand: Commander and Engineer. B has Lieutenant, Company Commander, Regiment Commander, Battalion Commander, Brigade Commander, Division Commander, Army Commander, and Bomb (Engineer can disarm the Bomb, while Commander and the Bomb perish together). What are the best strategies for both sides?
If A plays Commander, then whatever B plays, he cannot escape death. So is A’s best strategy to play Commander, while B can only randomly grab a card from his hand? Of course not. B’s best strategy is to play Bomb with a high probability. In this way, once A plays Commander, there is a high chance that he will be blown up. And what A considers first and foremost is, naturally, his own survival, so he will not rashly play Commander. Of course B cannot play Bomb with 100% probability, because then A would simply always play Engineer. So the best strategy is the equilibrium point of the game between the two sides. Suppose A and B play Commander with probability x and Engineer with probability 1-x. B plays Bomb with probability y and other cards with probability 1-y. For A, when equilibrium is reached, we should have xy=(1-x)(1-y). And for B, he should strive to maximize the survival rate, namely (1-x)(1-y). The result gives x=y=1/2. In other words, B’s best strategy is to play Bomb with 50% probability, so that if A is a clever person, B will obtain a 25% survival rate.
The mung-bean-grabbing problem is much more complicated. But it may not be impossible to find a similar equilibrium point.
However, this problem is still a fake game-theory problem. As a game-theory problem, this problem is also unsolvable, because only A’s choice is balanced, while B’s cannot be balanced…… Of course, this problem in fact reflects a kind of paradox within it……
But in a more complex mung-bean-grabbing problem, it is quite possible for a genuine game-theoretic solution to emerge. The key is that the last person will never obediently play a passive role, but will use a suicidal attack to pressure the people in front into leaving a chance of life for the one at the end. In fact, in this game the first person does not enjoy much of an advantage over the last person. In fact, the first person’s advantage is merely that he moves first, but the later mover also has the advantage of moving later. The last person will choose after referring to the results of the first four, while for the first person, the choices of the latter four are still an uncertain probabilistic state.
Gu Wu
2008-11-25 03:45:57 [reply]
Ah right, right. As a game, why would the last person obediently resign himself to fate and choose randomly? In fact, in this problem, since all five people are absolutely intelligent people, it also means that the earlier people will be able to understand the optimal strategy of the last person. And the last person’s optimal strategy is absolutely not to pick any number from 1 to 34 at random, but rather, for example, to choose 16 or 17 with very high probability, or to choose 18 or 15 with very high probability…… This is not because he has any private grudge against the earlier people or anything of the sort, but because only by adopting such a strategy can he ensure the possibility of his own survival. The fifth person is a smart person, so he will certainly choose the strategy more likely to let him survive, and since the first person knows the fifth person’s strategy, he will not rashly choose 16 or 17, because then he will very likely be killed by the fifth person. So he must choose other numbers with a certain probability, and that will leave room for the fifth person to survive.
Therefore this game can indeed have an equilibrium point. That is, the first person chooses 16 or 17 with some probability, and also chooses 19 or 14 with some probability. And the last person chooses 16 or 17 with some probability, and chooses 18 or 15 with some probability, and so on.
In this way, for example, when the first person chooses 19, the second person will not necessarily choose 18, because the fifth person can still take a different strategy when the remaining number is not 34 but 30. That is, once 30 remain, it likely means that the first person chose 19 and the second person chose 18; then the fifth person’s strategy can be to choose 18 with a huge probability once 30 remain in an effort to kill the second person, and in that case the second person will not rashly choose 18. — The second person’s strategy is also a probabilistic distribution among several options such as 18 or 14. Thus, once the situation arises where the first person chooses 19, the second person chooses 14, and the fifth person chooses 16 or 17, the fifth person will be able to survive.
In short, the fifth person does have the possibility of survival, and the equilibrium point of the game may well be found.
Gu Wu
2008-11-24 23:29:46 [reply]
Hmm…… actually the second person’s situation seems to be the same as the first person’s. This involves a paradox: if one gives up one’s own ability to choose and entrusts the choice to something else—the first person entrusts it to a random-number generator, the second person entrusts it to the first person and a random-number generator, and oneself completely stops making choices—in other words, if the choices made by others would lead to his certain death, he would still follow them. If that were the case, he would obtain a higher survival rate. However, the problem is, if people are unwilling to give up the freedom of their final choice, then even if the first person sees the random-number generator indicate that he should choose 4 (and die), or the second person sees the first person choose 4, they will absolutely never obediently choose the doomed option. Then the game strategy is infeasible. In this way, the cost of reclaiming freedom is a lower survival rate……
Moreover, an exhaustive argument for this problem is still possible, namely to assume that each person chooses I beans with probability Xi%, then expand all the possible outcomes, and finally find the saddle point according to the solution method for game-theory problems…… but that seems far too massive..
But in any case, the game-theoretic scheme I mentioned is merely a disguised scheme; as a game, if equilibrium is eventually reached, then the winning probability of each option should be the same. But here obviously that cannot be reached. But the key is to prove it.
Gu Wu
2008-11-24 22:46:36 [reply]
Oh right, we can make it symmetric: the first person can choose 4 or 29 with the same tiny probability, as well as 15 or 18. The second person’s response is also symmetric. In this way, 16 and 17 can be occupied by the third person with equal probability, and what is left for the fifth person is always 34. Hmm.
Uh, the first person does not need to increase the probability of choosing 29; he only needs to increase the option of 18, while the second person increases the tiny possibility of 4+31~
Of course, in this problem, no matter whether the first person chooses 4 or 29 or the like, once it has become an established fact by the time it reaches the second person, it seems impossible for the second person to cooperate with it. But is it possible to force him to cooperate? I can’t find a proof that such a strategy is impossible. An exhaustive enumeration one by one won’t do, because the strategy here is not just a single choice, but a subtly distributed probabilistic scheme, and its possibilities are infinite.
Gu Wu
2008-11-24 22:33:54 [reply]
As for how to turn it into a game-theory problem, I can give an example: let’s do it according to this problem:
The first person adopts the following strategy: with 99.999……% probability he chooses 16, then with 0.00001% probability he chooses 4, and with 0.0001% probability he chooses 15; the second person then cooperates with the first person—when the first person chooses 4, he chooses 27 with 99% probability and 29 with 1% probability (if he chooses something else, the death rate is also extremely high, and he may have to cooperate, though I have not analyzed this carefully). When the first person chooses 15, the second person of course chooses 16.
If the first two choose 15+16 or 4+27, then the third and fourth will choose 17 and 18. And when the first two take 16+17 or 4+29, the third and fourth will choose 15 and 18 (I have not analyzed this carefully either).
The key comes at the last person: what is left for him is always 34 beans, but now his survival rate is no longer 0%, but has a glimmer of hope, though smaller than 0.00001%. If the first person chooses 4, then the last person will survive by choosing 5, 6, 7, and so on. Yet he will not choose 16 or 17, because even when the first person chooses 4, the second person has a 99% chance of choosing 27; that is to say, the probability that 16 and 17 will be occupied by someone among the first four is far higher than the probability that 5, 6, 7, and so on will be occupied, so the last person will be more inclined to choose 5, 6, 7, and so on, and almost impossible to choose 17.
That is to say, although for the first person choosing 4 beans is almost a suicidal act, if he only increases his probability of choosing 4 beans by 0.000000……1%, he can cause the fifth person to greatly reduce the probability of choosing 16 or 17. In other words, the first person’s survival rate thus rises from 33/34 to 99.9999……%!
Even if this strategy still has loopholes and is infeasible. The reason I bring it up is mainly to show a certain possibility—that through a complicated game, it may be possible to give the fifth person a sliver of hope, thereby reducing the chance of duplication with the fifth person and of being executed.
Even if I cannot produce such an example, if you have not proved that such an example necessarily does not exist, then your argument is not rigorous.
igeli
2008-11-24 21:36:34 [reply]
I think that kind of perfect strategy is impossible.
In fact, because there are so many possibilities, we had previously excluded the situation where No. 1 chooses 20 or above in qualitative terms, in which case he would very likely become the one with the highest probability. If you have time, you can also quantify them one by one 🙂 Of course, you can also calculate all the situations below 15. As for whether some possibilities should be weighted by probability—like you said, turning it into a game-theory problem—I did not think of any reason for doing so. No matter how large the proportion by which the optimal strategy of No. 1 is split off and degraded, it would lower No. 1’s overall survival probability, wouldn’t it? Can you think of a counterexample?
Gu Wu
2008-11-24 18:18:48 [reply]
Once probability is involved, a strategy problem can become a “game-theory problem”; that is to say, once probability is involved, the “best strategy” is not necessarily a definite choice, but may be a choice of a set of probabilities. For example: “a certain person’s best strategy is to choose A with 90% probability and B with 10% probability.”
Gu Wu
2008-11-24 18:08:33 [Reply]
I also believe the best strategy is 16 or 17 mung beans; the problem is that the argument is not rigorous enough. After all, when the first person chooses 16 or 17 mung beans, the survival rate is not 100% either. But could there be such a situation: because we have not proved that when the first person does not choose 16 or 17, the later people will also necessarily choose consecutive numbers, perhaps when the first person chooses A beans, the choices of the first four people will still leave gaps, so the fifth person would still have a sliver of hope; in that case the fifth person would not choose randomly, but would, say, have to gamble on B or C. And if A is neither the largest nor the smallest, and there is no danger of colliding with the fifth person, then the first person’s survival rate would be 100%.
Intuitively, such a perfect strategy does not seem very likely, but the solution you gave does not by itself prove that such a strategy does not exist.
igeli
2008-11-24 16:10:12 [Reply]
Got it. That number problem is almost a purely mathematical problem; there’s not much point in discussing it here anymore.
igeli
2008-11-24 15:15:14 [Reply]
In other words, although in the discussion we mention scheme 1, scheme 2, in fact there are also schemes 8, 9, 10…
But because those schemes are not optimal strategies, they will not be considered as possibilities, nor will they be weighted into the result.
igeli
2008-11-24 15:11:28 [Reply]
Interesting idea. However, since these people are all extremely smart, when 4 discovers that the front is not the optimal combination 17, 16, 18, he should be able to judge that someone must be playing tricks, and the most likely one is 3, because 17, 16 are optimal for 1 and 2. Then he may infer 3’s number, thereby putting 3 in the most unfavorable position. So 3 would not dare take the risk, otherwise he would be rather unreasonable.
Aside from the combination 17, 16, it should be impossible for such a situation to occur; otherwise they would not be smart (which contradicts the premise of the problem), or else someone would be playing tricks. That would involve too much risk, also unreasonable and not smart; and since it can be figured out by the people behind, it should all be ruled out.
I’ve had some thoughts about that problem with 100 numbers; I’ll write them out in a moment and discuss them with you 🙂
Gǔ Chù
2008-11-24 13:26:11 [Reply]
Your solution and answer are exactly the same as mine. But I have the feeling that it still doesn’t seem quite rigorous.
The key issue is: how can the last three people determine that the people before them chose consecutive numbers? Because they can only infer the total number taken by the first three people. If one simply assumes without further thought that the first three people must have chosen consecutive numbers, the fourth person may be fooled.
For example, if the first two people choose 17 and 16, and then the third person plays a dirty trick and chooses 21. In that case, would the fourth person mistakenly think that the first three chose 19, 18, 17? Then the fourth person would choose 16, and thus die in collision with the second person; meanwhile the third person, having chosen 21, survives, whereas if he had chosen 15 his survival probability would only be 19/34.
Going further, once the second person considers that the third person might play a dirty trick and kill him, would he also no longer dare to choose 16 so casually?……
igeli
2008-11-24 12:51:34 [Reply]
Postscript: several interesting special cases:
1) Person 1 chooses 100, he dies himself and saves the other 4;
2) Person 1 chooses 99, persons 1 and 2 both die, the other 3 live;
3) Person 1 chooses 98, person 2 dies, but he can choose either person 1 or 3 to take down with him.
igeli
2008-11-24 12:46:03 [Reply]
(Continuing from above, Part 3) I didn’t expect that it would take three chunks to finish 🙂
Scheme 3 (Person 1 chooses 17)
When person 1 chooses 17, if the sequence 17, 16, 15, 14 appears, then 5 has 38 possible choices
1 dies: 5 chooses 17, or a number smaller than 14, 14 kinds in total, survival probability 24/38
2 dies: 5 chooses 16, 1 kind, probability of survival 37/38
3 dies: 5 chooses 15, 1 kind, probability of survival 37/38
4 dies: 5 chooses 14, or a number larger than 17, 22 kinds in total, survival probability 16/38
For person 4, since 16/38<19/34 (see scheme 2, choosing 18), he will not choose 14, but instead choose 18, producing the arrangement 17, 16, 15, 18; of course person 3 knows that if the arrangement 17, 16, 15 appears, then person 4 will certainly not choose 14 but will choose 18, so person 3’s survival probability is only 17/34. Since 17/34<19/34, he will give up choosing 15, and seize 18 first, thereby forcing person 4 to choose only 15. In this way person 1 achieves his aim of forcing the others to sandwich him in the middle: ultimately the first four people’s choices are 17, 16, 18, 15
The survival probabilities of 1–5 are: 33/34, 33/34, 19/34, 17/34, 0%
Conclusion: if person 1 chooses 17 (or 16), and person 2 chooses 16 (or 17), the chance of survival is greatest, about 97%
igeli
2008-11-24 12:44:27 [Reply]
(Continuing above)
Scheme 1 (Person 1 chooses 19)
According to the reasoning above, when person 1 chooses 19, the arrangement 19, 18, 17, 16 will appear; at this point 5 has 30 possible choices:
1 dies = (5 chooses 19, or a number smaller than 16), 16 kinds in total, person 1’s survival probability 14/30 (obviously person 1 is at the greatest disadvantage)
2 dies = (5 chooses 18), 1 kind, person 2’s survival probability 29/30
3 dies = (5 chooses 17), 1 kind, person 3’s survival probability 29/30
4 dies = (5 chooses 16, or a number larger than 19), 12 kinds in total, person 4’s survival probability 18/30
Scheme 2 (Person 1 chooses 18)
When person 1 chooses 18, the arrangement 18, 17, 16, 15 will appear (no one will choose 19, because 14/30 would be the minimum), and at this point 5 has 34 possible choices:
1 dies: 5 chooses 18, or a number smaller than 15, 15 kinds in total, survival probability 19/34
2 dies: 5 chooses 17, 1 kind, survival probability 33/34
3 dies: 5 chooses 16, 1 kind, survival probability 33/34
4 dies: 5 chooses 15, or a number larger than 18, 17 kinds in total, survival probability 17/34; (obviously 17/34>14/30)
igeli
2008-11-24 12:40:38 [Reply]
Maybe it’s too long; I can only try splitting it into two parts:
My conclusion is the same, it’s my own answer, though I don’t know whether there are any holes in the reasoning, please advise 🙂
Obviously, people at either end (the largest number or the smallest number) have a higher probability of death. Person 1 chooses first, so he should not choose a number greater than 20; otherwise, he will leave person 2 a very good strategy: choose a number one less than his, or a slightly smaller number close to it (in special cases, person 2 can even guarantee that he won’t die; for example, if person 1 chooses 35, then person 2 chooses 34 or 33, because the remaining total is smaller than his choice, so person 2 will not die. If person 1 chooses 21, then person 2 chooses 20, which guarantees that someone later will be smaller than him), so person 2 would be in a very advantageous position, at least guaranteeing that he is neither the largest nor the smallest, while person 1 faces the danger of being the largest number. By the same reasoning, 2, 3, and 4 would not be the first to choose a number greater than 20; 20 would be the largest of the first four numbers. Person 1’s strategy is to choose a number that forces the people behind him to sandwich him in the middle; obviously, choosing 20 would not be wise for him.
Once person 1 has chosen a number, if possible person 2 will definitely choose a number adjacent to person 1’s; in this way he will not leave person 3 the excellent position of the middle number. From this, person 3 can infer what combination the first two numbers are, and for the same reason, he will also choose a number adjacent to those two; likewise, person 4 will also choose one of the ends of the above three consecutive numbers (these four people will not choose repeated numbers, which would mean suicide); thus it can be determined that the first four numbers are four consecutive numbers. No matter what number person 5 chooses, he will definitely die—if he chooses one end, then he is the largest or smallest; if he chooses the middle, he will duplicate one of 1, 2, 3, or 4. Since two people die every time, person 5 will choose a number at random, and one (and only one) person will be dragged down with him to die.
igeli
2008-11-24 12:39:09 [Reply]
Can’t post a comment; is there a problem with the website?
Gǔ Chù
2008-11-23 13:35:00 [Reply]
I worked it out and it seems the first person should grab 16 or 17
Please publish the answer~
igeli
2008-11-23 09:16:49 [Reply]
Yes, the later people only know how many beans the earlier people took in total.
But that 50% probability is obviously not the maximum, because in that case the survival probabilities of the 4th and 5th people are already 100%. 🙂
igeli
2008-11-23 09:10:48 [Reply]
The conditions for grabbing mung beans are fully specified.
I think that in the kind of desperate situation you mentioned, his choice should be random—because the problem does not say that he especially hates those people; it only says that they like killing people, and if he can make more people die with him, he certainly won’t let that chance slip.
Gǔ Chù
2008-11-22 21:06:59 [Reply]
At first I felt that it should be the second person who has the highest survival probability, but later I came up with a strategy for the first person: just grab 98 mung beans at once, and then the second person will either grab 2 or grab 1; either way it’s a dead end. If he grabs 2, he drags the first person down with him; if he grabs 1, he drags the third person down with him. If, in a situation where death is inevitable, the second person’s choice probabilities are each 50%, then by grabbing 98 beans the first person can guarantee himself a 50% survival rate. That probability seems rather high for the first person……
Gǔ Chù
2008-11-22 20:56:35 [Reply]
Are the conditions of the mung-bean-grabbing problem fully specified?
Is it the case that when grabbing, one can only know how many beans remain—that is, for example, when the third person grabs beans, he can know how many beans the first two people took in total, but not how many each of them took individually? Also, is this a probability problem? Then if someone is in a desperate situation (knowing that whatever number he grabs, he dies), with what probability will he make his choice? Does that mean each possible choice has equal probability?
Gǔ Chù
2008-11-22 20:12:29 [Reply]
Don’t talk about being extraordinary-minded or anything like that. I haven’t done olympiad math for four or five years; my thinking has become very sluggish, and I should have reacted much earlier. Besides, even a few years ago, my brain would have had no footing at all in front of that group of geniuses from the science track class……
Your problem seems a bit difficult, and now I no longer have the enthusiasm to spend sleepless hours working on math problems. I’ve thought for an hour and still have no idea; forget it..
igeli
2008-11-22 18:54:10 [Reply]
You really are extraordinarily sharp-minded. That thought—that the views of B and C differ—flashed through my mind, but I immediately discarded it. Now it seems very risky 🙂
I do have one problem I’ve never had a good way of solving; would you be willing to do it for amusement?
Suppose a natural number from 1 to 100 is randomly written on the foreheads of 100 people. They can see everyone else’s number, but not their own. What strategy should they adopt to ensure that at least one person can guess their own forehead number correctly? Before the numbers are written, they can discuss and make a plan; after the numbers are written, they can no longer reveal any other information to one another.
I haven’t found a good answer online.
Another amusing problem:
There are 5 prisoners, labeled 1 through 5, who take mung beans from a sack containing 100 mung beans in turn. It is stipulated that each person must take at least one bean (a prisoner who is passively assigned 0 is automatically spared from execution). Without duplicate numbers, the one who takes the most and the one who takes the least will be executed. They are not allowed to communicate, but when taking, they can feel how many beans remain. The question is: whose survival probability is greatest?
Hints:
1) They are all very smart people
2) Their principle is to preserve their own lives as much as possible, and then kill others
3) The 100 beans do not have to be fully divided
4) If duplicate numbers occur, the person who duplicates the maximum or minimum will be executed instead
Please communicate more; I’m very happy to discuss problems with you 🙂
Gǔ Chù
2008-11-22 18:43:08 [Reply]
Mm, it seems your method is correct.
Gǔ Chù
2008-11-22 18:39:31 [Reply]
Oh, so perhaps D can be divided all at once? Just slightly modify the method you mentioned before?
Gǔ Chù
2008-11-22 18:32:18 [Reply]
Your method looks fairly good, but the key is that the part cut off still has to be divided, and the remaining D also needs to be redistributed. In that case, it cannot be guaranteed that the division can be completed in a finite number of steps, even though the disagreement can indeed become smaller and smaller.
igeli
2008-11-22 18:23:16 [Reply]
Let me simplify the description a little:
When both B and C think that A is the largest, suppose B believes A>B>=C. Let B divide A into A- and D, so that B=A-
Now let C choose from A-, B, and C. If C does not choose A-, then B must choose A-, leaving one share for A.
The following statement about D does not need to be modified. How about it?What do you think?
2008-11-22 18:07:30
You really still don’t get it? The rule that B chooses A- applies only when C has chosen C. And of course A- is what B cut off.
It doesn’t matter whether he cut it evenly or not; as long as he thinks it is even, that’s enough. C will never say whether you cut too much or too little, because C chooses first.
I suppose I’ve talked you dizzy 
2008-11-22 18:00:11
Ha, you’re probably confused 🙂
When the third person thinks A>C>B, while the second person thinks A>B>C, we let the second person divide things so that A-=B. At that point, the choices left for the third person are A-, B, and C; he can choose whichever he likes. We do not guarantee that the third person will think A- is smaller than C—perhaps he will think it is larger—but he has the right to choose, and he will pick from A- and B, or even C, the share he believes is not too small.
The first sentence in your next comment is also wrong as a condition (“if a person is willing to choose one part, he must be sure that this part is at least one-third.”). That conclusion is only correct after the final allocation is complete; during the intermediate allocations, each person only cares that the total I get is not less than the other two people’s total, i.e. it has to be >= one-third of the total; you still have to wait for the next round of allocation.
How about it?
2008-11-22 17:36:17
And besides, in your “rule that the second person must choose A- (he thinks A-=B>C)”—who cut this A- down? If it is B who subtracts A to make it equal B, C may not necessarily agree. C might say that B cut away far too little: not only is it not equal to B at all (the smallest, in C’s view), it is still larger than C! You have no way to resolve the disagreement. If it is C who does the cutting, B of course may also disagree: too much was cut away!
2008-11-22 17:27:35 [reply]
You need to pay attention that, under your conditions, if a person is willing to choose a certain portion, he must be certain that this portion is no less than one-third. Because if he knows that what he gets is less than one-third, then he will think that at least one of the other two people got more than one-third—that is, more than he did.
So if the third person thinks A>C>B and moreover A>1/3>C>B, then he will absolutely not be willing to choose C, because it is less than 1/3.
In short, you must solve a case like this: after person A divides the peach juice into A, B, and C, persons B and C both think A is the largest, both think that the two pieces B and C are less than 1/3, and they do not agree on which is larger between B and C.
Gu Hu
2008-11-22 17:18:34 [reply]
How can you ensure that the third person thinks A- is smaller than C?
igeli
2008-11-22 17:15:12 [reply]
Haha, you really are remarkable!
But this does not in the least affect the distribution. The third person can choose C (the smallest share, in the second person’s view), but the rule is that the second person must choose A- (which he thinks is A-=B>C), thus leaving B to the first person; after that, the principle of distribution is the same as above.
Gu Hu
2008-11-22 13:34:15 [reply]
Although I did not look at it carefully, your distribution seems not to work. The key point is that when the other two both think A is the largest, they may not agree on which is larger, B or C; that is to say, one must consider the situation where the second person thinks A>B>C, while the third thinks A>C>B. In that case, if the third person can only choose between A- and B, he may conclude that the first person, who gets C, has more than he does.
igeli
2008-11-22 13:20:46 Anonymous 58.31.177.132 [reply]
What a coincidence, I was just about to explain that the solution for n people has the same problem, and you have already discovered it 🙂
Let me explain the peach-juice problem for 3 people:
Suppose the first person divides it into three portions A, B, and C in a way he considers equal; now let the other two choose, and two situations arise:
1. One chooses A and the other chooses B—very good, C goes to the first person, and everyone stays in peace.
2. The two people both choose A, meaning they think A>B>=C
Then let the second person pour off a small part of A into a container D, and call the remainder A-. The second person thinks A-=B
Now let the third person choose between A- and B; the one left over goes to the second person, C goes to the first person, and none of the three thinks anyone has more than he does.
Now, let the person who took B (suppose it is the second person; if it is the third person, the situation is similar) divide D into three equal parts, with the third person choosing first, then the first person, and finally the second person. In this way, none of the three thinks the others got more than he did:
The first person thinks that even if the third person (A-) took all of D, it would only be the same as what he has (C=D+A-); now he has only taken part of it, so his total is still less than my C, and I can choose the larger of the remaining two portions, so I will not have less than the second person.
The second person thinks that his B is no less than A- and C; the small portion he finally takes is the same as the other two people’s, so no one has more than he does.
The third person thinks that his A- is no less than B and C, and since he gets first choice among the final three portions, no one will have more than he does
2008-11-22 01:56:30
In addition, this problem was then generalized to the case of n people: see http://epr.ycool.com/post.2471356.html . However, even according to that general solution, it absolutely cannot satisfy your additional condition that “each person does not want the others to get more than he does”; the advantage of that general solution is that each person ends up with precisely the portion that he himself thinks is 1/n—not more, not less. Yet clearly there is no guarantee that the others will also each get exactly the same amount, so in the end it will certainly be discovered that someone has more. I really cannot see how this problem could still have a solution once your condition is added; please instruct me!
2008-11-22 01:43:33
Oh, sorry. It seems it really was my problem (waking suddenly from a dream…). The problem was set too long ago, and I forgot to check it carefully. The question should have specified that what each person ultimately cares about is only that the share he himself receives is fair. But if we do not add this stipulation, and instead assume, as you said, that “each person does not want the others to get more than he does,” then what way is there to divide the peach juice?
2008-11-21 14:21:03 Anonymous 221.219.245.20
I happened to come across your blog; it’s really nice, and I especially like those fun puzzles. Haha, at last I found an error:
Peach-juice division problem: “If C thinks the largest is B+ or C+, then let us suppose C thinks the largest is B+, and then divide C+ to A and A- to B, and that will do.” That won’t work. For example: B divides the peach juice into 1/8, 4/8, and 3/8 (the numbers are exaggerated for clarity of example), and when 3/8 is given to A, A will not be satisfied (assuming that each person does not want the others to get more than he does). I didn’t think further beyond that.
I do happen to have another good way to divide this peach juice
Translated from the Chinese original with AI assistance. The original text is authoritative.
Leave a Reply