A Collection of Questions on the Mung Bean Distribution Problem and a Summary

After the previous “summary collection” was posted, the argument still continued, but now I’ve made up my mind to cut off the discussion! Professor Wu’s assignment has already been handed out, and other assignments may be close at hand as well, so let me focus on my current affairs for the time being~

This discussion began with a problem provided by the user igeli in https://yilinhut.net/2006/08/05/498.html. Later, because I forcibly closed the comments on that article, the discussion was moved under another unrelated article. I’ve now deleted those comments, but the full content is preserved in this collection.

I’ve said before that my interest in philosophy really stems from mathematics, and that is indeed true. But the advantage of a mathematical problem should be this: if both the problem and the solution are sufficiently rigorous, then as a rule there can be no argument. The reason this problem has been so contentious is mainly that the problem itself—especially definitions like that of “smart people”—contains fundamental ambiguities. Of course, the subjective reason for the endless wrangling is partly that my opponent demanded too much of me; in fact, I merely wanted to point out that the other side’s proof was not rigorous, and had never intended to offer a rigorous proof myself. Another reason is that I simply cannot suppress my habit and desire to answer whenever I’m asked. But in the end I have at last cut it off myself. Let this discussion come to an end for now. From this point on I’m going to make myself into a fool—sometimes deliberately making oneself into a fool is the smartest strategy, if that can in fact be done……

Besides me and igeli, I’m afraid no other reader will have much interest in reading this collection. But some of the issues involved may nevertheless contain deeper significance, and can be further developed philosophically or logically; if there is an opportunity in the future, I may still be able to make use of it.

2008-11-29 0:55

igeli 2008-11-28 23:47:37 [reply]
Oh, the greatest probability of hitting and dying is not 1-a.
But this can be compensated for as follows:
Let’s see whether No. 4 can choose a number outside these four numbers!
If No. 4 chooses the number represented by a, his survival probability is 1-a;
if he chooses a number outside the four numbers, then he only has to wait for either No. 5 or one of Nos. 1–3 to collide and die, and the maximum probability of that collision is no more than b.
Since 1-a>=b
and since choosing a number outside can also potentially increase his own death rate, No. 4 will definitely not choose a number outside the four numbers, and can only choose a. (The rest is the same as before.)
How about it this time?
(You should have pointed out this oversight to me.)
Are there any other mistakes?

Gu Xu 2008-11-28 22:39:51 [reply]
Your argument makes an obvious mistake from the very beginning. And I have long since hinted at this many times.

But, hm hm hm! I’m restraining myself! I’m restraining myself! I won’t say it anymore! Work it out yourself! If you can’t think of it, then just suppose I’m deliberately being mysterious! I really don’t want to keep tangling over this anymore.

Comments here will be deleted; the exchange record will be preserved in the “collection.” I’m glad to have exchanged ideas with you, and you’re welcome to discuss other questions in the future, but I absolutely will not discuss mathematics again recently!

igeli 2008-11-28 22:22:30 [reply]
I actually found very many loopholes in your argument and calculations :), but I really didn’t have the patience to write them out—and I know that I, too, would have many loopholes, like that game-theoretic calculation last time—what a pity, though, that when you corrected things you also made a mistake :), following your line of thought at the time, No. 5’s survival rate was 0% rather than 1%; and moreover, if we follow your other line of thought, No. 4 should have a way to make way for No. 5, right? Then No. 5 would have achieved his ideal (I haven’t verified any of these thoughts at all; I was too lazy to look at those numbers)

I’ve suddenly had an idea now, and it seems possible to prove that No. 5 does not in fact have the kind of life-risking strategy you mentioned. This requires the following two points of consensus:
1) If No. 5 carries out the so-called life-risking strategy, but the final result still does not allow him to obtain a higher survival probability, then his so-called life-risking strategy does not stand and should be abandoned.
2) The probability distribution No. 5 gives for choosing the four numbers 15, 16, 17, 18 is a>=b>=c>=d, (a+b+c+d=1). Why doesn’t No. 5 choose numbers less than 15 and greater than 18? Because those numbers are death numbers; choosing them will not put pressure on Nos. 1–4. Of course, No. 5 chooses last; if there is any other chance for him to survive, he should not let it slip away.
Now let’s look at how Nos. 1–4 choose. It seems very simple: No. 1 will definitely choose d, 100% of the time, because his chance of survival is the greatest = 1-d.
No. 2 will 100% choose c, the second-highest chance is 1-c.
No. 3 will 100% choose b, survival chance 1-d.
No. 4 will 100% choose a, survival chance 1-a.
Nos. 1–4 will all not choose numbers outside these four numbers, because then the only survival chance would be one thing: wait for No. 5 and someone else to collide and die, and the maximum probability of that collision is only 1-a. Not only that, but choosing a number outside can instead possibly increase one’s own death rate, so the result above is inevitable.
What if a=1?
When a=1, it seems No. 4 has no reason to definitely choose the number represented by a; his situation is the same as the most original situation of No. 5, so he also has to begin his life-risking strategy just like No. 5 does—is this going to be an infinite loop? Of course not, events occur in time order: No. 1 must choose first, and the four numbers he now has to choose from have all been occupied by the life-risking parties, but No. 1 still will not choose a number outside those four numbers; that would of course be suicide. So he first carries out his own life-risking plan. One can infer that afterwards, No. 5’s life cannot be preserved.
If No. 5 still gains nothing from his own life-risking plan, then according to 1), we regard his life-risking plan as invalid.
The above is only a sudden thought; I haven’t thought it through carefully. Do they really have to get tangled up with these four numbers 15, 16, 17, 18? Couldn’t they be some other numbers? At that point it seems to have nothing to do with their original probability anymore.
What do you think? Can this argument be made more rigorous?

Gu Xu 2008-11-27 23:05:40 [reply]
If we make a slight adjustment to the original problem, changing the total number of green beans from 100 to 101, then according to your original line of thought, No. 4’s survival rate becomes 17/35, which is less than 50%. But if No. 5’s coercive strategy succeeds, No. 4’s survival rate is still 50%. In that case, No. 4 would have ample reason to cooperate with No. 5’s strategy, right? Yet I’m afraid your original line of thought would never have expected such a difference between 100 and 101!

What I am trying to explain is that No. 5 may possibly have some coercive strategy. If you cannot prove once and for all that all coercive strategies are impossible, then your argument is not rigorous.

Oh, and in the case of 101 beans, there is still the question, in a one-shot game, of whether a strategy can be carried through after the first three people have already taken theirs and the matter has become a settled fact. Forget I said that~~

(However, in the case of 101 beans, if this is an infinitely repeated gambling game, then there is no problem with No. 4 cooperating with No. 5’s strategy.)

Gu Xu 2008-11-27 22:04:42 [reply]
From beginning to end I have acknowledged that my plan contains many ambiguities, but the problem is that your criticism has not hit the main point.

The key ambiguity in my plan is still the one I mentioned at the very beginning: can No. 5 “refuse to check the number of remaining green beans” as part of his optimal strategy? It seems you have not given this enough attention, so you did not understand what I just said. What I just said—that “there is therefore no reason for No. 5 to change the original strategy”—means that No. 5 has no reason at all to check the number of remaining beans, because under any settled fact that might be left to No. 5, checking the remaining number of beans will not increase his survival rate. So from the very beginning when I proposed this “laughable plan,” the optimal strategy I was proposing for No. 5 has always been “regardless of the situation, just choose 16 or 17.” Please do not forget this.

What makes me feel something suspicious is that since No. 4 knows that No. 5’s optimal strategy is not to check the number of beans, then if No. 4 chooses 1 bean, 2 beans, and so on, the survival rate is also 50%. Then should he also have the possibility of choosing them? And if No. 5 knows that No. 4 has a relatively large possibility of choosing a lower number, then would No. 5 abandon his original strategy and choose to check the number of remaining beans? But if that happens, the equilibrium of the game will be broken again……

And if the original problem is not a one-time execution event but an infinitely repeated gambling game, then perhaps this instability can be eliminated. Because there are sufficient reasons to support No. 5’s insistence on choosing 16 or 17 even when he knows he is doomed to lose, since his insistence will affect the considerations of the first two people in the later infinitely repeated gambling rounds. But the problem here is that there is only one gamble, and after the choices of the first few people have become settled facts, why can’t No. 5 take a look? This is precisely the greatest difficulty in my proposal, and this difficulty is one I made explicit from the very beginning.

My plan is indeed a little laughable, but if that is the case, then the person who keeps arguing endlessly over such a laughable plan is even more laughable. I did not put forward this plan with any special seriousness; I simply presented it to show that this problem is not so simple—even if this plan does not stand, how can you prove that no other plan can stand? You have not proved it, so your plan is not rigorous. I merely hope that you will admit that your plan is not rigorous. As for my plan, I admitted from the very beginning that it was not rigorous.

igeli 2008-11-27 20:28:10 [reply]
First you proposed a life-risking plan for No. 5 to choose 16 and 17, making Nos. 1 and 2 yield to him; then you proposed asking No. 4 to consider things for him and devise a plan that leaves himself a way out—these two plans are really too laughable. The person who can propose such plans is truly not of sound mind 🙂
Don’t be angry!

igeli 2008-11-27 20:22:33 [reply]
No. 4 choosing 17 directly carries no risk at all; he directly sends No. 5 to his death, while himself having a 50% chance of survival. How could he possibly still think of No. 5 and devise a smokescreen to rescue No. 5—you really think that is just too funny.

igeli 2008-11-27 20:09:31 [reply]
I think you’re the one who’s not of sound mind—I originally didn’t want to write it in such detail because I thought you’d understand at once:
Since No. 5 clearly knows No. 4’s strategy, when the remaining 31 beans are drawn, he knows that one of only two situations must have occurred: either it is 15, 18, 17, 19; or it is 15, 18, 16, 20. If it is the former, then he can only survive by choosing 16; if it is the latter, then by choosing 17 or 19 he can survive. Since he doesn’t know which situation has occurred, he chooses one from among 16, 17, and 19, any of which might let him survive. None of these three numbers is superior to the others, and none is worse than the others, so you have no reason to require him to choose any particular one, nor any reason to forbid any particular one, because the survival rate offered to No. 5 by each is the same.
But it’s different for No. 4: his survival rate has already gone down, so he definitely will not choose this way!
Right, you said No. 5 will not change his strategy—No. 5’s strategy is of course determined according to the situation of the first four people. At the very least, No. 4 must think this way; would he joke with his own life? What reason do you have to convince No. 4 that he can safely take the risk? You could even ask: what reason do you have to have No. 4 cooperate with you when he gets no benefit at all?

