No, they don't!!

Multumesc pentru evidentierea greselii din demonstratia trecuta. Voi credita cei 1500 de ron dupa cum am promis.

Insa am corectat demonstratia, si cea actuala este corecta si completa. Am pus la bataie inca 1400 de ron pentru cine imi evidentiaza primul o greseala majora in ea.

http://informatica-computer-science.blogspot.com/2012/03/variatie-pe-tema-gamblers-ruin.html

Remember furnicuta? [Probabilitatea unui random walk infinit]. I was vindicated: Pentru orice 0<p<1, probabilitatea ca furnicuta sa nu cada niciodata in prapastie la pozitia 0, este FIX 0, indiferent de p, daca facem niste asertii foarte firesti (intuitive) despre spatiul probabilistic in care formalizam problema!
That meens, I WAS RIGHT, and EVERYBODY ELSE (incluzand Radu Berinde, Andrei Grigorean, precum si unii studenti post-doctorali si profesori chiar) WERE WRONG!

Va rog si va provoc sa ma ajutati sa descopar greseala in demonstratia de mai jos. Ofer 1500 de ron primului care ma convinge ca e gresita (tineti minte ca pe un alt pariu cu Radu Berinde am achitat suma cand m-a convins de o o greseala in alta demonstratie) sau depisteaza o eroare fundamentala in ea.

http://informatica-computer-science.blogspot.com/2012/03/variatie-pe-tema-gamblers-ruin.html

Another tweet: What is the probability of a given input file?If you assume uniform distribution, just ignore the input and output 134217728.

Keeping this under a tweet, Cosmin, what is the maximum allowed program (code) size? If unlimited, the problem can be answered precisely.

How good is the estimate in what case? Worst case? Best case? Expected case?
And what do you mean by 'good'? Absolute error? Absolute positive error? Error margin with a certain % of confidence?
And in the case of any answer implicating probabilities, are there any assumption about the kind of input files to be expected? Or are all 1GB 0,1 strings equally probable?
Also, do the 1024 bytes imply any limit on code size, or could I potentially include 1 GB of precomputed values in the source code? If there is no limit on the size of the source code, the problem becomes meaningless, since it can be answered precisely, with just 1 bit of writable extra space.
In case you are not allowed an unreasonable code size, I don't think you can have any 'good' estimate for when there are significantly more distincts than can be represented as a set in 1024 bytes. I tend to believe the best you can hope for is to be able to say 'there are more than x distincts' for a very small x. I think you have to actually represent them somehow; after thorough reflection I tend to find it unlikely you can gain any useful information by 'seeing' a new number without having a representation of all that you have seen up until that point. Without any statistical particularities of the input file, the best you can achieve is 1 bit / stored number, so you can store no more than 8192 numbers. Thats 2^13. There can be as many as 2^27 distincts. So, even if you're lucky and manage 1 bit / number, your error will be huge (up to 99.99389%). It is likely that you will do much less than 1 bit / number, unless you plan on getting lucky.

In case one cares about worst-case positive error (so underestimate the number of distinct integers by the least possible amount) with 100% confidence, the problem is reduced to finding a cute data structure that can represent the highest number of 64-bit distinct integers, that can fit in 1024 bytes and can be updated by exposing it to a 8 byte number. A lot of interesting ideas come to mind. Mine are essentially based on a 'compacted' trie and some counters.

Also, keep in mind that the number of distinct integers that a data structure can store can depend on the actual distribution of the integers it is exposed to! So the actual sampling from the input file could matter. This can easily be randomized however (the sampling), or you could do even cuter things to make sure your structure tries to count as many distinct integers as it possibly could, regardless of how they are ordered in the input file.

