infoarena

https://infoarena.ro/blog/numbered-hats

@Mircea please keep the comments in English.

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}

Do they all have to guess their numbers, or at least one?

Do they have to guess it from the first try?

At least one has to guess his own number. They get just one try.

Members 1 to N-1: each says the sum of numbers he sees. Then member N can sum all those sums and subtract (N-2) * sum of numbers he sees. He is left with (N-1) * his number. I guess. :) // I read it a bit too quickly, as this does not apply if the guesses aresimultaneous.

Here's what i was thinking. Let K be the sum of all the numbers on everyone's hats. And lets number the persons( give them an ordering). Each persone will presume K is congruent with his number(modulo N). One of them has to be right. Let him be x. So K is congruent to x. Now everybody sums the numbers on everybody else's hat. Let that value be Vx for the xth person. Obviously x's number( let it be r) + Vx = K. so r = K-Vx so r is congruent with K - Vx modulo N. We know K modulo N, we know Vx so we know r modulo N. But r is between 1 and N so the must be unique. X says the number and the game is won.

@Vlad
They all say their guess at the same time.

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 ].

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

@Mircea, I don't see a way to frame it as a network flow problem. So it must not be that easy :).

Couldn't follow your second idea. Will give it another try later.

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).

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.

@Mircea
Your reasoning for Part2 is not correct. Let's take N=2, player 1 can't see anything so he just guesses 1 all the time, out of the 4 possibilities he will be right 2 times ,  N^(N-1) - N^(N-2) = 2-1 = 1 

@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! :)

@Mircea, man, you're so verbose, it's a chore to read each post even if it may be correct :).

@Mircea: I'm not sure that is correct either.
Let's try N=3, player i guesses i all the time. The contributions of player 1 (games where he is the only one correct) will be: (1, 1, 1), (1, 1, 2), (1, 3, 1), (1, 3, 2). N^(N-2) = 3 (not 4).

Also, once you get the right solution it will fit in 300 chars of layman's terms.

The people order themselves from 1 to N. Before they are given the numbers, they establish the following rule: Person i (1 <= i <= N) will assume that the sum of all given numbers (let's say S) is congruent with i modulo N. So person i will say i minus the sum of all the assigned numbers he sees, modulo N. Obviously one of them will be right, as S modulo N is within 0 and N-1.

For the second question, if the person who will be right sees only N-2 hats, then he can't figure out his answer.

@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 :P). 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?

No, you are wrong.

@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...

@Mircea, you know your proof contradicts a well established result in probability. Instead of spamming the forum you may consider publishing your result in a peer reviewed probability hournal.

@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. :)

Regarding furnicuta, Radu linked an article with the proper proof in section 1.2 here: http://math.arizona.edu/~faris/stoch.pdf (http://math.arizona.edu/~faris/stoch.pdf) which uses http://en.wikipedia.org/wiki/Strong_law_of_large_numbers#Strong_law (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?

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.

Ca sa nu va obositi, nici demonstratia asta nici cea precedenta a lui Digu nu e corecta IMO (pana si autorul lor e de acord ca sunt cel putin incomplete).

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.

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.

Nu, tot gresita. Cel putin aici: "|R(i)|=r(1)+..+r(N)=N^(N-1)" nu e adevarat, sunt doar N^(N-2) w-uri posibile si multimile r(1)..r(n) formeaza o partitie. Also, fiecare element din r(i) corespunde a N vectori in care jucatorul 1 raspunde corect, deci sunt N^(N-1)/N = N^(N-2) elemente.

Am eu o demonstratie clara si corecta care incepe ca a ta da o scriu intuitiv de la inceput:

------

Fiecarei configuratii pe care un jucator dat i raspunde corect ii corespund alte N-1 configuratii pe care raspunde incorect (pentru cele N-1 alte valori pt jucatorul respectiv). Daca ne gandim un pic, e clar ca multimile astea sunt disjuncte, deci un jucator raspunde corect pe maxim 1/N din numarul total de configuratii. Deci ca sa fie toate "acoperite", in fiecare configuratie exact un jucator trebuie sa raspunda corect. [asta e prima jumate din demonstratiile lui digulescu, spus fara --verbose]

Acum construiesc o configuratie pe care juc 1 si 2 ghicesc corect: iau o configuratie oarecare pentru jucatorii 3,..N, sa zicem toti 1. Notam cu x ce ghiceste juc 1 cand vede toti jucatorii 3..N cu valoarea 1. Notam cu y ce ghiceste juc 2 cand vede ca juc 1 are x si juc 3..N au 1. Configuratia x y 1 1 1 .. 1   este ghicita corect de ambii jucatori. QED

------

Mircea, in notatia ta, eu doar construiesc configuratia F1(w)  F2(F1(w) w)  w.  Cheia constructiei e jucatorul 2, pentru ca el vede tot ce vede si jucatorul 1, plus valoarea lui 1.

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$. :)