An intuitive example for why sample size is maximum when probability is 0.5 In computing sample size for qualitative research (e.g. a confidence interval for an estimated proportion) as follows:

$$n=\frac{Z^2P(1-P)}{d^2}$$


\begin{eqnarray}\text{where  }\,n&=&\text{ sample size,}\\  
 Z&=&\text{ Z statistic for a level of confidence,}\\
 P&=&\text{ expected prevalence or proportion}\\
  & &\,\text{(in proportion of one; if }20\%,\, P=0.2\text{), and}\\
 d&=&\text{ precision}\\
  & &\,\text{(in proportion of one; if }5\%,\: d=0.05\text{).}\\
\end{eqnarray}

(cited from Naing et al, 2006 [1])
Mathematically I understand when $P = 0.5$, the required sample size ($n$) is maximum. However, to convince myself in reality, I cannot find any intuitive example to prove that.
Does anyone have any examples to demonstrate that?
[1] Naing, L., T. Winn, B.N. Rusli (2006),
"Practical Issues in Calculating the Sample Size for Prevalence Studies"
Archives of Orofacial Sciences; 1: 9-14
(pdf here: citeseer)
 A: I'm not sure quite what you're after with an "example" since we're dealing with a mathematical fact about an unobservable (population) quantity -- the variance of a sample proportion is a population quantity which varies from sample to sample -- to show that it changes "in an example" we'd need to have many samples at different values of $p$ but holding $n$ constant (i.e. use sample variances across many sets of samples to show us what's happening with population variances of sample proportions); this suggests looking at simulated samples.
However, since you requested an intuitive example I will begin with some intuition before proceeding with what we can glean from simulation.
Intuitive explanation: If the population proportion is close to 0, then the sample proportion cannot ever be very much lower than it (because the sample proportion cannot be less than 0). Consequently, at the same time it should usually not be much larger either (because if it was typically much larger when it was larger, it would be wrong on average, but we know that the expected sample proportion is the population proportion). So the presence of the lower boundary at 0 forces the variance to be small in that region. Similarly the boundary at 1 forces the variance to be small in that region. In the middle, however, the sample proportion has plenty of "room", without getting squished up against a hard boundary.
Simulation example: Note that the aim is to get the half-width (a.k.a. "margin of error") of a confidence interval to no larger than a specified size.
When the variance of a quantity of interest is larger, it then takes a larger sample size to identify it down to that specified accuracy.
The sample size is largest when $p=0.5$ because the variance of a $\text{binomial}(n,p)$ is $\frac{_1}{^n}\cdot p(1-p)$. So the effect of $p$ is through that term $p(1-p)$. If $p$ is near $0$ or $1$ then you have a product of a small term and one near $1$ -- so the result is small, but near $\frac12$ both terms are relatively big and the product is large, being maximized right at the middle.

This makes the variance of the sample proportion larger. Here we have simulated binomial proportions -- each pale grey point (many are overlapping so I have made them partly transparent) on the plot is the sample proportions from a simulation of many samples of size 10 from the binomial with the indicated population proportion $p$ in $(0.05, 0.2, 0.5, 0.8, 0.95)$:

where we can see the spread is smaller near the ends and wider in the middle. 
Now let's look at sample variances from such sets of simulations. In the plot that follows, each point on the plot is the sample variance of ten binomial proportions (each of size 10) at the specified population proportion ($p$) (that is each small circle shows the sample variance from 10 grey points at a given $p$ like those in the plot above):

As we see that on average the variance at each value of $p$ is following that quadratic shape and the typical variance really is larger in the middle.
A: What you are looking for is the proof that p*(1-p) is maximum when p=0.5 for p in the interval [0,1], meaning: p + ( 1 - p ) = 1.
That has nothing to do with probabilities, is a maximum/minimum of a function problem.
Graphically you can just plot it to see it.
If you want an analytical solution, then you have: 

y(p)=p*(1-p)

you must calculate first derivative, that indicates the change of the function:

y'(p)= (1-p)+ p (-1) = 1 - 2 * p

We want to know when it is zero, so where it changes from positive to negative, what indicates a maximum,( or inversely for a minimum):

0 = 1 - 2 * p  ==> p = 1/2

If you want to be very formal, you must calculate second derivative:

y''(p) = -2

what confirms that the singular point we found is a maximum because the second derivative in the point y''(1/2)=-2 is negative.