Here are a few other interesting observations:
 - An input file from the problem statements' point of view is equivalent to a partition of the number 2^64 into at most 2^27 components.
 - So for any correct answer r, there are around (2^64)^(r-2) possible choices of r distinct integers: http://en.wikipedia.org/wiki/Partition_(number_theory)#Asymptotics_of_restricted_partitions . So, a particular configuration can be represented using around 64^(r-2) bits.
 - In case you don't 'cheat' by keeping any information regarding the input file in the actual code, essentially your program will be (at most) a finite automata with 2^(1024* states and 2^64 maximum possible transitions from each state and each state must represent a result.
 - So, there are 64^2048 possible states. Each state has to be mapped to a possible result in 1..2^27.
 - Transition from a state representing a result r to a state representing r+1 by exposing the automata to a 64 bit number implies that it should somehow be able to discern based on 1024*8 state bits between the 2^(64^(r-3)) cases when the 'new number' is a duplicate and the remaining  2^(64^(r-2)) - 2^(64^(r-3)) cases when it's not. So even if r is a small 100,003, the share magnitude of 64^100000 compared to 8192 is just overwhelming and a sufficient argument to support the case that no good approximation is possible.
 - So, with a limited program size and so little memory space I think a strategy that is almost as good as the best strategy is to ignore the input file completely and just answer with the expected number of duplicates in 2^27 64-bit numbers .

Dap, e chiar cool: F1(w)  F2(F1(w) w)  w! Nu doar ca arati ca exista overlap, il si gasesti si, dupa introducerea mea verbose, demonstratia ia 20 de caractere! Si da, cheia sta nu doar in cate variante pot fi acoperite de F2..FN ci si in maniera in care se interconditioneaza (in cazul asta F1 si F2).

Totusi ce ma surpinde este cum am putut sa emit 3 documente despre care sa fiu increzator ca reprezinta demonstratii complet si corecte a ceva and yet be wrong! Si mai ales ca unele contineau scapari triviale si evidente (gen sa impart la N-1 si nu la N). Something about my revision and QA process needs to be improved. I need to find out what! I will reflect on this further...  Si hey, am aflat asta cu doar 100$.

[So, for any possible challenge, player 1 answers correctly for at least some vector also answered correctly by some player i > 1.]

Ok, this is "IT"... the final (and successful) attempt at a complete and correct proof:

Assume without loss of generality that Player 1 has less information, seeing just N-2 other numbers. Also, assume, in our favor, that he doesn't see player 2's number always, and that they all know this.

What the N player have to do now is come up with N distinct strategy functions F1..FN, such that Fi(w) is the number player i answers when he sees w:
F1: {1..N}^N-2 -> {1..N}
F2: {1..N}^N-1 -> {1..N}
F3: {1..N}^N-1 -> {1..N}
..
FN: {1..N}^N-1 -> {1..N}

Proof is by contradiction: Assuming there exists such a set of strategies, F1..FN:

Let R(i) be the set of input vectors v, for which player i answers correctly when exposed to v|i.
Let C_i(x) be the set of input vectors v on which player i correctly answers (under the strategy Fi) by saying x.
Let D_i(w) be the set of all v, such that v is in C_i(F_i(w)) - i.e. player i answers correctly for such a v when exposed to w.
Note that R(i) = U (D_i(w)) for all w in F_i's domain.
What is the maximum size of R(i)?
For all w, there are precisely N "originating" v vectors. Since player i only sees w, it can respond correctly to AT MOST one of these vectors (since they all have different v[ i ] values). So |D_i(w)| <= 1. There are N^(N-1) potential w vectors, so |R(i)| <= N^(N-1) for all i=2..N and all conceivable strategies Fi.

In the case of player 1 things are as follows:
Since the strategy is deterministic, whatever he answers to a challenge w, he will be wrong at least N*(N-1) times:
For every w, there are N^N/N^(N-2) = N^2 possible v-s, as follows:
N where v[ 1 ] == 1.
N where v[ 1 ] == 2.
...
N where v[ 1 ] == N.

So, for any F1(w), it will be wrong on N-1 lines above ( N*(N-1) v-s) and right on exactly one (N v-s). In total, F1(w) will be right on at most N*N^(N-2) = N^(N-1) input vectors. This upper limit NEEDS to be reached (otherwise the correct number of covered vectors will be less than N*N^(N-1) = N^N, so at least on vector will not be covered). It can be reached (for example by answering with a constant) but if v1 is in D1(w) it MUST follow that any v such that v|2 == v1|2 is also in D1(w). So, |D1(w)| = N for any w (since it can be no greater than N, no less than N). |R(i)| <= Sum (|D1(w)|) = N^(N-1), with equality only if all D1(w) are pair-wise disjoint. Since R(i) must be precisely N^(N-1) all D1(w) must be disjoint.

