I think about one combinatorial problem and can not crack it yet. I introduce the statement in way of question about a bipartite Graph of BOYs and GIRLs.
Suppose $n\in \mathbb{N}$, let $P_n$ be the set of persons with names all possible $n$-tuples with letters (i.e components of name) from alphabet $\{0,a,b\}$ with at least one and at most two zero in name, one name per person.
Standard manes of members of $P_n$ are of the form $$x=(x_1,\dots,x_{i-1},0,x_{i+1},\dots ,x_{j-1},0,x_{j+1},\dots,x_n)$$ with two zeros somewhere (let us call them GIRLs) and $$x=(x_1,\dots,x_{i-1},0,x_{i+1},\dots,x_n)$$ with only one zero somewhere (let us call them BOYs), where $x_i$ denotes $i$-th component of the name of $x$.
Let $P_n=B\cup G$ where
$B$ be a set of BOYs, that is $n$-tuples with only one zero component
and
$G$ be the set of GIRLs, i.e. $n$-tuples with two zero components.
Now let us say that a boy $x$ and a girl $y$ like each other (and set the edge from $x$ to $y$ in $P_n$)
iff
$x\in B$ and $y\in G$ and the name of $x$ differs by only one symbol from the name of $y$ in place where name of $y$ has $0$.
Then if $x$ is girl and $y$ a boy, then $(x,y)\in E$ iff $(y,x)\in E$.
e.g.
$y=(0,0,a,a,b,a)$ and $x=(0,a,a,a,b,a)$ like each other,
as well as
$y=(0,0,a,a,b,a)$ and $x=(0,b,a,a,b,a)$ like each other.
Then $P_n$ becomes a bipartite graph the following way $$(x,y)\in E~~(\text{there is an edge from $x$ to $y$})$$ $$\text{iff}$$ $$ x\in B ~~\&~~y\in G~~\&~~ \exists k\in \overline{1,\dots, n}~~\big(~y_k=0~~\&~~x_k\neq 0 ~~\&~~\forall j\neq k ~(~x_i=y_i)\big)$$
Note that $$|B|=2^{n-1}\times C^{1}_{n}=2^{n-1}\times n;$$ $$|G|=2^{n-2}\times C^{2}_{n}=2^{n-2}\times \frac{n\times (n-1)}{2}=2^{n-3}\times n\times (n-1)$$ Each boy likes exactly $n-1$ girl and each girl likes exactly $4$ boys.
Example of $P_3$:
Question: Is it true that for any $n\in \mathbb{N}$ the set of BOYs in $P_n$ can be decomposed in three groups $\{B_1,B_2,B_3\}$, such that every girl $y\in G$ do like at least one boy $x$ in each group $B_i$ where $i=\overline{1,\dots,3}$.
It is known for me that the answer is yes for $n\leq4$, but it is result of checking by hand, I do not see any pattern yet.
I thought on this matter for a while but can not crack the problem in general.
May be some one has seen this one somewhere sometimes, maybe some known results which imply that one, or may be someone suggest how can I look at the problem from other side?
Not an answer but too long for a comment...
There is more structure to the problem than just a bipartite graph (even one with fixed degrees on each side). However I don't know how to exploit this structure so this is just offered for discussion.
An $n$-vector of $\{a,b\}^n$ can be considered as a vertex in an $n$-dimensional hypercube. An $n$-vector of $\{0, a, b\}^n$ with exactly one $0$, i.e. a BOY, can be thought of as two such vertices, where $0$ is a wildcard for $a$ or $b$. This defines an edge of the hypercube. Similarly, an $n$-vector of $\{0, a, b\}^n$ with exactly two $0$s, i.e. a GIRL, can be thought of as four such vertices, defining a ($2$-d) face of the hypercube. Then a GIRL and a BOY like each other iff the edge is one of the four edges of the face.
Thus, the problem becomes: in an $n$-dim hypercube, can you color the edges with $3$ colors, s.t. every face includes edges of all $3$ colors?
Due to the hypercube analogy, I find it much easier to think of the symbols not as $(0,a,b)$ but as $(?,0,1)$ where $?$ is the wildcard. A GIRL (face) is a sequence $A?B?C$ where $A,B,C$ are binary sequences (i.e. sequences of $\{0,1\}^k$, note that empty sequences are allowed), and a BOY (edge) is a sequence $D?E$ where $D,E$ are binary sequences. Let $f(D,E)$ be a coloring function mapping edges to one of $3$ colors. What we seek is such a function where, for any binary sequences $A, B, C$ (summing to $n-2$ in total length), among the four values $f(A0B, C), f(A1B, C), f(A, B0C), f(A, B1C)$ all $3$ colors are present.
At this point I am stuck. I have tried obvious things like mod $3$ arithmetic on the sequences, looked up various walks on hypercubes, even considered first coloring the vertices, etc. But nothing seems to work so far.