30
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ It sounds like a transport problem from operations research. Maybe they have a theorem you can use? Gerhard "Can't Carry All The Way" Paseman, 2019.03.14. $\endgroup$ Mar 14, 2019 at 22:40
  • $\begingroup$ Here's an insufficient idea: Suppose girl $a$ has two or more balls of the same color $x$. Then $a$ must be missing some color $y$. Since there are $k$ balls colored $y$ and $a$ doesn't have one, some other girl $b$ must have two or more balls of the same color $y$. Swap the edges $ax, by$ to $ay, bx$. This reduces the number of multiple edges by one or two---$ax$ and $by$ were both redundant and $ay$ was absent, but there could have already been a $bx$ edge. Repeating brings you down to $K_{k,n}$ with 0 multiple edges. But how to guarantee that changed edges aren't used again? $\endgroup$ Mar 15, 2019 at 20:07
  • $\begingroup$ @BrianHopkins in general you should be care: say, after a couple of such operations Mary may get two red balls which she can not change anymore. $\endgroup$ Mar 15, 2019 at 20:23
  • 1
    $\begingroup$ @TeoBanica if $k=2$ (the case $n=2$ is the same, look at the graph reformulation) with girls Ann, Mary we look at all say $N$ Mary's colors (that is, Mary has both balls of this color) and $N$ Ann's colors, each of two girls choses one ball of each of "her" colors for exchange, and they exchange. $\endgroup$ Apr 7, 2019 at 21:57
  • 1
    $\begingroup$ A trivial observation is that the posed problem can be interpreted as the model of a true exchange market for goods with equal value; that is if two people meet, they exchange $m\le n$ of the $n$ goods in their possesion. That interpretation as a market model hints to e.g. Walras' law in equilibrium theory or economics in general to look for existing results that could aid in solving the problem. $\endgroup$ Mar 19, 2023 at 9:07

4 Answers 4

2
$\begingroup$

First off, let me reformulate the problem. I call edges of $G$ black. Let $K_{k,n}$ be the complete graph on the same partite sets $V_1, V_2$, whose edges I will refer to as red. Let $H$ be the superposition (i.e. gluing of identical vertices) of $G$ and $K_{k,n}$. The graph $H$ is a two-colored graph, where each vertex has as many incident black edges as red ones. Hence, $H$ can be decomposed into a collection of alternating cycles (where the color of edges along each cycle alternate between black and red).

The problem is equivalent to finding an alternating cycle decomposition composed of 2- and 4-cycles only. Indeed, one can set up a one-to-one correspondence between pairs of black edges being exchanged in $G$ and 4-cycles (formed by the original two black edges and a pair of red edges corresponding to what the black edges become after the exchange) in $H$, and between black edges staying put in $G$ and 2-cycles (formed by parallel black and red edges) in $H$.

Theorem. The graph $H$ has an alternating cycle decomposition into 2- and 4-cycles.


The proof below may be incomplete. See comments.

Proof. Let $D$ be an alternating cycle decomposition of $H$ with the maximum number of 4-cycles. We will show that in $D$ there are no cycles of length $>4$. Assume that such a cycle $c$ exists.

I will call a red edge available if in $D$ it belongs to a cycle of length $\ne 4$.

Consider any triple of consecutive black-red-black edges (brb-path) $p$ in $c$. Clearly, its endpoints belong to distinct partite sets in $H$ and thus are connected by a red edge $e$. If $e$ is available, then we can form a new 4-cycle from $p$ and $e$ (and reshuffle the remaining edges from $c$ and the cycle of $e$ into some new cycles) to obtain a new cycle decomposition, where the number of 4-cycles is one more than in $D$. This contradiction to the definition of $D$ implies that $e$ is not available, and thus $e$ belongs to a 4-cycle $q$ in $D$. Let $T_1$ be the superposition of $c$ and $q$, and $b_1$ be any of the black edges of $q$. It is easy to see that $b_1$ is attached to $c$ (at an endpoint of $e$) in $T_1$.