Let's examine how this changes things for the remaining players.
If |R(1)|=N^(N-1) it follows that the remaining N players must correctly cover N^N - N^(N-1) = (N-1)*N^(N-1) distinct vectors, NOT ALSO COVERED BY PLAYER 1. Since there are N-1 remaining players, and R(i) <= N^(N-1) it follows all that R(i) = N^(N^1) so that all players guess correctly for some v for any w of the input domain of F_i, AND ALL R(i) are pair-wise disjoint.
Note that for players 2..N, |D_i(w)|=1. Since R(i) = N^(N-1) and there are N^(N-1) possible w-s, they are also disjoint.

For any w an N-2 element vector challenge for player 1:
Say F1(w) = x. Then D1(w) = {x?w | for ? = 1..N} = {F1(w)1w, F1(w)2w, ..., F1(w)Nw}. So |D1(w)|=N, for any w. Let r(x) = The number of distinct w's such that F1(w)=x. r(x) <= N^(N-2). Since |R(i)|=r(1)+..+r(N)=N^(N-1) => r(x) = N^(N-2) for all x.

For some player i>1,
R(i) = {a b v | Fi(abv|i) = v[ i ])}. Let RT = R(2) u R(3) u .. u R(n). Then |RT| = (N-1)*N^(N-1).
Then (N-1)*N^(N-1)/N <= RT|2 or (N-1)*N^(N-2) <= RT|2 //Because for each element in RT can be obtained from some element RT|2 by specifing some value for position 2.
Let A(y) = {v | v belongs to RT|2 and v[ 1 ]=y}. |A(y)| <= N^(N-2). Since, (N-1)*N^(N-2)=|RT|2| <= |A(1)| + .. + |A(N)| then |A(y)| = N^(N-2) for all y.
So, for any N-2 element vector w, the vector y w belongs to A(y).

So for any challenge w for player 1, F1(w) w belongs to A(F1(w)) => there exists k, such that F1(w) k w belongs to RT. Since D1(w)={F1(w) k w} for all possible k => D1(w) Intersect RT <> Empty.
So, for any possible challenge, player 1 answers correctly for at least some vector also answered correctly by some player i > 1.
Since this contradics a prior result, it means the initial assumption that a feasible strategy exists must be wrong.
Thus, there exists no feasible strategy. qed.

Just for your info:
We have also shown the stronger result that Player 1 overlaps, in total, on at least N^(N-2) occasions.

Da, asa este. Postasem mai mult pentru ceva in legatura cu un agreement cu Radu .
Inca nu e completa si corecta. So, da. You needn't waste time on it.

[for all such w, at least one vector based on w will be correctly answered by both player 1 and player i.]

Here's an embellished Part 2 proof that is correct and complete:

Assume without loss of generality that Player 1 has less information, seeing just N-2 other numbers. Also, assume, in our favor, that he doesn't see player 2's number always, and that they all know this.

What the N player have to do now is come up with N distinct strategy functions F1..FN, such that Fi(w) is the number player i answers when he sees w:
F1: {1..N}^N-2 -> {1..N}
F2: {1..N}^N-1 -> {1..N}
F3: {1..N}^N-1 -> {1..N}
..
FN: {1..N}^N-1 -> {1..N}

Proof is by contradiction: Assuming there exists such a set of strategies, F1..FN:

Let R(i) be the set of input vectors v, for which player i answers correctly when exposed to v|i.
Let C_i(x) be the set of input vectors v on which player i correctly answers (under the strategy Fi) by saying x.
Note that R(i) = U(C_i(x)) for x = 1..N.
Let D_i(w) be the set of all v, such that v is in C_i(F_i(w)) - i.e. player i answers correctly for such a v when exposed to w.
Note that R(i) = U (D_i(w)) for all w in F_i's domain.
What is the maximum size of R(i)?
For all w, there are precisely N "originating" v vectors. Since player i only sees w, it can respond correctly to AT MOST one of these vectors (since they all have different v[ i ] values). So |D_i(w)| <= 1. There are N^(N-1) potential w vectors, so |R(i)| <= N^(N-1) for all i=2..N and all conceivable strategies Fi.

