There are 25 masks of different colours. k sages play the following game. They are shown all the masks. Then the sages agree on their strategy. After that the masks are put on them so that each sage sees the masks on the others but can not see who wears each mask and does not see his own mask. No communication is allowed. Then each of them simultaneously names one colour trying to guess the colour of his mask. Find the minimum k for which the sages can agree so that at least one of them surely guesses the colour of his mask. ( S. Berlov )
Problem
Source:
Tags: combinatorics
ThE-dArK-lOrD
26.07.2017 20:16
Anyone? I strongly believe that the answer is $k=13$. Here's what I've done; Suppose that the set of those $25$ colours is $C=\{ c_1,c_2,c_3,...,c_{25}\}$. Let $S$ denote the set of all $(k-1)$-subset of $C$. Note that the problem is to determine whether there exist $k$ functions $f_i:S\rightarrow C$, where $i=1,2,...,k$, such that; (A) For every $d_j\in D=\{ d_1,d_2,...,d_k\} \subset C$, there exist $i\in \{ 1,2,...,k\}$ such that $f_i(D-\{ d_j\} )=d_j$. Note that there are $k\times \binom{25}{k}$ possibilities of $d_j,D$ in condition (A). So there's $i\in \{ 1,2,...,k\}$ which have at least $\binom{25}{k}$ members in $f_i$'s domain. This gives us $\binom{25}{k-1} \geq \binom{25}{k}\Rightarrow k\geq 13$. Now we can get some information from the equality case. I'm still trying to construct such functions.
math90
26.07.2017 23:46
The construction is simply Hall's theorem. We'll use your notation.Let $A$ be the set of all $13$-element subsets of $C=\{ c_1,c_2,c_3,...,c_{25}\}$. It's known that there is a bijection $g:S\to A$ such that $X\subset g(X)$ for all $X\in S$. Now define $f:S\rightarrow C$ by $f(X)=g(X)\setminus X$ for all $X\in S$. The strategy is that each person guesses the image of $f$ on the set of colors he sees. Hence for every set $D$ of $13$ colors, only $D\setminus\{g^{-1}(D)\}$ guesses his color correctly.