# Question: consider a dinner table where n dining philosophers are seated...

###### Question details

Consider a dinner table where n dining philosophers are seated.
Each

philosopher has a plate of food; however, there is only a single
eating-utensil placed

in the center of the table. Eating is done at discrete rounds. At
the beginning of

each round, if a philosopher wishes to eat, she may attempt to
obtain the utensil

from the center of the table. If the philosopher obtains the
utensil, she eats for the

duration of the round (i.e., only one philosopher may eat during
any given round)

and then places the utensil back at the table center at the end of
the round. If

two or more philosophers attempt to obtain the utensil at the
beginning of the

same round, then no philosopher will eat during that round (i.e.,
no one obtains the

utensil); thus, if all the philosophers try to access the utensil
on every round, no

philosopher would ever eat.

One way to avoid the starvation of these philosophers is to use
randomization. A

possible simple randomized algorithm is to have each philosopher
attempt to obtain

the utensil at any given round with probability p > 0. Assume
that each philosopher

uses the same probability p.

a) What is the probability (in terms of p) that a philosopher is
able to successfully

eat during any given single round?

b) What value of p maximizes this probability?

c) Using the probability from Part b, what is the probability that
a philosopher

does not successfully obtain the utensil after k consecutive
rounds?

explain