In the case of player 1 things are as follows:
Since the strategy is deterministic, whatever he answers to a challenge w, he will be wrong at least N*(N-1) times:
For every w, there are N^N/N^(N-2) = N^2 possible v-s, as follows:
N where v[ 1 ] == 1.
N where v[ 1 ] == 2.
...
N where v[ 1 ] == N.

So, for any F1(w), it will be wrong on N-1 lines above ( N*(N-1) v-s) and right on exactly one (N v-s). In total, F1(w) will be right on at most N*N^(N-2) = N^(N-1) input vectors. This upper limit NEEDS to be reached (otherwise the correct number of covered vectors will be less than N*N^(N-1) = N^N, so at least on vector will not be covered). It can be reached (for example by answering with a constant) but if v1 is in D1(w) it MUST follow that any v such that v|2 == v1|2 is also in D1(w). So, |D1(w)| = N for any w (since it can be no greater than N, no less than N). R(i) <= N^(N-2) * D1(some w) = N^(N-1), with equality only if all D1(w) are pair-wise disjoint. Since R(i) must be precisely N^(N-1) all D1(w) must be disjoint.

Let's examine how this changes things for the remaining players.
If |R(1)|=N^(N-1) it follows that the remaining N players must correctly cover N^N - N^(N-1) = (N-1)*N^(N-1) distinct vectors, NOT ALSO COVERED BY PLAYER 1. Since there are N-1 remaining players, and R(i) <= N^(N-1) it follows all that R(i) = N^(N^1) so that all players guess correctly for some v for any w of the input domain of F_i, AND ALL R(i) are pair-wise disjoint.
Note that for players 2..N, |D_i(w)|=1. Since R(i) = N^(N-1) and there are N^(N-1) possible w-s, they are also disjoint.

Let w be any N-2 element vector challenge for player 1, such that |C_i(w[ i ])| >= N^(N-2)
Say F1(w) = x. Then D1(w) = {x?w | for ? = 1..N} = {x1w, x2w, ..., xNw} = {r1, r2, ..., rN}
For some player i>1,
Let h_k = {t| t = w|i U {t[ 2 ] = k} U {t[ 1 ] = x}}; //h = h_k is a possible challenge for player i, compatible with w and F1(w).
Let J_k = D_i(h_k) //The vector on which player i answers correctly to h_k.
All J_k are distinct. It follows by Dirichlet that at least one J_k [ i ] = w[ i ], because:
{
We note that |C_i(w[ i ])|i|2| >= C_i(w[ i ])/1/N = N^(N-2)/N = N^(N-3). //We can extend each N-3 element in C_i(w[ i ])|i|2 to at most N vectors from C_i(w[ i ])|i, by choosing a value for position 2.
Since there are only N^(N-3) vectors of length N-3, it follows all N-3 element vectors must be in C_i(w[ i ])|i|2 (by Dirichlet).
In particular so must the vector x w|i, and thus there must be some vector v = x a w in C_i(w[ i ]), for some a.
Observe that for k=a, v = D_i(h_k) = J_k (by the fact Fi(w)=w[ i ]).
}
Since all J_k are also in D1(w), it follows that for all such w, at least one vector based on w will be correctly answered by both player 1 and player i.
Thus player 1 overlaps each player i on all w's for which |C_i(w[ i ])|>=N^N-2.
For any player i=2..N, there must be at least some w[ i ] in 1..N for which |C_i(w[ i ])|>=N^N-2 //Otherwise |R(i)| would be less than N*N^(N-2)=N^(N-1).
Thus, there are at least some vectors on which player 1 and player i overlap. This contradicts the prior result that all R(i) are disjoint, so the assumption that a valid strategy exists must be false. q.e.d.

Regarding furnicuta, Radu linked an article with the proper proof in section 1.2 here: http://math.arizona.edu/~faris/stoch.pdf which uses http://en.wikipedia.org/wiki/Strong_law_of_large_numbers#Strong_law.

So I was wrong on that one. But hey, does it mean I was also wrong with my proof for Part 2 here?

Ok, deci m-am inselat afirmand ca r = 0 oricand.
Adevarul este:
r = (1-2p)/(1-p), daca p<1/2
r=0, daca p>=1/2.

