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