Problem source

\begin{questionparts}
\item Sketch a graph of $y = x^{\frac{1}{x}}$ for $x > 0$, showing the location of any turning points.
Find the maximum value of $n^{\frac{1}{n}}$, where $n$ is a positive integer.
\end{questionparts}
$N$ people are to have their blood tested for the presence or absence of an enzyme. Each person, independently of the others, has a probability $p$ of having the enzyme present in a sample of their blood, where $0 < p < 1$. The blood test always correctly determines whether the enzyme is present or absent in a sample.
The following method is used.
\begin{itemize}
\item The people to be tested are split into $r$ groups of size $k$, with $k > 1$ and $rk = N$.
\item In every group, a sample from each person in that group is mixed into one large sample, which is then tested.
\item If the enzyme is not present in the combined sample from a group, no further testing of the people in that group is needed.
\item If the enzyme is present in the combined sample from a group, a second sample from each person in that group is tested separately.
\end{itemize}
\begin{questionparts}
\setcounter{enumi}{1}
\item Find, in terms of $N$, $k$ and $p$, the expected number of tests.
\item Given that $N$ is a multiple of $3$, find the largest value of $p$ for which it is possible to find an integer value of $k$ such that $k > 1$ and the expected number of tests is at most $N$.
Show that this value of $p$ is greater than $\frac{1}{4}$.
\item Show that, if $pk$ is sufficiently small, the expected number of tests is approximately
\[ N\!\left(\frac{1}{k} + pk\right). \]
In the case where $p = 0.01$, show that choosing $k = 10$ gives an expected number of tests which is only about $20\%$ of $N$.
\end{questionparts}

Solution source

\begin{questionparts}
\item $\,$ 
\begin{center}
    \begin{tikzpicture}
    \def\functionf(#1){exp(1/(#1)*ln(#1))};
    \def\xl{-1.5}; 
    \def\xu{20.5};
    \def\yl{0}; 
    \def\yu{2};
    
    % Calculate scaling factors to make the plot square
    \pgfmathsetmacro{\xrange}{\xu-\xl}
    \pgfmathsetmacro{\yrange}{\yu-\yl}
    \pgfmathsetmacro{\xscale}{10/\xrange}
    \pgfmathsetmacro{\yscale}{10/\yrange}
    
    % Define the reusable styles to keep code clean
    \tikzset{
        x=\xscale cm, y=\yscale cm,
        axis/.style={thick, draw=black!80, -{Stealth[scale=1.2]}},
        grid/.style={thin, dashed, gray!30},
        curveA/.style={very thick, color=cyan!70!black, smooth},
        curveB/.style={very thick, color=orange!90!black, smooth},
        curveC/.style={very thick, color=green!90!black, smooth},
        curveBlack/.style={very thick, color=black, smooth},
        dot/.style={circle, fill=black, inner sep=1.2pt},
        labelbox/.style={fill=white, inner sep=2pt, rounded corners=2pt} % Protects text from lines
    }
    
    % Draw background grid
    \draw[grid] (\xl,\yl) (\xu,\yu);
    
    % Set up axes
    \draw[axis] (\xl,0) -- (\xu,0) node[right, black] {$x$};
    \draw[axis] (0,\yl) -- (0,\yu) node[above, black] {$y$};
    
    % Define the bounding region with clip
    \begin{scope}
        \clip (\xl,\yl) rectangle (\xu,\yu);

        
        \draw[curveA, domain=.001:\xu, samples=150] 
            (0,0) -- plot ({\x},{\functionf(\x)});

        \filldraw ({exp(1)}, {exp(1/exp(1))}) circle (1.5pt) node[above] {$(e, e^{1/e})$};

    \end{scope}
    
    % Annotate Function Names
    % \node[curveB, labelbox] at (1.85, -1.1) {$x = \frac{4y^2+1}{3}$};
    

    \end{tikzpicture}
\end{center}


\begin{align*}
&& y & = x^{1/x} = \exp \left ( \tfrac1x \ln x \right ) \\
\Rightarrow && y' &= \exp \left ( \tfrac1x \ln x \right ) \cdot \left ( \frac{1}{x^2} - \frac{\ln x}{x^2} \right ) \\
&&&= \frac{\exp \left ( \tfrac1x \ln x \right ) }{x^2}(1 - \ln x) \\
y' =0: && x &= e 
\end{align*}
Therefore the largest integer values will be $2$ or $3$. Comparing $(2^{\frac12})^6 = 8 < 9 = (3^{1/3})^6$ we see the maximum value of $n^{1/n}$ where $n$ is an integer is $\sqrt[3]{3}$

\item The number of tests is $r$ plus however many groups fail times $k$. The probability of a group failing is $g = 1-(1-p)^k$ and the number of failing groups is $\sim B(r, g)$ so the expected number of additional groups is $rg$ and the expected total number of tests is
\[ \frac{N}{k} + N(1-(1-p)^k) \] 

\item $\,$ \begin{align*}
&& N &\geq E = \frac{N}{k} + N(1-(1-p)^k) \\
\Rightarrow && 1 &\geq \frac{1}{k} + 1-(1-p)^k \\
\Rightarrow && (1-p)^k &\geq \frac1k \\
\Rightarrow && k \ln(1-p) &\geq - \ln k \\
\Rightarrow && \ln(1 - p) &\geq -\frac{1}{k} \ln k \geq -\frac13 \ln 3 \\
\Rightarrow && 1-p &\geq \frac{1}{\sqrt[3]{3}} \\
\Rightarrow && p &\leq 1-\frac{1}{\sqrt[3]{3}}
\end{align*}
(taking $k=3$)

Claim: $1 - \frac{1}{\sqrt[3]{3}} > \frac14$

Proof: This is equivalent to $\sqrt[3]{3} > \frac43$ or $81 > 4^3 = 64$ which is clearly true.

\item If $pk$ is small then $(1-p)^k \approx 1 - pk$ and so we obtain $N \left ( \frac1k +pk \right)$ as required.

If $p = 0.01$ and $k = 10$ then $\frac{1}{10} + 0.01 \cdot 10 = 0.2$ so the expected number of tests is $\sim 20\%$ of $N$
\end{questionparts}