O demonstratie completa si corecta este si in sectiunea 1.2 aici: http://math.arizona.edu/~faris/stoch.pdf folosind http://en.wikipedia.org/wiki/Strong_law_of_large_numbers#Strong_law.

@Cosmin: Could you quote such a result that explicitly contradicts my result that the probability of the furnicuta living forever is zero? (i.e one showing that the probability the length of a biased (p,1-p) random walk with one absorbing barrier is >0 ?). Note that the fact the Average Path Length could be infinity does not imply that the Probabiliy of an unbounded (infinite) walk is >0. I may be wrong on some things, I may be verbose on others, but in this case I am right.

@Andrei:
If by "you are are wrong" you mean the Furnicuta problem (post "Intrebare de interviu pe Wall Street"), I can assure my conclusion is right (and I am also confident the first proof on my blog is also correct). So, I propose a friendly, scientific wager to you (and don't worry, you won't have to read or verify my verbose proof - although you have that option):

We ask the Probabilities Professor at FMI-UNIBUC about the solution to this problem. More particularly we pose this questions to him: "Is the probability that an ant starting at position 1 on the natural number axis and moving at each step with probability p>0 left (decreasing positions by 1) and 1-p right (increasing position by 1), NEVER reaches position 0 (assuming that, if it hasn't yet reached 0, it MUST take another step) precisely ZERO, regardless of any p>0? Yes or No?". If he asks for further clarifications, we agree, in good faith and without undue delay on a common text to each request and bring it down to a YES or NO. If, after thinking about it (and maybe clarifications), he answers YES, I win; If he answers NO, you win.
Now, if I win, the object of the wager is that you read the following 4 articles from my blog (2 current and 2 future ones) within a resonable amount of time:
- "Asupra Democratiei" ~ 15 pages
- "Despre Alegeri si Vot (II)" ~20 pages
- "Despre Moralitate" (will be posted in a few days) ~15 pages
- "Asupra Libertatii" (will be posted later) ~15-20 pages
The total number of equivalent A4 pages in Word is thus less than 70.

If you win I will read 3x as many pages from any source you like, including Milton Friedman . Or, if you have other suggestions...

@magua:
If player i answers i, then players 2..3 will not answer correctly for wholly disjoint sets; they both answer correctly for: (1, 2, 3), (2, 2, 3) and (3, 2, 3). My final (and irrelevant statement in terms of part 2 proof) was valid assuming players 2..N play one of the "necessary optimum" strategies in which they each cover sets disjoint to one-another. If they, don't, player one can actually answer correctly for as many as N^(N-1) situations.

@Cosmin:
Yup, I tend to be to verbose and formal (just wait until you see my article on morality on my blog ). But I am often also correct , which does not mean I don't strive to improve myself to be more concise too. Btw, did you confirm I was right about the "Furnicuta" problem, in that the probability it survives infinitely much is zero, for p>0?

[So player 1 and player i both answer correctly on some challenge h_k in D1(w), for any w, therefore R_i and R1 are not disjoint as required, so it is impossible to have a correct strategy for all v-s.]

@Andrei:
You're right! No idea why I dived by the "magic figure" N, instead of subtracting from N^2. Probably to get a "convenient" result.

Here's a a correct rephrasing of the proof for Part2:

Assume without loss of generality that Player 1 has less information, seeing just N-2 other numbers. Also, assume, in our favor, that he doesn't see player 2's number always, and that they all know this.

What the N player have to do now is come up with N distinct strategy functions F1..FN, such that Fi(w) is the number player i answers when he sees w:
F1: {1..N}^N-2 -> {1..N}
F2: {1..N}^N-1 -> {1..N}
F3: {1..N}^N-1 -> {1..N}
..
FN: {1..N}^N-1 -> {1..N}

Let R(i) be the set of input vectors v, for which player i answers correctly when exposed to v|i.
Let D_i(w) be the set of all v, such that v is in C_i(F_i(w)) - i.e. player i answers correctly for such a v when exposed to w.
Note that R(i) = U (D_i(w)) for all w in F_i's domain.
What is the maximum size of R(i)?
For all w, there are precisely N "originating" v vectors. Since player i only sees w, it can respond correctly to AT MOST one of these vectors (since they all have different v[ i ] values). So |D_i(w)| <= 1. There are N^(N-1) potential w vectors, so |R(i)| <= N^(N-1) for all i=2..N and all conceivable strategies Fi.