Now, let us consider a brb-path $p_1$ starting at $b_1$ and then going along $c$. Again, its endpoinds are connected by a red edge $e_1$ in $H$. If $e_1$ is available, we can construct two new 4-cycles formed by $p_1$ and $e_1$, and by $p$ and $e$, which will destroy only one 4-cycle $q$. Hence, we'd obtain a cycle decomposition with a larger number of 4-cycles than $D$, a contradiction. It follows that $e_1$ is not available, and thus $e_1$ belongs to a 4-cycle $q_1$ in $D$. Let $T_2$ be the superposition of $T_1$ and $q_1$, and $b_2$ be a black edge of $q_1$ that is attached to $c$ in $T_2$.

Continuing this process we will get an infinite series $(T_k,b_k)$, where the size of $T_k$ grows, which is impossible. The contradiction proves that cycle $c$ does not exist, and thus all cycles in $D$ have length $2$ or $4$. QED

$\endgroup$
5
  • $\begingroup$ Are edges from cycles of length 2 also available? $\endgroup$ Apr 11, 2019 at 11:24
  • $\begingroup$ Yes, we do not care about 2-cycles here. $\endgroup$ Apr 11, 2019 at 11:44
  • $\begingroup$ Can the problems occur when we start to use the same edges of $c$? It looks that this does not allow to get many disjoint 4-cycles as we need... $\endgroup$ Apr 11, 2019 at 17:11
  • $\begingroup$ @FedorPetrov: I've got same concern, but I did not have time to check this carefully. I'll add a notice in the answer and take a close look soon. In either case, I believe there is a proof somewhere along these lines. $\endgroup$ Apr 11, 2019 at 20:45
  • $\begingroup$ If I understand your procedure, each cycle which you are going to add contains some edges from $c$. They certainly can not be disjoint if there are too many of them. Actually something goes wrong quickly when $c$ has length 6. $\endgroup$ Apr 11, 2019 at 21:28
1
$\begingroup$

For the algorithmic solution, i.e. reducing the problem to an ordinary matching problem, the following idea helps:

  • every of the $k$ girls has bucket with $n$ balls and every girl also has $n$ empty boxes that are labeled with the $n$ color names.

  • now every girl puts the correctly filled boxes aside and looks for partner girls to exchange one of her leftover balls; say Ann has a blue leftover ball and an empty box labeled 'red'; so her problem is to find a girl with a red leftover ball and an empty box labeled 'blue'. That observation leads to the formulation as a matching problem.

After having put aside the correctly filled boxes the girls need to find a matching from the balls in the buckets to empty boxes that are labeled with such a ball's color.

Graph theoretic formulation:
every ball in a bucket corresponds to a vertex of partition $A$ and every empty box corresponds to a vertex of partition $B$; the edges in that bipartite graph connect the vertices of $A$ that corresponds to a ball of color $c$ to every vertex in $B$ that corresponds to an empty box that is also labeled $c$.

if a perfect matching exists, then its edges define the pairing for exchanging pairs of misplaced balls that renders each girl with balls of all $n$ colors.


Addendum:

I had assumed that only pairwise interchanges are the admissible operations; then the proposed algorithm works. If however also cyclic exchanges are allowed, then the proposed solution must be modified as follows:

Assume that all balls are in boxes and each girls has put as many balls as possible in a box that is labeled with a ball's color and then puts aside the balls and boxes where the ball's color matches the boxes label.

That leaves every girl with a maximal set of boxes whose labels do not match the color of the contained ball. Now we built a directed graph that is induced by arcs from all balls of color $c$ to all boxes with label $c$.

The solution, provided existence, corresponds then to a collection of vertex disjoint directed cycles that covers all vertices, which in turn correspond to the labeled boxes.

