Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for 1 ball, so each girl still has $n$ balls), but no ball may participate in more than one exchange. They want to achieve the situation when each girl has balls of all $n$ colours. Is it always possible?

On other language. Given is a bipartite multigraph $G=(V_1,V_2,E)$, $|V_1|=k$, $|V_2|=n$, each vertex in $V_1$ has degree $n$ and each vertex in $V_2$ has degree $k$. We may replace two edges $ab,cd$ ($a,c\in V_1, b,d \in V_2$) to $ad,cb$, but new edges can not be used in exchanges anymore. Is it possible to get a usual $K_{k,n}$ without multiplicities?

If yes, this implies the positive answer to this question, which I find quite interesting itself.

I think I may prove it when $\min(n,k)\leqslant 3$, but already for $3$ there are many cases to consider.

UPDATE (May 2021) Here is the proof of $n=k$ case (due to Ilya Bogdanov), that was recently proposed as a problem on All-Russian olympiad.

Lemma. Let $r$ be a natural number and every girl has $r$ balls, and all girls together have exactly $r$ balls of any of $n$ colors. Then every girl can choose exactly one ball, such that all chosen balls have different colors.

Proof of Lemma. We say that a girl is friendly with a color if she has a ball with this color. Note that every $m=1,2,...,n$ girls are friendly with at least $m$ colors by pigeonhole principle (otherwise their $rm$ ball are colored with less than $m$ colors, thus there exists a color with more than $r$ balls of this color). Then with Hall`s Marriage theorem we can give to every girl one ball, and all these balls have different colors.

Let girls go to an $n \times n$ field and every girl choose her own column on the field. By Lemma they can choose $n$ balls of different colors, each girl choosing one ball, and put them in first row. Then by Lemma for $k=n-1,n-2,...,1$ they can choose balls of different colors and put them in the second, third,...,$n$-th row. Eventually we have a matrix, where in every row we have all balls of different colors, and in every row we have all balls of some girl. Now transposing this matrix (that corresponds to $n(n-1)/2$ legal balls changes) gives what we need: every column contains balls of different color.

Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for 1 ball, so each girl still has $n$ balls), but no ball may participate in more than one exchange. They want to achieve the situation when each girl has balls of all $n$ colours. Is it always possible?

On other language. Given is a bipartite multigraph $G=(V_1,V_2,E)$, $|V_1|=k$, $|V_2|=n$, each vertex in $V_1$ has degree $n$ and each vertex in $V_2$ has degree $k$. We may replace two edges $ab,cd$ ($a,c\in V_1, b,d \in V_2$) to $ad,cb$, but new edges can not be used in exchanges anymore. Is it possible to get a usual $K_{k,n}$ without multiplicities?

If yes, this implies the positive answer to this question, which I find quite interesting itself.

I think I may prove it when $\min(n,k)\leqslant 3$, but already for $3$ there are many cases to consider.

UPDATE (May 2021) Here is the proof of $n=k$ case (due to Ilya Bogdanov), that was recently proposed as a problem on All-Russian olympiad.

Lemma. Let $r$ be a natural number and every girl has $r$ balls, and all girls together have exactly $r$ balls of any of $n$ colors. Then every girl can choose exactly one ball, such that all chosen balls have different colors.

Proof of Lemma. We say that a girl is friendly with a color if she has a ball with this color. Note that every $m=1,2,...,n$ girls are friendly with at least $m$ colors by pigeonhole principle (otherwise their $rm$ ball are colored with less than $m$ colors, thus there exists a color with more than $r$ balls of this color). Then with Hall`s Marriage theorem we can give to every girl one ball, and all these balls have different colors.

Let girls go to an $n \times n$ field and every girl choose her own column on the field. By Lemma they can choose $n$ balls of different colors, each girl choosing one ball, and put them in first row. Then by Lemma for $k=n-1,n-2,...,1$ they can choose balls of different colors and put them in the second, third,...,$n$-th row. Eventually we have a matrix, where in every row we have all balls of different colors, and in every column we have all balls of some girl. Now transposing this matrix (that corresponds to $n(n-1)/2$ legal balls changes) gives what we need: every column contains balls of different color.

Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for 1 ball, so each girl still has $n$ balls), but no ball may participate in more than one exchange. They want to achieve the situation when each girl has balls of all $n$ colours. Is it always possible?

