How to divide $n$ people into two groups to maximize the probability of finding a lost boy

Question

A small boy is lost coming down Mount Washington. The leader of the search team estimates that there is a probability $p$ that he came down on the east side and a probability $1 − p$ that he came down on the west side. He has $n$ people in his search team who will search independently and, if the boy is on the side being searched, each member will find the boy with probability $u$. Determine how he should divide the $n$ people into two groups to search the two sides of the mountain so that he will have the highest probability of finding the boy. How does this depend on $u$?

---

No idea where to start. The answer has couple $\log$s in it. That's from a chapter of the book where I've learned this: https://i.stack.imgur.com/sbGj0.png. Perhaps I'm supposed to use some kind of derivative over $p$ somewhere along the way? But then I can't really come up with what to differentiate.

Answer 1

This is a partial answer only.

If you send $k$ people to the $p$ side, the probability that the boy is not found is $$p(1-u)^k+(1-p)(1-u)^{n-k}$$ Hence the probability that the boy is found is $$f(k)=1-p(1-u)^k-(1-p)(1-u)^{n-k}$$

Therefore you need to find the maximum of the function $$f(x)=1-p(1-u)^x-(1-p)(1-u)^{n-x}$$

whose derivative is $$f^\prime(x)=-p\ln(1-u)(1-u)^x+(1-p)\ln(1-u)(1-u)^{n-x}$$

Now this vanishes when $$(1-p)(1-u)^{n-x}=p(1-u)^x$$ That is $$\frac{1-p}{p}(1-u)^{n}=(1-u)^{2x}$$ Taking logs $$\ln(\frac{1-p}{p})+n\ln(1-u)=2x\ln(1-u)$$ Finally $$x=\frac{1}{2}\left(n+\dfrac{\ln(1-p)-\ln(p)}{\ln(1-u)}\right)$$

Now this is probably not an integer, so you still need to find which of the two nearest integers is the best.

Answer 2

Let $f(k)$ be the probability of failure if the leader sends $k$ people to the east side and $n-k$ people to the west side. As explained in Arnaud Mortier's solution, $$f(k) = pv^k + (1-p)v^{n-k},$$ where $v = 1-u.$ Since $k$ is a discrete variable, we can minimize $f$ by comparing its values at successive values of $k.$

$$f(k) \le f(k-1) \Leftrightarrow pv^{k}+(1-p)v^{n-k}\le pv^{k-1}+(1-p)v^{n-k+1} $$ $$\Leftrightarrow pv^k-pv^{k-1} \le (1-p)v^{n-k+1}-(1-p)v^{v-k}$$ $$\Leftrightarrow pv^{k-1}(v-1) \le (1-p)v^{n-k}(v-1)$$ $$\Leftrightarrow \frac{p}{1-p} \ge v^{n-2k-1} \Leftrightarrow \frac{\log p -\log (1-p)}{\log v} \ge n- 2k -1$$ $$\Leftrightarrow k \ge \frac{n-1}{2} - \frac{\log p - \log (1-p)}{2\log(1-u)} $$ Since we want the largest value of $k$ for which this holds, we take $$k = \Big \lfloor \frac{n-1}{2} - \frac{\log p - \log (1-p)}{2\log(1-u)} \Big \rfloor$$

I would appreciate it if someone would improve the formatting of this answer. My MathJax skills are still rather rudimentary.