The Smokers

Computer Science Level 2

To make a cigar, one needs three ingredients: paper, matches, tobacco.

  • Alice has an infinite supply of paper.
  • Bob has an infinite supply of matches.
  • Carol has an infinite supply of tobacco.

The dealer arbitrarily puts two ingredients on the table and the agents take them and combine with their own supplies to make a cigar and smoke it. The dealer again puts two arbitrary ingredients on the table when one of the agents has finished smoking.

Which of the two following ways should the agents desirably behave in?

(A) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
Alice:
    1. Wait until there are matches on the table - grab them.
    2. Wait until there is tobacco on the table - grab it.
    3. Make cigar. Smoke.
    4. Loop

Bob:
    1. Wait until there is paper on the table - grab it.
    2. Wait until there is tobacco on the table - grab it.
    3. Make cigar. Smoke.
    4. Loop

Carol:
    1. Wait until there are matches on the table - grab them.
    2. Wait until there is paper on the table - grab it.
    3. Make cigar. Smoke.
    4. Loop

(B) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
Alice:
    1. Wait until there are both matches and tobacco on the table - grab them both.
    2. Make cigar. Smoke.
    3. Loop.

Bob:
    1. Wait until there are both paper and tobacco on the table - grab them both.
    2. Make cigar. Smoke.
    3. Loop.

Carol:
    1. Wait until there are both matches and paper on the table - grab them both.
    2. Make cigar. Smoke.
    3. Loop.

(A) (B)

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Ivan Koswara
Oct 3, 2016

Assuming the dealer always puts two different ingredients.

In case A, it's possible that after the dealer puts two ingredients, nobody is currently smoking and thus the dealer never puts additional ingredients. For example, if the ingredients are matches and paper, and Alice grabs the matches before Carol does, then the paper will only be grabbed by Bob. Thus nobody has a complete set of ingredients to smoke yet, so nobody smokes, so the dealer doesn't continue. When nobody does anything, waiting for others to do something, this is called a deadlock .

In case B, only one person will ever be able to take the ingredients on the table, so there is no deadlock. One person will take both ingredients; they will smoke; and they will finish and notify the dealer to put more ingredients.

Whether case B is more desirable or not depends on whether you are a smoker or not (I personally prefer case A so nobody smokes because I don't like smoking). But for the purpose of this problem, case B is more desirable.

14 Helpful 1 Interesting 0 Brilliant 0 Confused

I thought the statement of the problem was ambiguous. Did the dealer put both items on the table together? Why would one person take both ingredients if one was already in his/her possession in infinite amount, and a cigar still could not be smoked? How are we supposed to know that the game is played like "Hands Down"?

Tom Capizzi - 4 years, 8 months ago

Log in to reply

It is not a game; it's a scenario, only that the words are poorly phrased (read: "the dealer") that it sounds like a game.

Three smokers are sitting on the table, wanting to smoke; they only have one of the three ingredients available and thus want the other two to be able to smoke. The table is supplied with two of the ingredients; this way, one of the smokers will be able to smoke. But this is not an easy matter if you're drugged from the smoking; the smokers should make sure that only one of the smokers take both ingredients, and not two smokers taking one ingredient each. You're presented with the two sets of algorithms that they use; it's your job to determine whether it's possible that the smokers reach to a dead end, after two smokers take one ingredient each.

Ivan Koswara - 4 years, 8 months ago

Log in to reply

The question might be flawed: If Alice has an infinite supply of paper, then how can the dealer put more paper on the table? Putting more paper on the table means be definition that Alice's supply was not infinite......

Y H - 4 years, 8 months ago

Log in to reply

@Y H – Infinite doesn't mean all. There are infinitely many integers, but I can still pick a real number that is not an integer.

Ivan Koswara - 4 years, 8 months ago

Nice and clear explanation. I also liked the humor :)

Agnishom Chattopadhyay - 4 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...