Finding Sample Size for a proportion hypothesis test I'm studying for a test and i got stuck at the following problem:
If a coin is being tested for honesty ($H_{0}: p = .5$) and we desire the test to fulfill the following conditions:
$P(\text{Reject } H_{0}|H_{0} \text{ is true}) \leq 0.05$
In other words, $\alpha$ (Error type I) must be equal or lesser than $.05$
$P(\text{Not reject $H_{0}$ when } |p -.5|\geq 0.1) \leq 0.05$
I understand this means we want a margin of error 0.1 with at least 95% confidence.
What's the minimum sample size we need to fulfill all these conditions and what's the rule of decision (Critical region)?
My doubt is really focused in this: I know we can isolate sample size in the margin formula as below, however as we do not know if the sample is sufficiently big so we can use a normal aproximation for the percentil, how can i use the available information to find the binomial percentile when $n$ is not known? 
$n = \frac{z_{\alpha/2}^{2}p(1-p)}{ME^{2}}$
EDIT: I found a way to deal with the problem without assuming normality. I'd like to know if this is a correct approach to it:
$P\left(\left| \frac{\hat{P}-P}{\sqrt{P(1-P)/n} } \right| \geq x \right) \leq 0.05$
$P\left(\left| \hat{P}-P \right| \geq x\sqrt{P(1-P)/n} \right) \leq 0.05$
Now, we know the formula to the error margin thus we can substitute the term inside the probabilty by the desired value
$P\left(\left| \hat{P}-P \right| \geq 0.1 \right) \leq 0.05$
My idea now is apply Chebyshev's Inequality as $P = E(\hat{P})$
$P\left(\left| \hat{P}-P \right| \geq 0.1 \right) \leq \frac{P(1-P)}{n 0.1^{2}} = 0.05$
When $H_{0}$ is true we have $p = .5$ so substituting,
$P\left(\left| \hat{P}-P \right| \geq 0.1 \right) \leq \frac{.5^{2}}{n 0.1^{2}} = 0.05$
Isolating $n$ in the equality in the right side so we satisfy the initial restriction
$n = \frac{.5^{2}}{.1^{2}.05} = 500$
Is this correct? Thanks for the attention.
 A: The probability 
$$P(\text{Not reject }\mathcal{H}_0 \text{ given } |p - 0.5| \ge 0.1) \le 0.05$$
Is the type II error rate. In this case, 1 minus that probability is the power. Therefore, it is a sample size calculation to achieve a power of 0.95 or greater with an effect of $p \ge 0.6$ or $p \le 0.4$. 
The 0.1 is not a margin of error. A margin of error applies to an estimate. However, you are referring to the truth (data generating mechanism) which has no margin of error (it isn't random). To calculate the minimum sample size, you have to choose the most conservative value, which as stated is 0.6 (or 0.4 which is WLOG equivalent).
This is nice, because formulated thusly, we can use off-the-shelf power calculators to calculate minimal sample size to achieve a desired power. The pwr package uses the 1988 Cohen transformation for a one-sample test. We can also check with simulation:

pwr.p.test(h=ES.h(0.5,0.6), sig.level=0.05, power=0.95)

gives:
 proportion power calculation for binomial distribution (arcsine transformation) 

          h = 0.2013579
          n = 320.5008
  sig.level = 0.05
      power = 0.95
alternative = two.sided

Which is much more conservative than your n=500 finding. Checking with simulation:
set.seed(123)
n <- 320
p <- 0.6
SIMS <- rbinom(10000, n, p)
SIMS <- cbind(SIMS, n-SIMS)
SIMS <- apply(SIMS, 1, function(x) chisq.test(x)$p.value)
mean(SIMS < 0.05)

gives
> mean(SIMS < 0.05)
[1] 0.9499

Which is as stated. The important thing is that with $N=300$ (or even much smaller), the asymptotic sampling distribution of the sample mean is very close to normal. Using our SIMS data from above, you can see:

