3
$\begingroup$

Currently, I am modeling a problem that I am working on (in distributed systems) as a riddle and I'd like to know your opinions, suggestions and solutions. You can find it here on github.

Thirsty men problem:

On a hot day, a water outage occured while you were feeling very thirsty. You went to the fridge to get some cold water. You were lucky enough and you found a single bottle of water left. While you were enjoying this finding and playing with your bottle in the air. Ding dong, somebody rang at the door.

You had got N unexpected guests, all of them staring at the bottle in your hand, and suddenly shouting all once "we are thirsty". You let them in, and you all gathered in the same room around a table and everybody asked you to drink.

Now the problem: The bottle (½ littre) can only fill 3 cups.

To overcome this problem you've ingeniously proposed a solution. You gave them each an empty cup and told them:

”Look guys I will drink a cup and give you 2 cups of water. But, I'll fill only the first and the last cups put on the table before me. The intermediaries cups will remain empty”

enter image description here

Besides your main rule, you agreed upon the following terms:

  1. It's only you who can pour water
  2. The cups can be filled only if all of them are put .
  3. The cups should be put in a row (the first one is the head of the row and the last is the tail). We can assume that the pourer has marked the final cups positions (first place, second,.. last), so each cup should be placed in one of these positions.
  4. No timer will be used and the game doesn't have a timeout.
  5. It's up to you to determine who is the first depositor/winner in case they race to put the first cup (in the first position).
  6. You will act with honesty 🐧
  7. A guest can drink only from his cup

The question: In this context, how would your guests behave, if you know that they are smart and can cheat 😈 (but cannot kill each other 💀)? Would there be a good compromise avoiding a deadlock?

To make the situation more real let's assume that 2< N< 15.

$\endgroup$

closed as unclear what you're asking by Rand al'Thor, PiIsNot3, Glorfindel, Fil-let's GoFundMonica, hexomino Sep 16 at 16:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ So... what's the actual goal here? What's the question that you're asking? You ask "how do the guests behave", but that depends on what you do, and there's no goal for the distributor. What are the precise rules of the game - everyone puts their cup down at some point, and only the first and last get water? You say the guests can "cheat" -- how can they cheat? This question is very underspecified - I don't think any actual answer can be given, since the problem is so vague and major parts of it are completely left out. $\endgroup$ – Deusovi Sep 14 at 23:32
  • $\begingroup$ the goal here is to propose a wining strategy that will avoid the deadlock !! in a normal case if the first player puts his cup no one will put the second one as he will be a loser. only the first cup and the last cup will be filled. they can cheat in any way!! (for example you can suggest that they can just agree on some strategy but one guest can just cheat and not put his cup as agreed, etc.). $\endgroup$ – Badr Bellaj Sep 15 at 0:22
  • $\begingroup$ I think it might be helpful to have an explanation of the original distributed-systems problem. $\endgroup$ – Gareth McCaughan Sep 15 at 0:53
  • $\begingroup$ I was thinking that the original problem is probably more precisely posed, and that it might be easier to figure out what's going on in the "riddle" version with that as context. $\endgroup$ – Gareth McCaughan Sep 15 at 1:00
  • $\begingroup$ Some things that are unclear (to me, at present): 1. Do the cups have to be placed in order? That is, are the "first cup" and "last cup" necessarily the temporally first and last, or e.g. could the first thing that happens be that someone places their cup in the second position? 2. How do we reconcile "A guest can drink only from his cup" (in the Q) with "they all agree ... to share water" (in a comment to JS1's answer)? 3. Can cups be un-placed? 4. Can we assume that each guest is selfishly attempting to get water and doesn't care about the others? $\endgroup$ – Gareth McCaughan Sep 15 at 1:05
2
$\begingroup$

Partial Answer (if $N$ is even)

If $N$ is even, then:

They can form $\frac{N}{2}$ pairs, and they swap each other cup.

Now, this is the "regulation":

If someone successfully put his partner's cup on the first place, then his partner should put his cup on the last place.

This won't cause any deadlock because eventually:

Everybody will try to put his partner's cup on the first place to make sure his cup is also safe on the last place!

As:

If both players on a pair failed to put a cup on the first place, then to make sure his own cup will be on the last place is to place his partner's cup right away before his partner does it!

So:

The partner of the person who put the cup on the first place will wait calmly and successfully put the cup on the last place.

$\endgroup$
  • $\begingroup$ How about a minor adjustment: each person gets the cup of the next person in a cycle (works for all N). The strategy for all players is to put their cups in losing slots as fast as possible, to maximize the chance that their own cups will not be placed in a losing slot (similar to your step 4). Once all but the two (winning) slots are filled, the last two players must put their cups (which are not theirs) into the winning slots. $\endgroup$ – JS1 Sep 15 at 6:11
  • $\begingroup$ @athin your solution IMO doesn't solve the problem even if we suppose that players are honest (they will stick to the regulation). If the first player puts the cup so the loosers won't put their cup !! why because a pair of losers can agree to share the wining cup so they will compete for the last position and this will bring the deadlock again right? $\endgroup$ – Badr Bellaj Sep 15 at 9:13
  • $\begingroup$ @BadrBellaj Hmm... So sharing the winning cup is possible? But according #7, each guest should only drink from his own cup, cmiiw. $\endgroup$ – athin Sep 15 at 13:07
  • $\begingroup$ @JS1 Hey I guess that strategy should be doable.. You should write an answer :) (Though this doable is also in my opinion.. Now I'm not really sure after what OP said.. And now I'm not sure either with my own answer...) $\endgroup$ – athin Sep 15 at 13:09
  • $\begingroup$ @athin yes the rule 7 says so but that doesn't stop a guest to pour water from his cup to his partner's cup ;) $\endgroup$ – Badr Bellaj Sep 15 at 13:11
1
$\begingroup$

To the answer with the two teams and switched cup strategy. Now when they can cheat what prevents the second person from team first cup win to just place his partners cup before the last cup. Once his cup is at position one he doesn't need to care whatever his partner gets the last spot or not? I mean wouldn't that again produce a deadlock?

I'm also confused with how does this work so like there is a start and an end defined? Cause it seems there is no problem for the starting position? Which confuses me already because if there is only one spot for the first glass then do all let's say 15 guy's try to reach this spot first and fight over it who reached it first? If that's the case this should also work for the last space and after first and last space are defined the rest will fill up the other spots?

Or is it more of a who puts his glass down first wins scenario in which case all would try to put it down first so it would be easy to determine first and last.

Or is the last space not defined yet until all glasses are put down. In that case is it possible to do like a Filter system. For example the person that pours water says a number and people need to decide on higher and lower and the person who got the first spot decides then if Higher or lower wins. The winning group continues the losing group puts their cups down. Eventually there will be one person left and he will be the last.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.