Competition problem — Combinatorics

Library / /172 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

King Arthur has two equally wise advisors - Merlin and Percival. Each of them finds the right answer to any question with a probability of $p$ or the wrong answer - with a probability of $q=1-p$ .

If both advisors say the same thing, the king listens to them. If they say the opposite, the king makes a decision by flipping a coin.

One day, Arthur wondered - would the probability of making correct decisions not decrease if he kept only one advisor and listened to him? So the king summoned the advisors and said:

- It seems to me that the probability of making correct decisions will not decrease if I keep only one advisor and listen to him. If this is true, I will have to dismiss one of you. If this is not true, I will leave everything as it is. Answer me, should I dismiss one of you?
- Who exactly are you planning to dismiss, King Arthur? - the advisors asked.
- If I decide to dismiss one of you, I will make the choice by drawing lots, flipping a coin.

The advisors left to think about the answer. The advisors, I repeat, are equally wise, but not equally honest.

Percival is very honest and will try to give the correct answer, even if it means he will be dismissed. Merlin, honest in all other respects, in this situation decides to give an answer that minimizes the probability of his dismissal. What is the probability that Merlin will be dismissed?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let's consider whether the counselor should be dismissed. If there is only one counselor, the king, following his advice, will make the right decision with a probability of $p$ on any issue.

What happens when there are two counselors? The probability that both of us give the correct answer is $p^{2}$ . In this case, the king will make the correct decision with a probability of 1. If both counselors are wrong (with a probability of $q^{2}$ ), the king will make the correct decision with a probability of 0. Finally, if the counselors disagree (with a probability of $2 p q$ ), the king will choose the correct decision with a probability of $1 / 2$ . By the law of total probability,

$P($ the king makes the correct decision $)=p^{2}+2 p q \cdot 1 / 2=p(p+q)=p$ .

Thus, one of the counselors should be dismissed.

If I say "Yes, dismissal is necessary," there are two scenarios.

1) Percival will also say "Yes" with a probability of $p$ , and then the king will dismiss me with a probability of $1 / 2$ .
2) Percival will be wrong (with a probability of $q$ ), and then the king will make a decision by flipping a coin. If he decides to dismiss someone (with a probability of $1 / 2$ ), it will be me again with a probability of $1 / 2$ .

Thus, $P($ I will be dismissed if I say "Yes" $)=1 / 2 p + 1 / 4 q$ .

If I say "No, dismissal is not necessary," there are again two cases.

1. Percival will say "Yes" (with a probability of $p$ ), and then the king might dismiss me by flipping a coin twice (probability \& \& №188;
2) Percival will be wrong (with a probability of $q$ ), and then the king will dismiss no one, as we will say the same thing.

Thus, $P($ I will be dismissed if I say "No" $)=1 / 4 p$ . Clearly, $1 / 4 p < 1 / 2 p + 1 / 4 q$ . Therefore, I should say "No."

By the problem's condition, Merlin will find this answer with a probability of $p$ , and with a probability of $q$ Merlin will be wrong and therefore

!
$p^{2} + 1 / 2 p q + 1 / 4 q^{2} = 1 / 4$ .

## Answer

$1 / 4$ .

Submit a comment

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.