Gu Xu 2008-11-27 17:45:30 [reply]
I’m not arguing with you anymore; you’re already not of sound mind…………

How many times have I said it!?！？！？ As No. 5, even if he checks the total number of remaining green beans, he still has no way to judge whether the earlier people chose 15, 18, 16, 20 or 15, 18, 17, 19!! Because the totals of these two situations are equal. And when the first two people have chosen 15 and 18, No. 3 choosing 16 or 17 is equivalent; only No. 4 can actually determine No. 3’s choice by checking, but No. 5 cannot infer it, and Nos. 4 and 5 cannot communicate in the middle, so No. 5 cannot be certain whether 19 has in fact been freed up! From No. 5’s point of view, the probability that 19 has been freed up is only one half, the same as the probability that 16 or 17 has been freed up, so No. 5 has no reason to change his original strategy. No. 4 knows that No. 5 has no reason to change his strategy, so he knows that choosing 20 still leaves him with a 50% survival rate.

OK?

All right, let’s stop arguing. Anyway, I never wanted to prove that my answer is correct; if you want to prove it, go ponder it slowly yourself~~

igeli 2008-11-27 12:55:44 [reply]
The key point is that once No. 4 leaves an opening, he raises his own death rate, and he would absolutely never take such a risk.

igeli 2008-11-27 12:48:49 [reply]
Huh? How could No. 4 choose that way? If he does, his survival rate will drop to 33%; how could he agree? He will definitely choose the 16 that No. 3 didn’t choose; it is definitely better to get a 50% chance of staying alive!
For example, in the situation where the numbers are 15, 18, 16, 20, No. 5 knows that if he chooses 16 he will die, but if he chooses 17 or 19 he can live, so of course he would not give up the possibility of choosing 19. Even if that doesn’t increase his overall survival rate, No. 4’s survival rate would go down, and No. 4 certainly wouldn’t accept that!
Do you understand?

Gu Xu 2008-11-27 11:06:58 [reply]
Of course I considered that, and I already mentioned it in my earlier formulation; don’t make me keep repeating myself, okay? I’ve also repeatedly mentioned that No. 4’s situation is very delicate.

When No. 3 chooses 16, No. 4 chooses 14 or 20; when No. 3 chooses 17, No. 4 chooses 13 or 19. In this way, even if No. 5 checks the number of remaining beans, he still cannot determine whether the situation in front was 16-14 or 17-13. So if he chooses 14, his survival rate is still 50%. With the same 50% survival rate, why must No. 4 choose 17 rather than 14 or 20? Therefore, we still think No. 4 may choose not to pick 17. Of course, I also mentioned that if No. 4 rigidly insists on choosing 16 or 17, then he can make No. 5’s strategy fail. But what good does it do to make No. 5’s strategy fail? The benefit of No. 5 forcing No. 1’s strategy to fail is a great increase in survival rate. But No. 4 is 50% survival in either case; what reason does he have to go out of his way to oppose No. 5?

igeli 2008-11-27 05:41:00 [reply]
Right, I never actually bothered to verify your calculation before. Looking back now, there is a huge loophole in your 50%-each scheme for No. 5 choosing 16 or 17:
It should be:
1. No. 1 must choose 18 (or 15)
2. No. 2 must choose the remaining 15 (18)
3. No. 3 must choose one of 16 and 17, with a 50% chance.
4. No. 4 must choose the one left over from 16 and 17, with a 50% chance. [No. 4 will not, as you said, choose a number outside these four numbers—if he chooses 14 or 19, No. 5 can figure out which number No. 3 chose; if he chooses above 19 or below 14, then as long as No. 5 chooses 19 or 14 he will live 100% (he finally no longer needs to choose with his eyes closed!), and No. 4 will have to die 100%.]
Since No. 5 chooses 16 or 17 with 50%, his survival rate is 0%
Understand?

Gu Xu 2008-11-26 23:02:01 [reply]
2008-11-26 19:29:02 [reply]
I don’t want to study the problem in more detail; I just want to tell you that this question is not simple. I cannot agree with you saying that the problem is already so clear and so on. The problem is not as clear and simple as you say. That is all I want to say.

—If you agree with this point, then the discussion ends here~

igeli 2008-11-26 21:53:47 [reply]
There are at least two situations that would leave this statement without support:
1) The paths leading to all of No. 5’s so-called optimal strategies are not unique; I haven’t thought of a good way to prove this, but you have not proved even one contrary case.
2) More frighteningly, even if such a unique path really exists, it still cannot be certain that an infinite loop will not occur—for example, No. 5 adopts some strategy to force No. 4 to yield, then No. 4 in turn forces No. 3…… In the end, No. 1 would still have to choose the original plan, and in turn threaten No. 5.

Gu Xu
2008-11-26 21:25:05 [reply]
How would I know! That’s why I did not assert that 16 and 17 are exactly the optimal strategy. But the key is that it may be larger, it may be smaller, but it will not be everywhere equal with no difference whatsoever, so the fifth person’s optimal strategy exists.

Because in each situation the fifth person has a survival rate, and the survival rate lies between 0 and 100%. Now we know that there is at least one situation (for instance, steadfastly grabbing only one bean) in which No. 5’s survival rate is 0, and also at least one situation (for instance, choosing 16 or 17 with equal probability) in which No. 5’s survival rate is not 0 (let’s assume it is x). Then among the countless other strategies, either all of them lie between 0 and x, or some are above x. In any case, let the highest be y. y lies between x and 100%. It will not be an open interval, because if the maximum does not exist but only a limit does, then let that limit be the maximum.

If the strategies that reach y or approach y are more than one, then all of those should be removed. Because if the optimal strategies are equivalent, then the earlier people cannot tell which one No. 5 will choose. Next, consider the remaining maximum y2 after removing y; if y2 is also repeated, then look at the third-highest y3, and so on. In the end, if there is an yn that corresponds to only one unique strategy exactly once (for example, choosing 16 or 17 with equal probability), then that strategy is No. 5’s best strategy.

In considering the survival rate for No. 5 when he chooses strategy A, we set No. 5 aside and look at the game among the remaining four people, assuming that all four of them understand No. 5’s strategy. Then we see how these four play; when their game reaches equilibrium, No. 5’s survival rate is the value corresponding to strategy A.

To calculate the game among the first four under scenario A, we can also start from No. 4 and consider it separately: calculate No. 4’s survival rate on the premise that all the strategies he might possibly adopt are taken into account. This is similar to the above.

To calculate the game among the remaining three when No. 5 chooses strategy A and No. 4 chooses strategy B, there is still a similar method……

Finally, one can derive the best strategy for No. 1 under the situation where “No. 5 adopts strategy p1, No. 4 adopts strategy q1, No. 3 adopts strategy r1, No. 2 adopts strategy s1,” and then everything becomes clear at a glance. Suppose that under the “p1q1r1s1” situation, No. 1’s best strategy is t1; at this point, No. 2’s survival rate is Xs1. Under the “p1q1r1” situation, let all of No. 2’s strategies be the set S, and let each strategy s correspond to an Xsi. Among all the Xs, excluding those values corresponding to multiple s’s, if the largest Xs2 corresponds to strategy s2, then s2 is No. 2’s best strategy under the “p1q1r1” situation. Then suppose that No. 1’s best strategy at this point is t2. Then we calculate No. 3’s survival rate under the “p1q1r1s2t2” situation, and this survival rate is No. 3’s survival rate under the “p1q1r1” situation, denoted Xr1. Among all of No. 3’s Xri, find the strategy r2 corresponding to the largest Xr2; then this strategy is No. 3’s best strategy under the “p1q1” situation. Suppose that under the “p1q1r2” situation, No. 2’s and No. 1’s best strategies are s3 and t3 respectively. Then calculate No. 4’s survival rate under the “p1q1r2s3t3” situation; this survival rate is No. 4’s survival rate under the “p1q1” situation, denoted Xq1. Find, among all Xqi, the largest value Xq2 corresponding to some qi, and the corresponding strategy q2; then q2 is No. 4’s best strategy under the “p1” situation…… Finally, run through it once more, and you find No. 5’s best strategy in all situations!

igeli
2008-11-26 20:20:30 [reply]
So in that case, would the result be smaller than if he chose 16 or 17?

古雴
2008-11-26 20:08:41 [reply]
Right, but the issue is: when No. 4 sacrifices himself, what survival rate can No. 5 get? If forcing No. 4 to sacrifice himself gives No. 5 a higher survival rate, then No. 5 will force him. But the problem is that if even by forcing No. 4 to sacrifice himself No. 5 still gets no benefit, then No. 5 will not choose the strategy of 100% choosing 18.

The strategies of all parties will eventually tend toward stability. Just like in gambling-type game theory problems.

igeli
2008-11-26 19:58:57 [reply]
Maybe you didn’t understand what I meant — each person’s survival probability changes with different strategies. For example, when No. 5 100% chooses the plan of 18, then for No. 4, he no longer has the survival probability you said he already had, namely 50%… Maybe even a 1% survival rate is enough to make him sacrifice himself.

古雴
2008-11-26 19:53:22 [reply]
So I hope you’ll calm down and think it over before speaking, and don’t make me repeat what I’ve already said over and over. Of course No. 3 and No. 4 may have sacrifice-themselves strategies, but right now their survival rate is already 50%. Can any sacrifice-themselves strategy make their survival rate rise a little? If not, then it won’t be considered. For the first four people, their survival rates are basically no less than 50%, while any survival rate gained by a sacrifice-themselves strategy is basically no more than 50%; therefore they won’t consider it. Only the fifth person has reason to consider a sacrifice-themselves strategy. And at present, under his strategy, the survival rates of the earlier people are all above 50%; then what else do the earlier people have to choose? The reason we say No. 5 has no choice but to adopt a sacrifice-themselves strategy is because if he does not choose it, his survival rate is 0, but if he does choose it, it increases, so he will choose it. The others have no room for further improvement, so they will not change any more, and the game reaches “equilibrium” in this sense.