In the case of player 1 things are as follows:
Since the strategy is deterministic, whatever he answers to a challenge w, he will be wrong at least N*(N-1) times:
For every w, there are N^N/N^(N-2) = N^2 possible v-s, as follows:
N where v[ 1 ] == 1.
N where v[ 1 ] == 2.
...
N where v[ 1 ] == N.

So, for any F1(w), it will be wrong on N-1 lines above ( N*(N-1) v-s) and right on exactly one (N v-s). In total, F1(w) will be right on at most N*N^(N-2) = N^(N-1) input vectors. This upper limit NEEDS to be reached (otherwise the correct number of covered vectors will be less than N*N^(N-1) = N^N, so at least on vector will not be covered). It can be reached (for example by answering with a constant) but if v1 is in D1(w) it MUST follow that any v such that v|2 == v1|2 is also in D1(w). So, |D1(w)| = N for any w (since it can be no greater than N, no less than N). R(i) <= N^(N-2) * D1(some w) = N^(N-1), with equality only if all D1(w) are pair-wise disjoint. Since R(i) must be precisely N^(N-1) all D1(w) must be disjoint.

Let's examine how this changes things for the remaining players.
If |R(1)|=N^(N-1) it follows that the remaining N players must correctly cover N^N - N^(N-1) = (N-1)*N^(N-1) distinct vectors, NOT ALSO COVERED BY PLAYER 1. Since there are N-1 remaining players, and R(i) <= N^(N-1) it follows all that R(i) = N^(N^1) so that all players guess correctly for some v for any w of the input domain of F_i, AND ALL R(i) are pair-wise disjoint.
Note that for players 2..N, |D_i(w)|=1. Since R(i) = N^(N-1) and there are N^(N-1) possible w-s, they are also disjoint.

Let w be any N-2 element vector challenge for player 1.
Say F1(w) = x. Then D1(w) = {x?w | for ? = 1..N} = {x1w, x2w, ..., xNw} = {r1, r2, ..., rN}
For some player i>1,
Let h_k = {t| t = w|i U {t[ 2 ] = k} U {t[ 1 ] = x}}; //h_k is the set of all possible N-1 element challenges for player i, compatible with w and F1(w).
Let J_k = The element in D_i(h_k) //The vector on which player i answers correctly to h_k.
All J_k are distinct. Since there are N such sets (for N possible values for player 2), it follows by Dirichlet that at least one J_k [ i ] = w[ i ]. That means J_k is also in D1(w), since D1(w) covers all possible values for player 2, thus at least one will be J_k[ 2 ]. So player 1 and player i both answer correctly on some challenge h_k in D1(w), for any w, therefore R_i and R1 are not disjoint as required, so it is impossible to have a correct strategy for all v-s.

In fact, for every N-2 vector w, each player i will overlap with player 1 on at least one vector induced by w. Assuming players 2..N all answer correctly on distinct v vectors, the total number of overlaps is N^(N-2) * (N-1) = N^(N-1) - N^(N-2).  So player 1, actually only brings a maximum additional contribution of N^(N-2) cases to the number of solved vectors. Just so that you know!

Regarding Part2:

Assume without loss of generality that Player 1 has less information, seeing just N-2 other numbers. Also, assume, in our favor, that he doesn't see player 2's number always, and that they all know this.

What the N player have to do now is come up with N distinct strategy functions F1..FN, such that Fi(w) is the number player i answers when he sees w:
F1: {1..N}^N-2 -> {1..N}
F2: {1..N}^N-1 -> {1..N}
F3: {1..N}^N-1 -> {1..N}
..
FN: {1..N}^N-1 -> {1..N}

Let R(i) be the set of input vectors v, for which player i answers correctly when exposed to v|i.
Let C_i(x) be the set of input vectors v on which player i correctly answers (under the strategy Fi) by saying x.
Let D_i(w) be the set of all v, such that v is in C_i(F_i(w)) - i.e. player i answers correctly for such a v when exposed to w.
Note that R(i) = U (D_i(w)) for all w in F_i's domain.
What is the maximum size of R(i)?
For all w, there are precisely N "originating" v vectors. Since player i only sees w, it can respond correctly to AT MOST one of these vectors (since they all have different v[ i ] values). So |D_i(w)| <= 1. There are N^(N-1) potential w vectors, so |R(i)| <= N^(N-1) for all i=2..N and all conceivable strategies Fi.