$\endgroup$
6
  • $\begingroup$ Which would be nice if it could be done (and when k or n is 2 such a matching does exist). Now imagine three girls and three colors, where the arrangement is rrb,bbg,ggr. This can be resolved, but not by the matching you propose. Gerhard "If Only It Were Easy" Paseman, 2019.03.17. $\endgroup$ Mar 17, 2019 at 18:47
  • $\begingroup$ The matching in this graph does not always correspond to a family of exchanges, say, a cycle of length 3 is also a matching. Or what do I miss? $\endgroup$ Mar 17, 2019 at 19:50
  • $\begingroup$ @FedorPetrov I have expanded my answer accordingly; I had not read your question careful enough, so I somehow missed that cyclic exchanges along cycles of arbitrary length are permitted. How would the girls agree on such an exchange along a long cycle? $\endgroup$ Mar 17, 2019 at 21:45
  • $\begingroup$ @FedorPetrov in your question you say that "two girls may exchange a ball"; maybe you could give an example, how a correct exhange for rrb, bbg and ggr would look like when two girl exchange balls until each has rbg balls. $\endgroup$ Mar 17, 2019 at 21:50
  • 1
    $\begingroup$ 1) rrb, bbg - rBb, bRg 2)rBb, ggr - rBG, gBr. Capital letter means that the ball can not be used anymore. $\endgroup$ Mar 17, 2019 at 22:22
1
$\begingroup$

Another reformulation of the problem. Call the matrix $\bigl( \begin{smallmatrix}+1 & -1\\ -1 & +1\end{smallmatrix}\bigr)$ and its negation a tile. Suppose we are given a $k\times n$ matrix $M$ of natural numbers such that the sum in each row is $n$ and the sum in each column is $k$.

Can we tile it to obtain the all-1 matrix such that any entry of $M$ is covered by at most one tile's '+1' entry? Equivalently, can we tile the all-1 matrix to obtain $M$ such that any entry is covered by at most one tile's '-1' entry?

I think it is straight-forward to see why this latter version is equivalent to the original question.

$\endgroup$
3
  • 1
    $\begingroup$ I was about to post the same thing, but now I'm not sure. I assume rows are girls and columns are colours. The problem says that no ball can be involved in more than one exchange, but your formulation is that no (girl,colour) pair is involved in more than one exchange. Or did I misunderstand? $\endgroup$ Mar 17, 2019 at 23:59
  • $\begingroup$ Also, tile suggests that the rows and columns are (numerically) adjacent. You might clarify that it is a submatrix of two arbitrary rows and columns. Gerhard "You Should See My Bathroom" Paseman, 2019.03.17. $\endgroup$ Mar 18, 2019 at 0:19
  • $\begingroup$ @Brendan This is why I wrote that it's easier to see the equivalence with the latter version - there's only a single 1 in every place, so you couldn't get more than 1 exchange. $\endgroup$
    – domotorp
    Mar 18, 2019 at 6:37
1
$\begingroup$

One aspect of exhanging the balls a girl initially has with balls from other girls can be interpreted as an assignment problem, namely matching the balls a girl has with the colors (depicted as squares) of the balls she receives; that aspect guarantees, that the girl has balls of all colors after the exchange:

The assignment problem aspect of the ball exchange

Another aspect is "communicating" the exchange of a pair of balls to the assignment-gadgets; that can be accomplished via the following gagdet, that connects two edges of different assignment-gadgets:

Gadget modelling the exchanging of a pair of balls

letting girl $i$ initially have balls $b_{ij}$, of which the color can be determined by evaluating by checking $\mathrm{color}(b_{ij})$; letting further $c_{ij}$ denote the color of the ball, against which ball $b_{ik}$ is exchanged.

The sought matching problem is then modeled by a graph with node sets $B_i=\lbrace b_{ij}\rbrace,\ C_i=\lbrace c_{ik}\rbrace,\ X_i=\lbrace x_{ijk}\rbrace$, for girl $i$. The edgesets are $\lbrace(b_{ij},c_{ik})\rbrace$ that constitute to the individual assignmet gadgets, $\lbrace(b_{ij},x_{ijk}),\ (x_{ijk},c_{ik})\rbrace$ that connect the assignment edges to the ball-exchange vertices, and $\lbrace(x_{iuv},x_{jrs})\ |\ \mathrm{color}(b_{iu})=c_{js}\ \wedge\ \mathrm{color}(b_{jr})=c_{iv}\rbrace$ for exchanging a pair of balls with colors $c_{iv}$ and $c_{js}$ between girls $i$ and $j$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.