A game reaching equilibrium means: everyone’s strategy is optimal; that is to say, if I make any adjustment to my strategy, others can make some corresponding adjustment so that their own winning probability increases and my winning probability does not increase. In that case I will not make any adjustment, and the strategy becomes stable.

A game that has not reached equilibrium means: there are some people who can make certain adjustments to their strategies, causing others—if they want to preserve their winning probability as much as possible—to be unable to adopt any improved strategy that would keep my winning probability from increasing. In other words, so long as the others first think in terms of their own winning probability, even if they know my new strategy, they still cannot stop me from using that strategy to improve my own winning probability.

igeli
2008-11-26 19:41:21 [reply]
The calculation example I just gave was wrong, but that doesn’t mean the idea itself is wrong. I can give a correct example that proves this idea — what I mean is, according to your logic that No. 5 must, eyes shut, choose that plan and force others to yield, No. 5 could have a plan that neither tangles with Nos. 16 and 17 nor has the greater survival rate you claimed; then your conclusion would be wrong.
Your judgment is that No. 5 has an optimal plan, while I think he does not. Otherwise it would follow that No. 4 also has a sacrifice-themselves plan, as do No. 3, No. 2, and No. 1, forming an infinite loop.

古雴
2008-11-26 19:29:02 [reply]
I don’t want to study the question in greater detail. I just want to tell you that this problem is not simple. I can’t agree with what you said about the issue being so clear; the problem is not as clear and simple as you say. That is all I want to say.

古雴
2008-11-26 19:25:07 [reply]
It seems that if one 100% chooses 16, then one will almost certainly not die (at this point No. 4 is playing the role of a random-number generator). However, the problem is that 100% choosing 17 is completely equivalent! Only then does what you said arise: when the earlier people cannot judge No. 5’s strategy, they can only assume that he adopts one of the options with average probability.

igeli
2008-11-26 19:22:26 [reply]
Or, more interestingly, if he 100% chooses 18, does the problem become that No. 4 is the one threatening the people ahead of him?

古雴
2008-11-26 19:21:06 [reply]
I have never tried to find the final answer to this problem, nor have I tried to prove that it exists. I only said that it very likely exists; I believe it exists, and I even tend to believe it is exactly 16 or 17. But I never intended to provide a proof. The problem itself was posed with so much ambiguity; what I originally wanted to emphasize was precisely this point.

igeli
2008-11-26 19:18:43 [reply]
By the way, if we modify No. 5’s plan and let him 100% choose 16, what do you say should be done?

igeli
2008-11-26 19:13:16 [reply]
Yes, that was a huge mistake in my calculation. But you have to prove that No. 5 has an optimal strategy, and that it is unique. How do you prove that?

古雴 发表于 2008-11-26 18:56:44
http://epr.ycool.com/post.3124188.html
Let me give one final overall summary: making this problem complicated is my responsibility. In fact, if the fifth person’s optimal strategy just happens to be choosing 16 or 17, then my solution does not involve anything more than what was used in the original 33/34 solution; the way of thinking and the understanding of the problem are the same. It is just that the reasoning in 33/34 is wrong because it did not consider the fifth person’s optimal strategy.
In fact, although the five people take turns grabbing the beans, the game is played simultaneously. When the problem is given, each person’s optimal strategy is determined at the same time.
Since the fifth person’s choice ultimately determines who lives and who dies, examining the probabilities of the fifth person’s choices is of course the breakthrough point for solving the problem. The reasoning in 33/34 is the same in this respect, except that that reasoning did not consider the fifth person’s strategy, and instead simply treated the fifth person as a random-number generator.
The proper line of reasoning should start with the fifth person. Under what circumstances can the fifth person survive? Of course, only two: one is that there is a gap in the first four people’s choices that can be exploited; the other is that two of the first four people make the same choice. So if he wants to survive, he can only strive to make his own strategy bring about these two kinds of situations.
//—Of course the fifth person can cause the earlier people to arrive at some choice, just as the strategies chosen by the earlier people will also cause the later people to arrive at some choice. Because, let me repeat once more: the game itself has no order of precedence; everyone’s strategy is determined simultaneously and affects others simultaneously. For example, in the reasoning of 33/34, why is the fifth person forced to choose arbitrarily? According to that line of reasoning, he is not forced to give up hope because of the fact that what he gets in hand is 34 green beans; rather, it is the optimal strategies of the earlier people that cause him to lose hope. In other words, the fifth person does not lose hope only after the first four have all finished choosing; rather, the outcome is determined from the very beginning—the influence among the five participants is synchronic, without temporal order. Therefore, of course, just as the first four people’s strategies affect the fifth person’s choice, the fifth person’s strategy simultaneously affects the first four people’s choices. And for any person, what is called the optimal strategy is precisely the one that, through its influence on the other four, maximizes his own survival rate.
Therefore, I repeat again and again: the choice of optimal strategy itself has no temporal order; the five people’s optimal strategies are determined simultaneously. And to first infer whose strategy, then infer whose strategy, is merely an order within the reasoning, not a necessary order.
So we may as well start with the fifth person first, infer his optimal strategy, and then infer the strategies of the first four on that basis. In fact, the reasoning in 33/34 did exactly that too, except that it fell into circular reasoning — it inferred the strategies of the first four by assuming the fifth person’s strategy, and then inferred the fifth person’s strategy based on the strategies of the first four. Of course, this argument is wrong. —//
And my reasoning truly starts with the fifth person. If your mind still cannot turn over this matter, then let us slightly modify the problem first:
Still five people grab 100 green beans. But now the second person cannot know how many green beans the first person has taken, and the later people can only know how many beans in total have been taken starting from the second person, unless the number of green beans he wants to take exceeds the remaining total; in that case, the beans already taken by the first person are taken back to make up the difference. Then what is the optimal strategy for the first person to grab? What is the survival rate?
In fact, the position of the first person in this modified problem is exactly the same as the position of the fifth person in the original problem, who gave up knowing the number of remaining green beans.
And why does the first person here focus on choosing 16 or 17? The reason is similar to the original first person’s considerations — because only 16 or 17 occupy some kind of “middle” position; that is to say, only by choosing 16 and 17 with extremely high probability can one force the later people to have to take 15 and 18, respectively. In other words, only by trying as hard as possible to occupy 16 or 17 can the first mover ensure the greatest probability of not becoming either the largest or the smallest.
And the previous fifth person, or the present first person, cannot expect others to collide and hand him a free ride; therefore only by trying as hard as possible to seize the middle position can he obtain a higher survival rate. For example, his optimal strategy obviously would not be to choose a number between 2 and 3; if he did, then no matter how his strategy affected the later people, the later people would not be foolish enough to choose 1. Similarly, he would not choose 33 all at once, because no matter how his strategy affected the later people, no one would then choose 34. Only the strategy of choosing 16 or 17 can not only influence others, but also force others to take the larger and smaller ones respectively, leaving him in the middle.
And because 16 and 17 are equivalent in the sense of occupying the middle position, the second person now has no way to guess whether the first person will choose 16 or 17, so he can only choose 15 or 18. And although 15 and 18, compared with 16 and 17, have a greater chance of becoming the largest or the smallest, he can nonetheless expect a free ride because of collisions among the others. Taking both considerations into account, the survival rate of choosing 18 or 15 is still higher than 50%; therefore the second and third people now will not risk colliding at 50% with the first person by choosing 16 or 17, but will choose 18 or 15 instead. In that way, they may be squeezed into the middle and survive, they may also gain a free ride because others collide, and they cannot collide with others themselves; thus for the present second and third people, 18 or 15 is the best choice.
When the problem reaches the last two people, the fourth person (the third person in the original problem) can choose 19 or 14; in that case he is doomed to become the largest or the smallest, and he can only hope that the last person collides with the first person and gives him a free ride. The last person (the fourth person in the original problem) has no other way to survive, and can only choose 16 or 17 and take a chance; in that way he has a 50% survival rate. Then the person before him also has a 50% survival rate. The person before him could also choose 16 or 17 instead of 19 or 14; then as long as he does not collide, he will certainly be in the middle, and his survival rate is still 50%. At this point, whether the last person chooses 17 or 16 (he can know the previous person’s choice, so he will avoid colliding with the previous person, but there is still a 50% chance of colliding with the first person), or chooses below 14 or above 19 and hopes the earlier person collides, the survival rate is still 50%; so he has no reason to keep staring at 16 or 17 and choose those. Therefore, the first person who chooses 16 or 17 will always have a certain survival rate.
Of course, the subtle issue here is the last person (the fourth person in the original problem): if he says, “Anyway, my survival rate is 50%, so I’ll just keep staring at 17 or 16 and choose, reducing the first person’s (the fifth person in the original problem’s) survival rate to zero, thereby forcing the first person (the fifth person in the original problem) to give up this strategy,” is that possible? Of course it is possible! However, his situation is completely different from that of the original last person. Once the original fifth person adopts a forcing strategy, he will obtain a higher survival rate, whereas the original probability was almost zero, so he had reason to do so. But now, even if the present fifth person uses self-sacrificing coercion to scare the first person, or even gives up the right to know the situation, he still cannot make his own survival rate exceed 50%. So he has no reason to do that.
Because of the subtlety of the fifth person (the fourth person in the original problem), the final answer is still rather questionable, but roughly that is the line of thought.

古雴
2008-11-26 18:49:12 [reply]
You’re wrong — you haven’t even understood the solution to your game-theory problem at all!

If “No. 5’s strategy is: choose 16 with 99% probability and 18 with 1% probability,” then “No. 2’s best strategy is to choose 18 with 99% probability and 16 with 1% probability” is absolutely wrong. Think about it: if No. 2 chooses 18 with 100% probability, then the probability of dying from a collision is only 1%, far lower than the 1.98% you calculated! In fact, No. 2’s best strategy is to choose 15 with 100% probability, so that he survives 100%! Then No. 3’s best strategy is to choose 18 with 100% probability, with 99% survival! Finally, No. 4 has no choice but to choose 16, because choosing anything else means certain death, so No. 4 must choose 16, with a survival rate of 1%. And No. 5 will collide to death with No. 4 99% of the time, with a survival rate of only 1%!

Understand?

I’m closing the comments only temporarily. My intention is to have you calm down and think a bit longer before speaking; besides, I’m too lazy to say any more.