But in the case of player 1 things are worse:
Since the strategy is deterministic, whatever he answers to a challenge w, he will be wrong at least N-1 times:
For every w, there are N^N/N^(N-2) = N^2 possible v-s, as follows:
N where v[ 1 ] == 1.
N where v[ 1 ] == 2.
...
N where v[ 1 ] == N.

So whatever F1(w) may be, the answer will be wrong AT LEAST on N*(N-1) potential v-s, or N*(N-1)/N = N-1 times it is exposed to a certain w. In total player 1 will be wrong at least N^(N-2)*(N-1) = N^(N-1) - N^(N-2) times. Clearly F1(w) <= F2(w), so, the total number of potential vectors v, where at least some strategy answers correctly is, by assuming they all max-out their number of correct guesses and that they guess correctly for wholly disjoint sets of v-s:

N^(N-1) - N^(N-2) + (N-1)*N^(N-1) = N^N - N^(N-2) which is less than N^N.

Therefore, there will be AT LEAST one input vector v for which all strategies will fail, no matter what F1,..,FN are.

Regarding the formulation of the problem as a network flow:
Consider this network:
1. Source linked by capacity one edges to
2. N*N left-hand nodes, representing potential v vectors (number assignments): v1,v2,...
3. Each vk is linked by capacity one edges to N distinct nodes corresponding to the pairs (i,vk|i) representing a projection of vk through player's i eyes.
4. Each of these N*N^(N-1)=N^N right-hand nodes is linked by capacity one edges to
5. Sink

Run a max-flow algorithm (notice this is actually a bipartite matching) and interpret the results as:
If there is a link between node vk and node (i,vk|i), player i will answer with vk[ i ] when he sees vk|i. Since the matching is perfect, there is no ambiguity in answers and all potential input vectors are match to at least one pair (corresponding to a player answering correctly).

And btw, freak93's response is also correct and much more direct .

Here is what I thought (in English this time):

Part 1.
The first thing the N persons need to agree is a total order among themselves (so they number themselves from 1 to N). Otherwise there is no strategy since if they don't distinguish between themselves each of them has just a shot at guessing a random number between 1 and N. So now we have N people from 1..N.

Let v[ i ] = the number received by the i-th person.
Let v be the entire vector of numbers received and let v|x be what person x sees (v except v[ x ]).

They now have to agree on some strategy that will give person x a result, r(x) to declare spontaneously with the others. It is clear that r(x) depends only on x and v|x, for any x, and has to work for all possible v-s.
So, their strategy is actually a function they must agree on before hand (or on a way to compute it):
F: {1..N} x {1..N}^N-1 -> {1..N}, such that F(x,v|x) = v[ x ] for AT LEAST one x. Basically player x will answer with r(x)=F(x,v|x).

There are N*N^(N-1) *N = N^(N+1) such potential functions. Let T(N)=N^(N+1) the total number of such functions.

For a function to be "right" for any v, it must include at least one of the maps (parings between a value in the domain and one in the co-domain) (i,w=v|i) -> v[ i ] for any conceivable v. This is can easily be framed as a max-network-flow problem.

An easier way to get directly to the solution is: We consider each conceivable v as being represented as (i, w, x), where w is a n-1 element vector, and v = w U {w[ i ]=x}. The set of all conceivable vectors v can be build by taking for every conceivable pair (w,i), and every possible x. There are N^N pairs (w,i). There are N x values. Of course, each v vector will be constructed N times this way. We need to assign every (i,w) pair precisely one x, with the aim that player i will answer x if he sees w.

We denote C_i(w) = {v| v is a case where player i answers correctly after seeing w}.
We need to partition the input universe so that, for every v,
C_1(v|1) U C_2(v|2) U ... U C_N(v|N) includes v.
Furthermore, all elements in each C_i need to produce the same v[ i ] for the same image v|i (otherwise, you cannot tell HOW to answer correctly). This is equivalent to saying, for each v1,v2 from C_i, v1|i == v2|i => v1=v2.

