Numbered hats

[•raduberinde]

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

[•MirceaD85]

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.

[•MirceaD85]

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.

[•raduberinde]

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.

[•MirceaD85]

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