igeli
2008-11-26 18:13:00 [reply]

In fact, maybe No. 4 should not choose 16 or 18—because if No. 2 and No. 5 crash into each other and die, then if he chooses one of these two numbers, there is a 50% chance he dies with them. It would be better to choose a number outside these four numbers; then he will definitely get the benefit when two people crash and die. In that case, No. 5’s chance of survival would still be a bit higher, but all of this is already beside the point.

igeli
2008-11-26 18:04:29 [reply]

Why is it only you who gets to talk? Hurry and open the comments again. We’re just discussing the problem, even if a bit fiercely—but isn’t that kind of fun? 🙂
Let me use this place to state my view first; don’t close it again here 🙂
By your logic, one can imagine that No. 5 has countless far superior “strategies” and need not choose between 16 and 17, yet can still make his survival rate far greater than 50%, and can force the first four people to make concessions, for example (just as an arbitrary example):

No. 5’s strategy is: with 99% probability choose 16, with 1% probability choose 18, (assuming he doesn’t even care how many remain, and would choose this with eyes shut), then:
No. 1’s best strategy is to choose 17
No. 2’s best strategy is to choose 18 with 99% probability and 16 with 1% probability
No. 3’s strategy: to simplify the calculation, assume he chooses 15 with 100% probability (he can assign a tiny proportion to the other numbers; that won’t affect the overall conclusion, it would only make the calculation more complicated.)
No. 4, he won’t choose 17, nor will he choose 15, because that would mean certain death; although the chance of surviving by choosing other numbers is small, at least there is still a chance to live. But no matter whether he places his choice on 18 or 16, or outside these four numbers, his only hope of survival is that No. 2 and No. 5 crash into each other and die.
What is the probability that No. 2 and No. 5 crash into each other and die?
The probability that both choose 16 is 99% * 1% = 0.99%
The probability that both choose 18 is also: 0.99%
The probability of crashing into death is the sum of the two, about 1.98%
Now, let us only look at No. 5’s survival probability
1. Suppose No. 4 chose a number above 18; at this point, No. 5 is unlucky only if he crashes into No. 2, with probability less than 2%
2. Suppose No. 4 chose a number below 14; then the death probability for No. 5 when choosing 18 increases again, but not beyond 1%
3. Suppose No. 4 chose one of 16 or 18, and No. 5 just happens to choose that same number too, then the probability of No. 4 and No. 5 crashing into each other and dying is: 1/34 * 99% + 1/34 * 1% < 3% Thus No. 5’s total death probability does not exceed 2% + 1% + 3% = 6% His survival probability is a strong 94%. May I ask, can your conclusion that he would shut his eyes and choose 16 and 17 still possibly stand? 古雴 2008-11-26 14:53:06 [reply] You’re the one being stubborn. Why won’t you think one layer deeper? I’ve already said that 16 and 17 are not just any two numbers. The fifth person can only threaten the first and second people by choosing 16 or 17. In fact, the fifth person’s threat is only effective against the first two. 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 be putting pressure on the first and second people. If No. 5 chooses 16 and 17 each with 30% probability, and 18 or 15 each with 20% probability, then he cannot threaten the first and second people, because although the first person’s survival rate will be only 80% if he chooses 16 or 17, if he chooses 15 or 18 the survival rate is even lower, so he will not be forced into changing his choice. And if No. 5 does not pressure the first two people, then he has no other means. In fact, the third and fourth people will not be pressured by the fifth person. Because even if they know they are being targeted by No. 5, their survival rate will still be at least 50%, and if they change strategy, their survival rate will actually be worse than 50%, so No. 5 cannot force them to give way by threatening them. The key point is that only the first and second people enjoy a comparatively large advantage; they have the chance to obtain a survival rate far above 50%, and therefore the threat is effective. The third and fourth people’s survival rates 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 the targets of the threat. Therefore No. 5’s only means is the threat of a suicidal attack, and the only possible targets on whom this means can work are the first two people; and the only way this means can affect the first two is by choosing 16 or 17 with an extremely high probability—and choosing 1 or 2 and the like poses no threat at all to the first two people. So the smart first person can of course know that threatening 16 and 17 is the only means No. 5 will inevitably adopt. Do you understand? If not, then forget it; I won’t say any more. Comments temporarily closed. Correction: “If No. 5 chooses 16 and 17 each with 30% probability, and 18 or 15 each with 20% probability, then he cannot threaten the first and second people, because although the first person’s survival rate will be only 80% if he chooses 16 or 17, if he chooses 15 or 18 the survival rate is even lower, so he will not be forced into changing his choice.” It should be: “If No. 5 chooses 16 and 17 each with 20% probability, and 18 or 15 each with 30% probability, then he cannot threaten the first and second people, because although the first person’s survival rate will be only 80% if he chooses 16 or 17, if he chooses 15 or 18 the survival rate is even lower (70%), so he will not be forced into changing his choice.” And at this point the first and second people will not change their choices but will still choose 16 and 17, but the third and fourth people will also not change their choices, because if they still choose 15 or 18, their survival rate instead rises to 70%, which is exactly what they want, and they absolutely will not give way to No. 5. 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 in order to pose a threat; as long as that probability falls below a certain value, it will not be threatening. So No. 5’s strategy must first make the probability of 16 or 17 sufficiently large to threaten the choices of the first two people, and only then consider how he can maximize his own survival rate. This consideration of increasing his survival rate will further筛选 out the optimal strategy. For example, if he chooses 16 or 17 each with 50% probability, then he can obtain an x% survival rate himself (because of the subtlety of the fourth person, it seems not to reach 50%). But if he chooses 16 or 17 each with 49% probability and 1 with 2% probability, then although this still suffices to threaten the first two people, the survival rate No. 5 obtains will certainly not be greater than x, because the extra possibility of choosing 1 has no effect on the situation; it is just pure suicide. So according to the degree of survival rate ultimately brought to No. 5, we can rank all the strategies available to No. 5 that can threaten the first two people. Among them there must be some strategy that brings the greatest survival rate. That strategy is then No. 5’s optimal strategy. This strategy is uniquely determined, and any smart person can work it out, so there is no need for No. 5 to declare it; the other smart people can already know the optimal strategy No. 5 will inevitably adopt. That’s all! igeli 2008-11-26 13:45:05 [reply] The problem is already this clear, and you still haven’t realized it? For example, according to your idea, we can assign No. 5 countless optimal strategies, and their results (by your reasoning) would all give No. 5 a 50% chance of survival; for example: No. 5 may have optimal strategy 2: choose 15 or 16 each with 50% probability, or optimal strategy 3: choose 18 or 15 with probabilities of 85% and 15%, respectively... and so on. On what grounds do you say that he must stubbornly cling to 16 and 17 and force Nos. 1 and 2 to give way? As for the game-theory principles and logical calculations you keep mentioning, I’m sure you know a lot about that area. But even if you bring the whole textbook over here now, it still won’t save No. 5’s life, because truth becomes clearer the more it is argued :) Sorry if that came out a bit sharp; I just think you’re too stubborn :) 古雴 2008-11-26 09:09:03 [reply] Let me summarize briefly: Igeli’s answer contains two conclusions. A: The first two people will choose 16 and 17 beans respectively, and the first four people will choose 15, 16, 17, and 18 beans. B: The fifth person gives up any specific strategy and just picks a number at random from the remaining beans. But how are these two conclusions proved? In fact, the proof of A requires B’s inevitability as a premise; in fact, A’s reasoning process contains something like: “B is inevitable; the first four people are smart; therefore the first four people know B; therefore the first four people will calculate their corresponding survival rates under B; therefore the first four people will necessarily make such-and-such trade-offs; therefore A.” On the other hand, where does B come from? In fact, B also takes the inevitability of A as a premise; its reasoning process is something like: “A is inevitable; the fifth person is smart; therefore the fifth person knows A; therefore the fifth person will know he is doomed; therefore B.” But this circular argument does not 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 perhaps expressing this in the language of modal logic would 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 I have proved “◇~A→~B/or written as ~□A→~B” (if non-A is possible, then non-B); “□~B→~A” (if non-B is necessary, then non-A) and “~□B→~□A” (not necessarily B means not necessarily A, in other words, if possibly not B, then possibly not A) And for the fifth person, he has the ability to choose; he can choose the mode of behavior B, or the mode of behavior ~B. He can choose always B, that is, □B, but he can also, in any situation (he can refuse to make a full assessment of the situation by refusing to thoroughly determine the remaining beans), refuse B, that is, □~B. And the condition says that the fifth person is an exceptionally smart person, so he will certainly choose the optimal 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 will certainly die. So the smart him certainly will not make □B true. In that way □A also no longer holds. This problem’s formalization still needs some additional modal operators, such as using “□1, □2, □3, □4, □5” to denote “the first person knows...,” “the second person knows...,” and so on; and the precise definition of a “smart person” can be: “□p→□1p” — that is, a smart person can know everything that is necessary. But here necessity refers to logical necessity, not factual necessity; that is to say, even if in fact the fifth person is already doomed to die when he makes his choice, he can still choose not to know this fact, if his factual doomed condition is not a logical necessity. In short, I can at least prove that Igeli’s proof is wrong; that much is logically clear. Of course, I suppose the original questioner did not intend to make things this complicated, but that is another matter. 古雴 2008-11-25 20:53:26 [reply] You have not understood the principle of game problems. In any case, now I, as the fifth person, choose the strategy of drawing 16 or 17 beans, and you, as the first person, also choose the strategy of drawing 16 or 17 beans. Fine, now my strategy has reached equilibrium, because even if I adjust my strategy I still cannot obtain the slightest chance of survival, so my strategy is stabilized at 16 or 17. But at this point, equilibrium has not been reached for you; you still have a better choice, so the game must continue, and if you slightly adjust your strategy to increase the probability of choosing 15 or 18 a little, your winning probability will increase a little, so you will continue to adjust your strategy. Of course, I have already said everything that needs to be said. If you still don’t understand, I’m afraid it’s because your concept of game theory is not sufficiently clear. Of course, I don’t have much understanding either, but I feel that this problem does not require overly deep knowledge of game theory in order 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 “exceptionally smart” in this sort of problem, are all open to question. If you raise targeted objections to these concepts, I’d be willing to take a further look; otherwise, let’s end this discussion here. And don’t discuss other math problems with me anymore either; at least for the near future I don’t want to keep fussing over these things. By the way, you might as well think again about that “commander, sapper” versus “bomb, platoon leader” game. Keep the other rules unchanged, but change one rule: namely, if the platoon leader runs into the sapper, there is only a 50% chance of killing the opponent, and a 50% chance of still being killed by the sapper. If both people are smart and both know the other is smart, what will happen? What strategy should be adopted? Where is the following reasoning wrong: If B chooses bomb, he dies for sure, so the smart B will not choose bomb. B will inevitably choose platoon leader. So A choosing commander is certain to live; choosing sapper carries a risk of death. A, being smart, will of course have to choose commander. B knows that A is exceptionally smart, so B knows that A will inevitably choose commander. So B knows that even if he chooses platoon leader, he will still certainly die. Knowing that both choices lead to certain death, B has no reason to favor one over the other. So B will choose 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 smart A knows that B can only choose bomb or platoon leader with equal probability. So A knows that if he chooses sapper, he will have a 3/4 chance of survival. 3/4 is greater than 1/2. So the smart A must choose sapper. The smart B understands the smart A’s choice, so B will definitely choose platoon leader. …… Where does the problem lie? The key is that the assumption “when one knows that both choices lead to certain death, then one will pick one at random with equal probability” is questionable. The key lies in what is meant by “knowing one is certain to die.” In particular, if the certain-death situation itself is related to the choice he will make under certain death, then how can one clearly know one is doomed before deciding what one will do in that doomed situation? In particular, if the rules allow one to choose while blindfolded, without fully knowing information that could be known, then how can you know before making your choice that you are doomed? You cannot appeal to a spectator outside the game to look at the problem. For the spectator, when the fifth person begins to choose, the first four people’s choices have of course already become fixed facts. But the key point is that the fifth person “can” not know. The fifth person has the right to decide to make his choice without knowing the sufficient information. And the problem is that in the reasoning by which you conclude that the first person must choose 16 or 17, you are using the assumption that the fifth person can only choose randomly. But this assumption does not hold; the fifth person has sufficient reason not to choose randomly, so the reasoning that the first person must choose 16 or 17 is invalid. That “commander, sapper” versus “bomb, platoon leader” paradox is still quite interesting—in the original problem, if we tweak it a bit further, say B has two bombs and one platoon leader in hand. If B is an irredeemable idiot and cannot distinguish the meaning of bomb from platoon leader at all, he would simply throw out one card at random, that is, 2/3 bomb and 1/3 platoon leader. And A knows that B is an idiot and that B will just toss cards around randomly, so A will choose sapper 100% of the time to ensure the highest survival rate, namely 2/3 (if he chooses commander, then the survival rate is only 1/3). Thus the idiot B also gets a 1/3 survival rate. But if B is not an idiot and instead is exceptionally smart, he will realize that choosing bomb is suicide no matter what, and therefore he will never choose bomb. And if A knows B is a smart person, he will know that B will certainly choose only platoon leader (note that this is questionable), so A will definitely choose commander; as a result, compared with the idiot B’s 1/3 chance of survival, the smart B instead dies for sure. Is this what it means for intelligence to be undone by intelligence? But in order to survive, does a smart person have the right to give up his own knowledge? Why can’t a smart person do what an idiot can do? igeli 2008-11-25 20:26:19 [reply] I think your biggest problem is that you hypothesize that No. 5 has an optimal strategy, but the first four people can see that, under the given facts, No. 5 has no optimal strategy. In your words: “Even if the opponent knows his strategy, there is nothing he can do, because even if he knows the opponent’s strategy he still cannot adjust to a new strategy to improve his winning rate; at this point the game has reached equilibrium.” I think there is no need to keep discussing this problem, 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 doubts about this conclusion, you can consult some authoritative institution; I think this problem is not so complicated that ordinary people cannot understand it. 古雴 2008-11-25 19:19:48 [reply] If a game problem has a solution, then each person’s strategy is exactly optimal, and even if the opponent knows his strategy, there is nothing he can do, because even if he knows the opponent’s strategy he still cannot adjust to a new strategy to improve his winning rate; at this point the game has reached equilibrium. For example, what is the best strategy in rock-paper-scissors? It is for each side to play rock, scissors, or paper with equal probability of 1/3; at equilibrium, the win rate is 50%. This equilibrium position can be understood as the balance reached in a gambling game repeated infinitely many times. For instance, if your initial strategy is to play rock 100% of the time, then after many rounds I discover your strategy, and I adjust my own strategy according to your move probabilities; I will then increasingly raise the probability of playing paper. But after many more rounds, when you discover that I am increasingly raising the probability of playing paper, you will in turn increasingly raise the probability of playing scissors... In this way, both sides’ strategies keep adjusting, but this adjustment is not chaotic; it has direction. You will find that when both sides adjust their strategies in order to improve their win rates, they are always getting closer and closer to the best strategy, namely 1/3, 1/3, 1/3. In the end, when both sides’ strategies approach adjustment to 1/3, 1/3, 1/3, the game tends toward equilibrium, and even if each side sees the other’s strategy, there is nothing to be done— even if I know your strategy is 1/3, I still cannot find a better strategy. Of course, if I know your strategy is 1/3, then going back to a strategy of 100% rock would also yield the same win rate, no? Then how can that be called equilibrium? But there is no helping it: that is what equilibrium means in a game problem; that is the best strategy. If you say that once equilibrium is reached one can just revert again, that is pure quibbling. If the bean-grabbing game is also understood in the same way as an ordinary game problem, then the question is simply where the final equilibrium of this strategy lies. Does such an equilibrium point exist? Now the fifth person is taking the strategy of 16 or 17; what should you, as the first person, do? The first person will certainly adjust toward the strategy with a higher win rate, and then the later people, knowing the new strategy after the first person’s adjustment, will in turn adjust their own strategies for a higher win rate. After the later people adjust, if the first person still has room to improve his win rate, he will adjust again... In short, if there is a solution in the end, it will be an equilibrium; at that point, even knowing everyone else’s strategy will be useless, and it will no longer be possible to improve one’s own strategy on that basis. That is the solution to the game problem. And here, even if we say that 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 randomly picking anything. 古雴 2008-11-25 18:58:13 [回复] Yes, exactly: he has no way to proclaim in advance that he will choose 16 100% of the time. Because the earlier people cannot predict this strategy of his, since 16 and 17 seem to have some sort of symmetry (of course I have not given a detailed proof that the symmetry is between 16 and 17; perhaps it is between 15 and 16, I don’t care, but it is very likely to be 16 and 17). That is to say, “if the earlier people know that the fifth person will definitely choose 16,” the survival rate of the fifth person, and “if the earlier people know that the fifth person will definitely choose 17,” the survival rate of the fifth person, are the same. Then the earlier people cannot guess whether the fifth person is choosing 16 or 17. But the effect of the fifth person choosing 16 is obviously not the same as his choosing 1; they are asymmetric, so a smart fifth person has reason to put more probability on 16 and 17. In game problems, the reason one side’s best strategy must be given in terms of some probability is that, under the relevant circumstances, one must increase the uncertainty of one’s own moves in order to increase one’s win rate. And if increasing the possibility of one option will not increase one’s win rate, then that option will not be considered. In other words, options such as taking 1 bean or 2 beans will not be considered by the fifth person, because even if the likelihood of choosing them increases, it will not cause any disturbance to the opponent, and therefore will not increase his own win rate. The options 16 and 17, however, can disturb the opponent to the greatest extent, thereby increasing his own win rate, so the fifth person will certainly lean toward choosing 16 or 17. This strategy is something the first person can foresee. Do you lack an understanding of game problems? Game problems can be converted into gambling problems. For example, here the consequence of grabbing green beans is not the one-time loss of life, but that the loser pays money, and the game is played repeatedly. Then if you are the first person and I am the fifth person, what strategy would you adopt? If you stubbornly insist on always choosing 16 or 17, then in 100 games you can only win about 50 times; but if you are willing to switch to another scheme, your win rate will rise dramatically to 75%, so that is your best plan. If you know full well that there is a better strategy with 75% and yet stubbornly refuse to use it, how can you call yourself a clever person? And if I can obtain some win rate in what appears to be a hopeless predicament, is that not clever? Are you saying that the most brilliant person’s win rate would be lower than that of a fool who only knows how to grab 16 or 17 beans? Then what exactly is your definition of “clever”? Back then I posed the simplest version of the game problem: http://epr.ycool.com/post.2471508.html. The other game problems are actually all similar. igeli 2008-11-25 18:32:20 [回复] Of course, as for the sentence “if he has a chance to live, then whether he figures it out or not it is 50%; if he doesn’t figure it out, it is also 50%,” I didn’t think about whether it is true or not. :) igeli 2008-11-25 17:59:48 [回复] This is obviously forced — why would person 5 choose 16 or 17? Of course because he has already calculated it. This has nothing to do with whether he figures out the remaining number or not, and no relation either. That also means that person 5 already knows his own fate. If he could threaten the others in advance, for example by declaring that he will choose 16 100% of the time, then perhaps he would have a very large expected survival period. Unfortunately, he cannot do that. 古雴 2008-11-25 17:01:57 [回复] Haha, you missed one condition! The condition says that each person can figure out the number of green beans remaining, but it does not say that each person “must” figure out the number of green beans remaining. The fifth person’s strategy is that as long as there are enough green beans, he takes 16 or 17, and no longer cares how many beans remain. Such a method is the most rational. The fifth person has sufficient reason to support not figuring out the number of beans remaining, and sufficient reason to support choosing certain specific numbers. That is the most rational and best strategy. Just like that game between the commander and the engineer against the bomb and the platoon leader. If the conditions stipulate that B must choose a card only after looking at the card, then no matter what he does he will not choose the bomb, since that would be suicide; thus B can only play platoon leader, and then A only needs to keep playing commander, and B cannot escape death. But if the conditions allow B to blindly draw a card without looking, and A knows that B can do this, then the result of the game is that B has a 1/4 survival rate. In that problem, because the conditions were vague, the answer was also unclear. But in the bean-grabbing problem, the conditions are clear — I can simply draw with my eyes closed! If drawing with my eyes closed gives me a higher survival rate than drawing after figuring things out, then I will not waste effort insisting on figuring things out; that is what rationality is! For the fifth person to spend extra effort figuring out the number of green beans remaining is irrational, because if he is doomed to die, he will die whether he figures it out or not; if he has a chance to live, then whether he figures it out or not it is 50%, so figuring out the remaining number of green beans is meaningless, and the fifth person will not do that. And the first person knows that the fifth person is rational. igeli 2008-11-25 13:46:59 [回复] I think the problem should be understood this way — this should be the rational interpretation: 1) Since person 5 has no way to inform the first four people of the distribution of his own probabilities, the first four people should choose in the way most advantageous to themselves. 2) Once the situation of 17, 16, 18, 15 has formed, person 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 at this point that he will choose 17 or 16, then that is not rational; it is being sulky :). And the question we are discussing is one that does not take emotional factors into account. 3) The first four people all understand this, so their choices are stable, thereby dooming person 5 in exchange for maximizing their own interests. This conclusion should be correct. We can discuss other questions now :) 古雴 2008-11-25 12:51:28 [回复] No, the first four people know that the fifth person will definitely adopt the best strategy; that is the premise of this question. Just as the first three know that the fourth person will necessarily adopt the best strategy, the first two know that the third person will necessarily adopt the best strategy... Under this premise, only then can you infer that the first four people will end up with the result 17, 16, 18, 15. However, your reasoning has not taken the fifth person’s best strategy into account; you think the fifth person simply gives up any strategy in despair. 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 sacrificial attack. For the fifth person, this strategy is always the best: if he is doomed to die, then the outcome is the same no matter which number he chooses; that is to say, when choosing other numbers, it is no better than choosing 16 or 17, so he always has ample reason to carry out this strategy. The first person understands this, and so 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 in any case there must be some numbers that are the focus) is not that he just picked two numbers at random. If the fifth person chooses other numbers with some probability, the equilibrium state may be broken, and he may no longer be able to obtain a 50% survival rate. If he wants any possibility of obtaining a 50% survival rate, the fifth person has no other way. In short, in this game of absolutely brilliant 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, at least he has such a survival rate. All right, let’s stop here on this problem. Of course, this definitely is not the final answer. Because there is still a problem here, namely that the fourth person does not necessarily have to leave the fifth person a way to survive. 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 additional reasons for making a particular choice even when the survival rates are equal. Moreover, even under your original line of thought, the fourth person’s survival rate also happens to be 50%; his situation is relatively subtle, so it seems that this equilibrium is still unstable. But at any rate, we have seen the hope of survival for the fifth person. Perhaps the fifth person’s optimal strategy should also include options such as 13 and 20, using subtle pressure to force the fourth person to give way? In any case, even if the fourth person, when survival rates are equal, will make his choice with equal probability, the fifth person still has reason to consistently carry out the sacrificial strategy. igeli 2008-11-25 12:00:12 [回复] For the first four people, since they do not know the fifth person’s probability distribution, they can only make decisions based on their own subjective judgments — their beliefs — and in this way the result will be 17, 16, 18, 15, won’t it? 古雴 2008-11-25 10:23:31 [回复] Perhaps the fifth person’s best strategy is not complicated at all; maybe it is simply to choose 16 or 17 with equal probability, as long as there are enough remaining numbers to choose from. Then the first two people know the fifth person’s best strategy. If the first person chooses 16 or 17, his survival rate will be under 50%, but if he chooses 15 or 18, his survival rate will be over 50%, so the first person’s best strategy is to choose 15 or 18, and the second person then chooses 18 or 15 depending on the first person’s result. Then the third person can choose 16 or 17, which gives a survival rate of 50%, or choose 14 or 19, in which case the survival rate is still 50% in the end. The fourth person, based 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 will both survive; if the fifth person does not die, then one of the first two people will die. That is to say, the survival rate for the first two people is 75%. Oh yes, the fourth person’s strategy cannot be to choose 14 or 19, otherwise the fifth person would be able to figure out whether the third person chose 16 or 17. So the fourth person should choose 13 or 14 or below, 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 being able to tell whether 16 or 17 has been occupied. Thus the survival rates are still 75%, 75%, 50%, 50%, 50%. Apart from the fifth person’s strategy, which is pieced together, the other four people all seem to have no choice but to choose according to this plan, otherwise it would be difficult to obtain a higher survival rate. The third person must not adopt the strategy of taking most of the green beans and leaving only two. Because then the survival rate he gets would not be 50%, but rather the “revenge” of the fourth person, who is doomed to die (if the third person leaves no way out for the fourth person, the fourth person will certainly drag him down with him, so the third person must leave a way out for the fourth person). 古雴 2008-11-25 10:07:07 [回复] Anyway, I’ve been so tormented by this problem these past two days that my sleep has not been good, so I’m giving up on continuing to wrestle with it... let’s stop the discussion here... igeli 2008-11-25 09:58:13 [回复] If this equilibrium point cannot be found, then the choices will probably become chaotic. Perhaps the problem setter simply never thought so much about it. igeli 2008-11-25 09:55:11 [回复] I think this discussion is becoming rather captivating :) Suppose person 5 announces a table matching remaining numbers to his own choice probabilities. Then he really might be able to survive, but this workload seems like it would probably be 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 immature thought: Publishing a table would probably make it easy to find an equilibrium point; but what if, in fact, there is no stable equilibrium? Because the prisoners cannot communicate information with one another, that is to say, for person 5 to artificially create an equilibrium point (by publishing a table) is impossible. 古雴 2008-11-25 04:44:10 [回复] 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 platoon leader, company commander, battalion commander, regiment commander, brigade commander, division commander, army commander, and bomb (the engineer can defuse the bomb, while the commander and the bomb perish together). What are the best strategies for both sides? If A plays commander, then whatever B plays, B will not be able to escape death. So is A’s best strategy to play commander, while B can only blindly draw from the cards in his hand? Of course not. B’s best strategy is to play bomb with a relatively high probability. In this way, once A plays commander, there is a high probability that A will be blown up. And what A considers first of course is his own survival, so he will not rashly play commander. Of course B cannot play bomb with 100% probability; in that case A could simply always play engineer. So the best strategy is the equilibrium point of the two sides’ game. 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, at equilibrium we should have xy = (1-x)(1-y). And for B, he should seek to maximize the survival rate, namely (1-x)(1-y). The result is x = y = 1/2. In other words, B’s best strategy is to play bomb with a 50% probability, and if A is a smart person, B will obtain a 25% survival rate. The bean-grabbing problem is much more complicated than this. But that does not mean there is no similar equilibrium point to be found. However, this problem is still a pseudo-game problem. As a game problem, it has no solution, because only A’s choice is balanced, while B’s is not... Of course, this problem actually reflects some kind of paradox inside it... But in the more complicated bean-grabbing problem, it is quite possible that a genuine solution to the game problem exists. The key is that the last person will by no means obediently play a passive role, but will instead use a sacrificial attack to intimidate the people before him into leaving some opening for the last person. In fact, in this game, the first person does not have much advantage over the last person. 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 make his choice after referring to the results of the first four people, whereas for the first person, the choices of the last four are still uncertain probabilistic states. 古雴 2008-11-25 03:45:57 [回复] Ah, right, right. As a game, why would the last person obediently leave everything to fate and pick randomly? In fact, in this problem, since all five people are absolutely smart, it also means that the people in front will be able to understand the best strategy of the last person. And the last person’s best strategy is absolutely not to pick any number between 1 and 34 at random, but rather, for example, to choose 16 or 17 with a very high probability, or to choose 18 or 15 with a very high probability... This is not because he has any private grudge against the earlier people or anything like that, but because only by adopting such a strategy can he ensure the possibility of surviving. The fifth person is a smart person, so he will certainly choose the strategy that makes it more likely for him to survive. And since the first person knows the fifth person’s strategy, he will not rashly choose 16 or 17, because if he does, he will very likely be killed by the fifth person. So he must choose some other number with a certain probability, and this will leave a gap for survival for the fifth person. Therefore, this game may indeed have an equilibrium point. That would be the first person choosing 16 or 17 with a certain probability, and choosing 19 or 14 with a certain probability. And the last person choosing 16 or 17 with a certain probability, and 18 or 15 with a certain probability, and so on. So in this way, for example, when the first person chooses 19, the second person is not doomed to choose 18 either, because the fifth person can still adopt a different strategy when there are not 34 beans left, but 30. That is, once 30 beans remain, it probably means the first person chose 19 and the second person chose 18. Then the fifth person’s strategy can be: when 30 remain, choose 18 with a huge probability in an effort to kill the second person. In that case the second person will not rashly choose 18. —The second person’s strategy is also some probability distribution among a few choices such as 18 or 14. Thus, once the situation arises in which the first person chose 19, the second person chose 14, and the fifth person chooses 16 or 17, the fifth person gets to survive. In short, the fifth person does have the possibility of surviving, and the equilibrium point of the game may be found. Gu Chu 2008-11-24 23:29:46 [reply] Mm… actually the second person’s situation seems to be the same as the first person’s. There is a paradox here: if one gives up one’s own ability to choose and entrusts the right of choice to something else—the first person entrusts it to a random-number generator, while the second person entrusts it to the first person and the random-number generator—and oneself no longer makes any choice at all, that is, if one will follow through even when the choice made by the other would lead to one’s certain death. If that were the case, then one would obtain a higher survival rate. But the question is, if people are unwilling to give up the freedom of their final choice, then even when the first person sees the random-number generator indicate that he should choose 4 (and die), or when the second person sees the first person choose 4, he will absolutely not obediently choose the fatal option. Then the game strategy becomes unworkable. In this way, the price of taking back freedom is a lower survival rate… Moreover, an enumerative proof of this problem is still possible, namely, assume that each person chooses I beans with probability Xi%, then expand all the various outcomes, and finally find the saddle point using the solution method for game-theory problems… though that seems far too enormous. But in any case, this game-theoretic scheme of mine is merely a disguised scheme. In a game, if equilibrium is eventually reached, then each option’s winning probability should be the same. But here that obviously cannot be achieved. Yet the key is to prove it. Gu Chu 2008-11-24 22:46:36 [reply] Oh yes, one can make it symmetric: the first person can, with the same tiny probability, choose 4 or 29, as well as 15 or 18. The second person’s response is also symmetric. In that way, it can make 16 and 17 equally likely to be taken by the third person, and what is left for the fifth person is always 34. Mm. Uh, the first person does not need to increase the possibility of choosing 29; he only needs to increase the option of 18. And the second person, in turn, increases this tiny possibility of 4+31~ Of course, in this problem, whether the first person chooses 4 or 29 or the like, once it has become a settled 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 cannot find a proof that such a strategy cannot exist. Verifying one by one with enumeration does not work, because the strategy here is not just a single choice, but a delicately distributed probabilistic scheme, and its possibilities are infinite. Gu Chu 2008-11-24 22:33:54 [reply] Regarding how this can be turned into a game-theory problem, I can give an example—let me use this very problem as the example: The first person adopts the following strategy: with a 99.999…% probability he chooses 16, then with a 0.00001% probability he chooses 4, and with a 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 a 99% probability and 29 with a 1% probability (if he chooses something else, the death rate is also extremely high, and he may be forced to cooperate, though I have not analyzed this carefully yet.). 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 if the first two both seize 16+17 or 4+29, then the third and fourth will choose 15 and 18 (I have not analyzed this carefully either). The key is the last person. What is always left for him is 34 beans, yet now his survival rate is no longer 0%, but has a glimmer of hope, however smaller than 0.00001%. If the first person chooses 4, then the last person choosing 5, 6, 7, … and so on will all survive. Yet he will not choose 16 or 17, because even when the first person chooses 4, the second person has a 99% probability of choosing 27—that is to say, the chance that 16 and 17 will be taken by someone among the first four people is far higher than the chance that 5, 6, 7, and so on will be taken. Therefore the last person will be more inclined to choose 5, 6, 7, and so on, and will be almost impossible to choose 17. In other words, although for the first person choosing 4 beans is an act that is nearly suicidal, so long as he increases the probability of choosing 4 beans for himself by 0.000000…1%, he can induce the fifth person to drastically reduce the probability of choosing 16 or 17. In other words, the first person’s survival rate thereby rises from 33/34 to 99.9999…%! Even if this strategy still has loopholes and is unworkable. The reason I brought it up was mainly to show a certain possibility—through some complex game, it may be possible to give the fifth person a glimmer of hope, thereby reducing the chance of repetition with the fifth person and execution. Even if I cannot produce such an example, if you have not proven that such an example necessarily does not exist, then your proof is not rigorous. igeli 2008-11-24 21:36:34 [reply] I think that kind of perfect strategy cannot exist. In fact, because there are so many possibilities, we previously qualitatively ruled out the case where person 1 chooses above 20; in that case he is very likely to become the largest. If you have time, you can also quantify them one by one for him :), and of course you can also calculate all the cases below 15. As for whether one should weight the probabilities in some possibilities—as you say, turning it into a game-theory problem—I have not come up with any reason to do so. If you split off part of person 1’s optimal strategy and degrade it, no matter how small that proportion is, it will lower person 1’s overall survival probability, won’t it? Can you think of a counterexample? Gu Chu 2008-11-24 18:18:48 [reply] Once probability is involved, the strategy problem may become a “game-theory problem”; that is to say, once probability is involved, the “best strategy” may no longer be a definite choice, but a choice of probabilities. For example, “the best strategy for a certain person is to choose A with a 90% probability and B with a 10% probability.” Gu Chu 2008-11-24 18:08:33 [reply] I also believe that the best strategy is 16 or 17 green beans; the problem is that the argument is not rigorous enough. After all, even when the first person chooses 16 or 17 green beans, the survival rate is not 100%. But could there be such a situation: because we have not proved that when the first person does not choose 16 or 17 beans, the later people must also choose consecutive numbers, perhaps when the first person chooses A beans, the choices of the first four people still leave gaps, and then the fifth person still has a glimmer of hope. In that case the fifth person would not choose blindly, but would, for example, have to gamble on B or C. And if A is neither the largest nor the smallest, nor poses a risk of colliding with the fifth person, then the first person’s survival rate would be 100%. Intuitively, this perfect strategy seems unlikely, but the solution you gave alone is not enough to prove that such a strategy does not exist. igeli 2008-11-24 16:10:12 [reply] I’ve thought it through; that number problem is almost a purely mathematical problem, with little meaning, so I won’t discuss it here anymore. igeli 2008-11-24 15:15:14 [reply] That is to say, although in the discussion we mention scheme 1 and scheme 2, in fact there are also schemes 8, 9, 10... But because those schemes are not optimal strategies, they would not be considered possible, nor would they be weighted into the result. igeli 2008-11-24 15:11:28 [reply] An interesting idea. However, because these people are all extremely intelligent, if person 4 discovers that the preceding people are not the optimal combination 17, 16, 18, he should be able to judge that someone is definitely playing tricks, and the most likely culprit is person 3. Since 17, 16 is optimal for persons 1 and 2, then he may be able to infer person 3’s number, thereby putting person 3 in the most unfavorable position. Person 3 therefore would not dare take the risk; otherwise he would be rather irrational. Except for the combination 17, 16, it should be impossible to appear; otherwise they would not be smart (contradicting the premise), or else someone would be pulling tricks, and that would involve too much risk, making it irrational and unwise. Since it can be deduced by the later people, all such cases should be excluded. I’ve had some ideas about the problem with 100 numbers; I’ll write them out in a bit and discuss them with you :) Gu Chu 2008-11-24 13:26:11 [reply] Your solution and answer are the same as mine. But I have a feeling it may not be rigorous enough. The key is: how can the last three people determine that the earlier people chose consecutive numbers? Because they can only infer the total number taken by the first three people; if one naively assumes that the first three definitely chose consecutive numbers, the fourth person may be fooled. For example, suppose the first two choose 17 and 16, and then the third person plays a dirty trick and chooses 21. In that case, will the fourth person mistakenly think that the first three chose 19, 18, 17? If so, the fourth person would choose 16, thereby colliding to death with the second person. Then the third person, having chosen 21, survives, and his survival probability if he chooses 15 is only 19/34. Going further, the second person, considering that the third person may play a dirty trick and kill him, would he also no longer dare to choose 16 so easily?… 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 four. 2) Person 1 chooses 99; persons 1 and 2 are both doomed, while the other three live. 3) Person 1 chooses 98; person 2 is doomed, but can choose person 1 or 3 to die with him. igeli 2008-11-24 12:46:03 [reply] (continued from the previous part, Part 3) I didn’t expect it would have to be split into three chunks :) Scheme 3 (person 1 chooses 17) When person 1 chooses 17, if the sequence 17, 16, 15, 14 appears, then person 5 has 38 possible choices Person 1 dies: person 5 chooses 17, or a number less than 14, 14 possibilities total; survival probability 24/38 Person 2 dies: person 5 chooses 16, 1 possibility; survival probability 37/38 Person 3 dies: person 5 chooses 15, 1 possibility; survival probability 37/38 Person 4 dies: person 5 chooses 14, or a number greater than 17, 22 possibilities total; survival probability 16/38 For person 4, since 16/38 < 19/34 (refer to Scheme 2 when choosing 18), he will not choose 14, but will choose 18, producing the arrangement 17, 16, 15, 18. Of course person 3 knows that if the arrangement 17, 16, 15 appears, person 4 will definitely 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 15. In this way person 1 achieves the goal of forcing others to sandwich him in the middle: in the end the first four choices are 17, 16, 18, 15 The survival probabilities of persons 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 survival probability is maximal, about 97% igeli 2008-11-24 12:44:27 [reply] (continued) Scheme 1 (person 1 chooses 19) According to the above reasoning, when person 1 chooses 19, the arrangement 19, 18, 17, 16 will appear. At this time person 5 has 30 possible choices: Person 1 dies = (person 5 chooses 19, or a number smaller than 16), 16 possibilities total; person 1’s survival probability is 14/30 (clearly the most unfavorable for person 1) Person 2 dies = (person 5 chooses 18), 1 possibility; person 2’s survival probability 29/30 Person 3 dies = (person 5 chooses 17), 1 possibility; person 3’s survival probability 29/30 Person 4 dies = (person 5 chooses 16, or a number greater than 19), 12 possibilities 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 (nobody chooses 19, because 14/30 would be the minimum), and person 5 then has 34 possible choices: Person 1 dies: person 5 chooses 18, or a number smaller than 15, 15 possibilities total; survival probability 19/34 Person 2 dies: person 5 chooses 17, 1 possibility; survival probability 33/34 Person 3 dies: person 5 chooses 16, 1 possibility; survival probability 33/34 Person 4 dies: person 5 chooses 15, or a number greater than 18, 17 possibilities total; survival probability 17/34; (clearly 17/34 > 14/30)

