66 dwarfs have a total of 111 hats. Each of the hats belongs to a dwarf and colored by 66 different colors. Festivities are organized where each of these dwarfs wears their own hat. There is no dwarf pair wearing the same colored hat in any of the festivities. For any two of the festivities, there exist a dwarf wearing a hat of a different color in these festivities. Find the maximum value of the number of festivities that can be organized.
Problem
Source: 2020 Turkey TST P3
Tags: combinatorics
14.04.2020 10:14
The answer is $\boxed{2^{22}}$. We may assume that each dwarf has a set of hats with different colors. Consider a bipartite graph $G=(C\cup D, E)$ where $C,D,E$ represents the set of colors, dwarfs and hats respectively. Draw an edge between $c\in C$ and $d\in D$ iff the dwarf $d$ has a hat in color $c$, then we have $$\#C=\#D=66,\; \#E=111.$$Note that each possible festivity corresponds to a perfect match in $G$, therefore our goal is to estimate the maximum possible number of perfect matches in $G$. Lemma. For any bipartite graph $G=(C\cup D, E)$ where $\#C=\#D=n,\#E=e$, $G$ contains at most $2^{\left\lfloor\frac{e-n}{2}\right\rfloor}$ distinct perfect matches. Proof. Apply induction on $n$. For $n=1$ the conclusion is trivial. Suppose the conclusion holds for $n-1$, consider the case of $n$. WLOG assume that each vertex has a positive degree, then we can pick out the vertex $v$ with the smallest degree. Let the neighbors of $v$ be $u_1,\dots,u_s(s\ge 1)$. For each possible perfect match $M$, let the neighbor of $v$ in $M$ be $u_i$. Wipe out $v,u_i$ (and all their adjacent edges, but do not wipe out their other neighbors) from $G$ we are left a graph $G'$ with $2(n-1)$ vertices and at most $e-(2s-1)$ edges (due to the minimality of $s$). From the induction hypothesis there are at most $$2^{\left\lfloor(e-2s+1-n+1)/2\right\rfloor}=2^{-s+1}\cdot2^{\left\lfloor(e-n)/2\right\rfloor}$$perfect matches in $G'$, each of which corresponds to a $M$ with $(v,u_i)\in M$. Since there are $s$ possible choices for $i$, the total number of perfect matches does not exceed $$s\cdot 2^{-s+1}\cdot2^{\left\lfloor(e-n)/2\right\rfloor}\le2^{\left\lfloor(e-n)/2\right\rfloor}.$$Take $n=66, e=111$ we get that at most $2^{22}$ festivities can be organized. Construction for $\bold{2^{22}}$ festivities. Let $$C=\{c_1,c_2,\dots,c_{66}\}, D=\{d_1,d_2,\dots,d_{66}\},$$then the $111$ edges are chosen as follows. $$(c_i, d_i)\;(1\le i\le 66);$$$$(c_{2i-1},d_{2i}),(c_{2i},d_{2i-1})\;(1\le i\le 21);$$$$(c_{43}, d_{44}),(c_{44}, d_{45}),(c_{45}, d_{43}).$$It's easy to check that there are exactly $111$ edges and $2^{22}$ perfect matches.
16.03.2022 20:13
We will solve the problem with generating functions. The answer is $2^{22}$ Let $c_j$ denote a hat of color $j$. Replace $66$ with $n$ and $111$ with $k$. I will prove if we have $n$ linear polynomials ($P_j$ in $c_1, \cdots, c_n$ for $j=1,2,\cdots,n$) with only 0,1 as coefficients and a total of $k$ terms then $[\prod\limits_{j=1}^n c_j] \prod\limits_{j=1}^n P_j(c_1,\cdots,c_n) \le 2^{\lfloor \frac{k-n}{2} \rfloor}$. We proceed by induction, with the base cases $n=1,2$ verifiable by hand. Inductive step: We have the following recursive structure: if a term $c_t$ appears in $m$ polynomials, then if it is the only term in a polynomial then it must be used, and if only one polynomial has it it must also be used. Therefore, $m\ge 2$ and this implies $f(t,k) \le mf(t-1,k-m-1)$. If $m=2$ we have $f(t,k)\le 2f(t-1,k-3)$ so we are done by inductive hypothesis. Same for $m=4$ and any $m\ge 6$. We are done by inductive hypothesis unless $m=3$ or $m=5$ for all coefficients $c_t$. Therefore, each term is in 3 or 5 polynomials. This means $k-t$ is odd. Now, if say $c_t$ shows up in 3 polynomials, call $P,Q,R$. Then if two of P,Q,R has at least $3$ terms, then picking $c_t$ from $P$ with at least 3 terms suggest there are at most $2^{\lfloor \frac{k-t-4}{2} \rfloor} = \frac 14 2^{\lfloor \frac{k-t}{2} \rfloor}$ ways to picking $[c_1c_2\cdots c_t]$ coefficients. This implies that if $c_t$ shows up in 3 or 5 polynomials, then at most one of them can have more than 2 terms. Take a polynomial containing two terms, call $c_j, c_k$. Since $c_j$ appears in at least 3 polynomials, it follows that if I pick $c_j$ there exists at most $2^{\lfloor \frac{k-t-3}{2} \rfloor}$ ways because I get rid of $c_j, c_k$ and the other two occurences of $c_j$. The same conclusion holds for $c_k$, completing the induction.
Construction for $n=66, k=111$. We take 22 monomials $c_j$ where $j=45,\cdots, 66$, and 2 copies of $c_{2i-1}+c_{2i}$ where $i=1,\cdots,22$. For each $i=1,\cdots,22$ there are 2 ways to pick $c_{2i-1}c_{2i}$, for a total of $2^{22}$ ways. Since $22=\lfloor \frac{111-66}{2} \rfloor$, the conclusion follows.