On other language. Given is a bipartite multigraph $G=(V_1,V_2,E)$, $|V_1|=k$, $|V_2|=n$, each vertex in $V_1$ has degree $n$ and each vertex in $V_2$ has degree $k$. We may replace two edges $ab,cd$ ($a,c\in V_1, b,d \in V_2$) to $ad,cb$, but new edges can not be used in exchanges anymore. Is it possible to get a usual $K_{k,n}$ without multiplicities?

If yes, this implies the positive answer to this question, which I find quite interesting itself.

I think I may prove it when $\min(n,k)\leqslant 3$, but already for $3$ there are many cases to consider.

Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for 1 ball, so each girl still has $n$ balls), but no ball may participate in more than one exchange. They want to achieve the situation when each girl has balls of all $n$ colours. Is it always possible?

On other language. Given is a bipartite multigraph $G=(V_1,V_2,E)$, $|V_1|=k$, $|V_2|=n$, each vertex in $V_1$ has degree $n$ and each vertex in $V_2$ has degree $k$. We may replace two edges $ab,cd$ ($a,c\in V_1, b,d \in V_2$) to $ad,cb$, but new edges can not be used in exchanges anymore. Is it possible to get a usual $K_{k,n}$ without multiplicities?

If yes, this implies the positive answer to this question, which I find quite interesting itself.

I think I may prove it when $\min(n,k)\leqslant 3$, but already for $3$ there are many cases to consider.

UPDATE (May 2021) Here is the proof of $n=k$ case (due to Ilya Bogdanov), that was recently proposed as a problem on All-Russian olympiad.

Lemma. Let $r$ be a natural number and every girl has $r$ balls, and all girls together have exactly $r$ balls of any of $n$ colors. Then every girl can choose exactly one ball, such that all chosen balls have different colors.

Proof of Lemma. We say that a girl is friendly with a color if she has a ball with this color. Note that every $m=1,2,...,n$ girls are friendly with at least $m$ colors by pigeonhole principle (otherwise their $rm$ ball are colored with less than $m$ colors, thus there exists a color with more than $r$ balls of this color). Then with Hall`s Marriage theorem we can give to every girl one ball, and all these balls have different colors.

Let girls go to an $n \times n$ field and every girl choose her own column on the field. By Lemma they can choose $n$ balls of different colors, each girl choosing one ball, and put them in first row. Then by Lemma for $k=n-1,n-2,...,1$ they can choose balls of different colors and put them in the second, third,...,$n$-th row. Eventually we have a matrix, where in every row we have all balls of different colors, and in every row we have all balls of some girl. Now transposing this matrix (that corresponds to $n(n-1)/2$ legal balls changes) gives what we need: every column contains balls of different color.

Given $k$ girls, they are given $kn$ balls so that each girls has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each color. Two girls may exchange the balls (1 ball for 1 ball), but no ball may participate in more than one exchange. They want to achieve the situation when each girl has balls of all $n$ colours. Is it always possible?

On other language, given is a bipartite multigraph with parts $G, |G|=k$, and $C,|C|=n$, each vertex in $G$ has degree $n$ and each vertex in $C$ has degree $k$. We may replace two edges $ab,cd$ to $ad,cb$, but new edges can not be used anymore. Is it possible to make a usual $K_{k,n}$ without multiplicities?

If yes, this implies the positive answer to this question, which I find quite interesting itself.

I think I may prove it when $\min(n,k)\leqslant 3$, but already for $3$ there are many cases to consider.

Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for 1 ball, so each girl still has $n$ balls), but no ball may participate in more than one exchange. They want to achieve the situation when each girl has balls of all $n$ colours. Is it always possible?

On other language. Given is a bipartite multigraph $G=(V_1,V_2,E)$, $|V_1|=k$, $|V_2|=n$, each vertex in $V_1$ has degree $n$ and each vertex in $V_2$ has degree $k$. We may replace two edges $ab,cd$ ($a,c\in V_1, b,d \in V_2$) to $ad,cb$, but new edges can not be used in exchanges anymore. Is it possible to get a usual $K_{k,n}$ without multiplicities?

If yes, this implies the positive answer to this question, which I find quite interesting itself.

I think I may prove it when $\min(n,k)\leqslant 3$, but already for $3$ there are many cases to consider.