igeli
2008-11-24 12:40:38 [reply]

It may be too long, so 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 flaws in the reasoning. Please advise 🙂
Clearly, the person at either end (the largest number or the smallest number) has a higher probability of death. Person 1 chooses first; he should not choose a number above 20, otherwise he will leave person 2 a very good strategy: choose a slightly smaller number, one that is 1 less than his or close to it (in special cases, person 2 can even guarantee he won’t die—for instance, if person 1 chooses 35, then person 2 chooses 34 or 33, because the remaining total is smaller than him, so person 2 will not die. If person 1 chooses 21, then person 2 chooses 20, thus guaranteeing that someone later will be smaller than him), so person 2 is placed in a very advantageous position, at least guaranteeing that he is neither the largest nor the smallest, while person 1 faces the danger of possibly becoming the largest number. By the same reasoning, persons 2, 3, and 4 will not be the first to choose a number above 20; 20 will be the largest among the first four numbers. Person 1’s strategy is to choose a number and force the later people to sandwich him in the middle; clearly, choosing 20 is not wise for him.
After person 1 chooses a number, if possible person 2 will certainly choose a number immediately adjacent to person 1’s, so that he will not leave person 3 the excellent position of being in the middle; from this, person 3 can determine what combination the first two numbers are, and for the same reason he too will choose a number adjacent to those two; likewise, person 4 will also choose one at one end of the above three consecutive numbers (these four people will not choose duplicate numbers, since that would mean suicide); thus it can be determined that the first four numbers are four consecutive numbers. No matter what person 5 chooses, he is doomed—if he chooses an end, he is the largest or the smallest; if he chooses the middle, then he will duplicate one of persons 1–4; since each round dies two people, person 5 will choose a number at random, and one person (and only one) will be dragged down with him to die.

