Problem 6. Robin Hood captured seven rich men and demanded a ransom. A servant of each rich man brought a purse of gold, and they all lined up in a queue in front of the tent to pay the ransom. Each servant entering the tent places the purse they brought on the table in the center of the tent, and if no one has previously brought a purse of equal or greater weight, the rich man is released along with the servant. Otherwise, the servant is told to bring another purse that would be heavier than all the purses currently on the table. After fetching the next purse, the servant goes to the end of the queue. The trips to fetch the purses take the same amount of time for everyone, so the order of entering the tent does not get disrupted. When Robin Hood released all the captives, he had: a) 28; b) 27 purses on the table. What was the initial position in the queue of the servant of the rich man who was released last?

[10 points] (M.A. Khachatryan)
Answer. a) Seventh; b) sixth or seventh.

Solution. If the servant brought a new purse, and since he was last in the tent, no one has been released, then he is definitely in for a stroke of luck (his purse is the heaviest and this time his master will be released). That is, if there were $N$ rich men in captivity and only one has just been released, then there can be no more than $N-1$ failures in a row from now on.

a) If there were seven rich men at the beginning, the first one will be released immediately, then there will be no more than 6 failures, then a success and no more than 5 failures, and so on - and in total Robin Hood will receive no more than
$(1+6)+(1+5)+(1+4)+(1+3)+(1+2)+(1+1)+1=$ $=28$ purses. And he will get exactly 28 purses only if on the first round, everyone except the first one had a failure, then everyone except the second one, and so on. And the seventh servant will put the last purse.

b) If Robin Hood ended up with 27 purses instead of 28, then exactly one interval of failures must be 1 shorter than the maximum. Then it will end not after the transition to the next round, but one step earlier, and on this round, in addition to the servant with the smallest number, the seventh servant will also get lucky.

If this happened on the last round, when all the other servants had already left, then the seventh servant will put the last purse. And if some servants are still left when the seventh servant gets lucky out of turn, then the remaining ones will continue to leave in order, as in the previous part. And the last purse will be put by the last of the remaining - the sixth servant.