Another p-value fallacy Wikipedia examples say that a coin is unfair if it generates a sequence 1111111. A high alternation rate, such as 1010101010, would be similarly unfair. 
What is a fallacy to think that a coin is unfair on the grounds that it is equally improbable to see any sequence? 
I mean that it is normally "resolved" by stating the fact that P(11111111) = P(00000000) = P(01010101) = P(10101010) = P (010101000) = P(any other sequence). This explains that the coin is fair. But, I interpret it as there cannot be any fair coin just because of identity of all probabilities and because P(all ones) = P(any sequence) etc, all being highly improbably. 
Now, we have that fair coin cannot be fair. Where is the fallacy and how to apply the p-test properly?
edit The hypothesis is that the coin is fair and statistic is the probability of occurring the sequence. I can compute the probability of occurred sequence from the hypothesis. For any sufficiently long sequence, the theoretical probability is too low and, therefore, fairness must be rejected. Where is the fallacy?
edit2 Why nobody can simply say that the pitfall is pointed out in the first Wikipedia example: p-criteria does not take the sample size into account? I can even trivialize the problem. Forget the series. Let's evaluate the probability of picking a single item38 under assumption of uniform 0-100 distribution. Obviously, it is 1%, which is sufficiently low to be picked by chance. But, statistics shows that item appears in 100% of the cases (1 time per 1 experiment). This obviously cannot be by chance, according to p-level test, yet, sample size is also insufficient. So, p-test must be complemented by sample size analysis. It is a fallacy to forget this. Right?
A related question: which distribution will have the probability of picking item38 if I draw multiple samples? How do I take the integral of "extreme cases"?
 A: A test procedure goes like this:
(1) Define the sample space:  1024 outcomes of tossing a coin 10 times
(2) State the null hypothesis: A fair coin; i.e. $\mathsf{H}$ & $\mathsf{T}$ equiprobable, tosses independent
(3) Define a test statistic: You can use the sum of heads, or the number of runs, or whatever you like
(4) Perform the experiment & calculate the observed value test statistic: Toss the coin 10 times
(5) Calculate the probability (under the null hypothesis) of getting a value of the test statistic greater than or equal to the observed one.
The result from (5) is the p-value. It lets you calibrate the test statistic.  Suppose the null hypothesis were indeed true:  if you were to follow this test procedure many times & reject the null hypothesis (wrongly) every time you got a value of the test statistic this big or bigger, you'd reject it (wrongly) a fraction $p$ of the many times.
The tricky part is (3). What's right about your intuition is that every particular sequence can be seen as favouring some alternative or other against the null—there are so many different ways a coin can be unfair. But you have to choose a test statistic that gives you some discrimination. The count of heads is a good one if you want to test whether the probability of heads is different to one-half, & are not so doubtful of independence.  The count of runs of the same side up is a good one if you're more concerned about independence.  If someone tells you they're going to toss $\mathsf{HHTHTHHHTT}$ then to test their ability you can let your test statistic equal one when just that sequence arises, and zero otherwise.  What you can't do is look at a particular sequence after the experiment, say it would have been extremely improbable according to some test statistic or other, & quote a p-value based on that.
[In response to your comment:
(a) The p-value of $\mathsf{HHTHTHHHTT}$ is not in general $\frac{1}{1024}$, but depends on the test statistic being used. If the count of heads is being used as the test statistic (as it is when the alternative of interest is that the probability of heads is greater than $\frac{1}{2}$), the more extreme cases are counts of 7, 8, 9, & 10, & the probabilities of these counts would be summed into the p-value. I gave an example of someone's saying they intended to toss $\mathsf{HHTHTHHHTT}$, & in this case, but certainly not in all cases, it would be sensible to define the test statistic such that $\mathsf{HHTHTHHHTT}$ was the most extreme value.
(b) You can calculate what probabilities you like before & after the experiment, but valid p-values are derived from a test statistic defined beforehand, or at any rate independently of the observed results. If you choose your test statistic depending on the observed results, you're following a different procedure from the one described above, & the interpretation in terms of error rates over hypothetical repetitions—which is the whole point of introducing p-values—will no longer be relevant.
(c) I can't follow your argument on sample size at all. An exact p-value will be valid regardless of sample size.]
A: I don't think this is anything to do with P-values. In any case you nowhere specify what test you have in mind. 
The usual definition of a fair coin I take to be that heads and tails are equally probable, but nothing rules out "fairness" being a vague concept that can be made precise in several ways. In practice one should also be wary of -- to take one example -- perfect alternation between heads and tails and suspect the coin -- or more to the point perhaps, the machine or person tossing it. Other kinds of regularity can also be imagined. 
In that case, the thing to do is to set up a test specific to that kind of behaviour and calculate P-values (or preferably some kind of confidence interval for a key parameter). Alternatively, go as Bayesian as you want. 
So, I don't see anything here except the idea that the wrong question can give you an irrelevant answer. 
A: What's the implicit model?
The probability p = 1/1024 is derived from the fair coin model of $\Pr(H)=\Pr(T)=0.5$ with independent throws, i.e. $Cov(n_i,n_{i-1})=1$. Note that this model is invariant to the sequence of throws, i.e. $\Pr(HHT)=\Pr(HTH)=\Pr(THH)$.
Under this model, a sequence such as HTHTHTHT is suspect, because it violates the second condition - the sequence of throws doesn't display independence.
However, OP asks why we shouldn't consider any n-tuple to be suspect, as the probability of any n-tuple is $1 \over2^n$, which for $n>5$ is below the "traditional" cut-off of $p<0.05$. What OP fails to recognize in this question is that he is using a model of individual throws to model the p-value of n-tuples.
In my opinion, the appropriate model is $H_0:\Pr(T_{k,i})=\Pr(T_{k,j}) \forall i,j$ versus $H_A:\exists i,j: \Pr(T_{k,i}) \neq \Pr(T_{k,j})$, where $T_{k,i}$ is the i'th k-tuple. This follows a multinomial distribution with k outcomes, and the test statistic can be derived.
A: On the chance of misunderstanding you, I will guess about what you might mean.
I guess your hypothesis is that the coin is fair, right? 
And your problem is how to test this if, in fact, all sequences by themselves have the same probability to occur. However when we are talking about p-values, this usually doesn't matter. At least not for the coins minted from the central bank of statistics books, if you will.
Well, if the coin if fair then we can (for example) assume that the throw is a random experiment which is Bernoulli distributed. If we assume that, then we can state that the result of "1111111..." is a result of a n-Binomial distribution of n throws of that coin.
And our hypothesis is then that the experiment, throwing the coin n-times with k successes stems from a binomial probability distribution. In this case, k=the amount of "1" we got, or our successes.
So we can test the hypothesis and we will see that it is highly unlikely to achieve the amount of successive "1" we got.
In fact the probability for this is NOT equal to all other sequences, since we are looking at the amount of successes with the binomial distribution. In fact the fact that the "1" are successsive doesn't matter for us. The order doesn't matter and therefore the probability of a sequence doesn't matter.
A binomial distribution with p=0.5 will have the most likely event that there are just as many heads as there are tails.
Like so, where in 15 throws the most "expected" outcome is 7.5:

This way, we could pretty accurately deny the hypothesis that the coin is fair and there would be no fallacy by using a simple binomial test.
http://en.wikipedia.org/wiki/Binomial_test
Your confusion seems to stem from the assumption we are testing not the amount of heads but rather the sequence. In this case you would be right: Every sequence is equally likely. But there are many more of these sequences that generate k throws with "1" if k is smaller than n, so with our fair coin we assume to have, our series of only "1" is unlikely precisely BECAUSE all throws have the same probability to go "1" or "0"