igeli
2008-11-24 12:39:09 [reply]

I can’t post comments; is there something wrong with the site?

Gu Chu
2008-11-23 13:35:00 [reply]

After thinking it over, it seems the first person should grab 16 or 17 beans

You can 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 fourth and fifth people are already 100%. 🙂

igeli
2008-11-23 09:10:48 [reply]

The conditions of the green-bean grabbing problem are fully given.
I think that in the desperate situation you mentioned, his choice should be random—because the problem does not say he particularly hates those people; it only says that they like killing people. If he can make more people die with him, he certainly will not let that chance go.

Gu Chu
2008-11-22 21:06:59 [reply]

At first I felt it should be the second person who has the highest survival probability, but later I thought of a strategy for the first person: just grab 98 green beans at once, and then the second person can either grab 2 or grab 1; either way it is a dead end. If he grabs two, he drags the first person down with him; if he grabs one, he drags the third person down with him. If, in a situation where death is certain, the second person’s choices are each 50%, then if the first person grabs 98 beans he can guarantee himself a 50% survival rate. That probability seems rather high for the first person…

Gu Chu
2008-11-22 20:56:35 [reply]

Are the conditions of the green-bean grabbing problem fully specified?

Does it mean that when grabbing, one can only know how many remain? That is, for example, when the third person grabs beans, he can know how many the first two together have taken, but not how many each of them took separately? Also, is this a probability problem? Then if, when someone is in a desperate situation (knowing that no matter how many he grabs he will die), what probability will he use in making his choice? Does it mean that in such a case each choice has an equal probability?

