Numbered hats

[•Cosmin]

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

[•MirceaD85]

@Mircea please keep the comments in English.

[•MirceaD85]

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}

[•Mishu91]

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

Do they have to guess it from the first try?

[•Cosmin]

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

[•vlad.manea]

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.

[•freak93]

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.

[•caheman]

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

[•MirceaD85]

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

[•MirceaD85]

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

[•Cosmin]

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

[•MirceaD85]

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

[•MirceaD85]

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.

[•magua]

@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 

[•MirceaD85]

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

[•Cosmin]

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

[•magua]

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

[•Mishu91]

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.

[•MirceaD85]

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

[•wefgef]

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.

[•MirceaD85]

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

[•Cosmin]

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

[•MirceaD85]

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

[•MirceaD85]

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?

[•MirceaD85]

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.