So, here's how to construct the sets:
{
  U = {1..N}^N;
  Covered = empty;
  for(i=1..N)
   {
    D = U \ Covered; //By induction |D| = ([N-i]/N)*N^N
    D = D|i; //eliminate the i-th element from all vectors to obtain a set of shorter vectors.
    Partition D into equally sized, disjoint sets Di, Di+1, ... , DN; /* You must be careful at this step to partition in such a way that this step will remain feasible at all future iterations. One solution involves cyclic permutations. */
    Ci = {v | v[ i ] = 1 and v|i = w with w in D1 } U .. U {v | v[ i ] = N and v|i = w with w in DN};
    Covered = Covered U Ci;
   }
}

To respond, player i, looks up the (only) v in Ci with v|i = the seen w and responds with v[ i ].

Erata:
Obs.1: Pentru orice x si v:
-> Daca pentru orice y <> x, f(y,v|y) <> v[y] {daca nimeni altul nu a ghicit corect} ATUNCI f(x,v|x) = v

• . {atunci ghicesc eu corect}

@Mircea please keep the comments in English.

Ah, si inca ceva: Omul a fost ateu (fapt documentat pe Facebook)! So give him a break cu "Dumnezeu sa ..."! Cred ca ceva gen "Fie ca memele sale sa ii supravietuiasca in perpetualitate" l-ar fi deranjat mai putin .

http://en.wikipedia.org/wiki/Meme

Eu il tin minte pe Mihai de cand a tinut un lecture la Lot prin anii 2003-2004 (ce vremuri ), venind in Romania din State. A vorbit despre Perfect Hashing si a descris extrem de clar structura de date Van Emde Boas. M-au incantat ambele foarte tare si stilul lui Mihai a fost extraordinar. Tin minte ca m-a amuzat cum era el incantant ca la Perfect Hashing poti tine 4 elemente de 32 de biti in cacheul de latenta minima sau ceva de genul. L-am ascultat si cand a mai vorbit odata la FMI Unibuc pe tema Recunoasterii Faciale (partea de cautare multidimensionala). Ah, si chiar am folosit un paper de-al lui de cautare in arbori pentru firma...  So, nice!

Is he really gone?

[Oricare ar fi o succesiune infinita de evenimente E = E0, E1, E2, ... Ek, cu P(Ei | ~E0 ^ ~E1 ^ ... ^ ~E(i-1))>0 pentru orice i => probabilitatea ca nici un eveniment sa nu se intample (nici unul din infinitatea aceasta) daca le probez pe toate in ordine este fix ZERO.]

Ca sa va stimulez sa cititi demonstratiile, uite si un bonus!

Aplicand Demonstratia 2 (ad literam practic) se demonstreza si ca:

Oricare ar fi o succesiune infinita de evenimente E = E0, E1, E2, ... Ek,  cu P(Ei | ~E0 ^ ~E1 ^ ... ^ ~E(i-1))>0 pentru orice i => probabilitatea ca nici un eveniment sa nu se intample (nici unul din infinitatea aceasta) daca le probez pe toate in ordine este fix ZERO.

Eh? Merita?

Cred ca se generalizeaza usor la daca E ~ N, cu P(e)>0 pentru o infinitate de elementele => Pentru orice succesiune infinita de evenimente, daca le-as proba => Probabilitatea sa iasa toate fals este ZERO.

M-as baza pe faptul ca probabil (sic! ) infinitatea aceea este numarabila => exista un izomorfism de la ea la E => exista un izomorfism intre functia succesor al secventei alese si succesorul din E => P(secventei alese) = P(oricarei secvente ~ succesorul din E).  Practic ignor toate experientele k in care P(Ek | ^Ei care s-au petrecut ^ (^~Ei-urilor) care nu s-au petrecut pentru i < k) = 0.

Daca vreti sa vedeti demonstratiile intr-un format usor mai lizibil, ele sunt disponibile si pe blogul meu , http://mirceadigulescu.blogspot.com/ la sectiunea Informatica si Stiinta Computationala.

Raspunsul este tot ZERO pentru p>0.