Gu Chu
2008-11-22 20:12:29 [reply]

Don’t talk about extraordinary brilliance—it’s been four or five years since I last did Olympiad math, and my thinking has become much duller. I ought to have reacted much earlier. And even a few years ago, my brain had no standing whatsoever in front of that bunch of prodigies in the science track…

Your problem seems a bit difficult, and now I no longer have the enthusiasm to puzzle over math problems day and night. I thought for an hour and came up with nothing, forget it…

igeli
2008-11-22 18:54:10 [reply]
You really are extraordinarily sharp-minded; that thought (that Yi and Bing had different views) flashed through my mind too, but I immediately discarded it. Looking at it now, it was a close call 🙂
I do have one problem that I’ve never found a good way to solve. Would you care to treat it as a pastime?
Suppose we randomly write a natural number from 1 to 100 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 the number on his own forehead correctly? Before the numbers are written, everyone may confer; after they are written, they may no longer reveal any other information to one another.
I couldn’t find a good answer on the internet.
Another little puzzle:
Five prisoners, numbered 1 through 5, each take green beans from a sack containing 100 green beans. The rule is that each person must take at least one bean (a prisoner who passively chooses zero is automatically spared). If there are no duplicate numbers of beans taken, then the person who takes the most and the person who takes the fewest will be executed. Moreover, they cannot communicate with one another, but while taking beans, they can feel how many beans are left. Who among them has the greatest chance of surviving?
Hints:
1) They are all very intelligent 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 completely divided up.
4) If there are duplicate counts, then those duplicates will be executed in place of the max and min.
Please do exchange ideas; I’m very happy to discuss this with you 🙂

Gu Yao
2008-11-22 18:43:08 [reply]
Hmm, it looks like your method is not wrong.

Gu Yao
2008-11-22 18:39:31 [reply]
Oh, it seems D can be divided in one step? Just a slight modification of the method you mentioned earlier will do?

Gu Yao
2008-11-22 18:32:18 [reply]
Your method looks fairly good, but the key is that the part cut off still needs to be divided, and this remaining D still needs to be redistributed. In that case, there is no way to ensure that the allocation 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 statement a bit:
When both Yi and Bing think A is the largest, suppose Yi thinks A>B>=C. Let Yi split A into A- and D, so that B = A-.
Now let Bing choose from A-, B, C. If Bing does not choose A-, then Yi must choose A-, and the remaining share goes to Jia.
The following version involving D does not need to be changed.
What do you think?

igeli
2008-11-22 18:07:30 [reply]
You really didn’t understand? The rule that Yi must choose A- applies only when Bing has chosen C. And of course A- is what Yi has cut out.
It doesn’t matter whether he cuts it evenly; as long as he thinks it is even, that’s enough. Bing will never say whether you cut too much or too little, because Bing chooses first.
I suspect I’ve talked you into a daze.

igeli
2008-11-22 18:00:11 [reply]
Haha, I suppose you’re dazed now 🙂
When the third person thinks A>C>B, while the second person thinks A>B>C, we let the second person do the division so that A-=B. Then the choices left to the third person are A-, B, and C; he may choose freely. We do not guarantee that the third person will think A- is smaller than C; perhaps he will think it larger, but he has the right to choose, and he will pick from A-, B, and even C the share he considers not too small.
The first sentence of your reply below is also wrong as a condition (if a person is willing to choose a certain part, he must be sure that this part is no less than one third.) This conclusion is only correct after the entire division has been completed. But in the intermediate stages of division, each person only cares that the total amount he gets is not less than the other two people’s, and that it is at least one third of the total; we still have to wait for the next round of division.
How about that?

Gu Yao
2008-11-22 17:36:17 [reply]
Also, in your “rule that the second person must choose A- (he thinks A-=B>C),” who cut down this A-? If Yi cuts A down until it equals B, Bing may not agree; Bing might say Yi cut far too little—far from equal to B (which in Bing’s view is the smallest), and still larger than C! You cannot resolve the disagreement. If it were Bing who did the cutting, Yi certainly might not agree either: too much was cut off!

Gu Yao
2008-11-22 17:27:35 [reply]
You should note that under your conditions, if a person is willing to choose a certain part, he must be sure that this part is no less than one third. Because if he knows what he gets is less than one third, then he will think that at least one of the other two people has gotten more than one third—that is, more than he has.

So if the third person thinks A>C>B, and also that 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 deal with this kind of situation: after Jia divides the portion into A, B, and C, both Yi and Bing think A is the largest, and both think B and C are less than 1/3, but they disagree about which is larger, B or C.

Gu Yao
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 extraordinarily sharp-minded!
But this in no way affects the division. The third person may choose C (the smallest share in the second person’s view), but we stipulate that the second person must choose A- (which he thinks satisfies A-=B>C), thereby leaving B to the first person. After that, the principle of division is the same as above.

Gu Yao
2008-11-22 13:34:15 [reply]
Though I didn’t look closely, your distribution doesn’t seem workable. The key issue is that when the other two both think A is the largest, they may not agree on whether B or C is larger. In other words, you have to consider the situation in which the second person thinks A>B>C, while the third person 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 took C, got more than he did.

igeli  2008-11-22 13:20:46 anonymous 58.31.177.132 [reply]
What a coincidence—I was just about to explain that the same problem exists in the solution for n people, and you’ve already noticed it 🙂
Let me explain the three-person peach-juice problem:
Suppose the first person has divided the juice into three shares A, B, and C in a way he considers equal. Now the latter two people choose, and two situations can arise:
1. One chooses A and the other chooses B. Very good—C goes to the first person, and everyone remains at peace.
2. Both choose A at the same time, meaning they think A>B>=C.
Then let the second person pour out 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 that anyone got more than he did.
Now let the person who got B (suppose it is the second person; if it is the third person, the situation is similar) divide D into three equal parts. Then let the third person choose first, then the first person, and finally the second person. In this way, none of the three thinks that someone else got more than he did:
The first person thinks that even if the third person (who got A-) had received all of D, it would only be equal to what he himself got (C = D + A-). Now the third person has only received part of it, so the total is still not as much as his own C; and since he himself can choose the larger of the remaining two shares, he will not get less than the second person.
The second person thinks that his own B is no less than A- and C, and the little share he gets last is the same as the other two people’s, so no one has more than he does.
The third person thinks that his own A- is no less than B and C, and since he chooses first among the final three shares, nobody will have more than he does.

Gu Yao
2008-11-22 01:56:30 [reply]
In addition, this problem was later generalized to the n-person case: see http://epr.ycool.com/post.2471356.html . However, even according to that general solution, it absolutely cannot satisfy your additional condition that “suppose no one wants others to have more than himself.” The advantage of that general solution is that each person gets exactly the share he himself considers to be 1/n—no more, no less. Yet obviously it cannot guarantee that everyone else also gets exactly the same share, so in the end it is certain that someone will find he has more himself, and this cannot be avoided. I really cannot see how this problem could still have a solution once your condition is added; please advise!

Gu Yao
2008-11-22 01:43:33 [reply]
Oh, sorry. It does seem to be my mistake (suddenly waking from a dream…). The problem was posed too long ago, and I forgot to check it carefully. The statement should have stipulated that what each person ultimately cares about is only whether the share he gets is fair. But if we do not add this condition, and instead, as you say, assume that “no one wants others to have more than himself,” then how can one divide the peach juice?

igeli  2008-11-21 14:21:03 anonymous 221.219.245.20 [reply]
I happened to come across your blog; it’s really nice, and I very much like those playful problems. Haha, at last I’ve found an error:
In the peach-juice division problem: “If Bing thinks the largest is B+ or C+, then let us assume Bing thinks the largest is B+, then divide C+ to Jia and A- to Yi, and that will do.” This won’t work. For example, if Yi divides the peach juice into 1/8, 4/8, and 3/8 (I am exaggerating the numbers for clarity of illustration), Jia will not be satisfied with getting 3/8 (assuming no one wants others to have more than himself). I didn’t think further beyond that.
I do have another good way to divide this peach juice

Latest replies

• Gu Yao

  2008-11-26 21:44:24 

  Alas, I’ve already indulged in nostalgia more than enough. After all, mathematics is no longer my main line of work…
  I won’t keep tormenting this problem any longer!

• Gu Yao

  2008-11-29 01:08:58 

  This discussion has been halted. It cannot continue. Because I have turned into an idiot. Mm.

Translated from the Chinese original with AI assistance. The original text is authoritative.

Subscribe to new posts

Subscribe

After submitting, click the confirmation link in your inbox to complete the subscription.

Advanced: subscribe only to selected topics

AI 与技术未来 Web3 与密码朋克 哲学与思想 教学与课程 文化与公共评论 生活与随记 科学史与学术 站务与琐事

勾选后只收所选主题的新文章；不勾选则订阅全部。