24
$\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.

$\endgroup$
  • $\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$ – Gerhard Paseman Mar 14 '19 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$ – Brian Hopkins Mar 15 '19 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$ – Fedor Petrov Mar 15 '19 at 20:23
  • $\begingroup$ Imagine each girl has $n$ boxes labeled with the numbers 1,...,n for each color and every girl puts as many balls in the correct box as possible; then the set of balls that are not in a correctly labeled box resemble a derangement of balls if additionally to its color the balls are labeled with the number of the owning girl. So the question would amount to whether a derangement can always be written as the product of 2-cycles. $\endgroup$ – Manfred Weis Mar 17 '19 at 7:25
  • 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$ – Fedor Petrov Apr 7 '19 at 21:57
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$
  • $\begingroup$ Are edges from cycles of length 2 also available? $\endgroup$ – Fedor Petrov Apr 11 '19 at 11:24
  • $\begingroup$ Yes, we do not care about 2-cycles here. $\endgroup$ – Max Alekseyev Apr 11 '19 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$ – Fedor Petrov Apr 11 '19 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$ – Max Alekseyev Apr 11 '19 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$ – Fedor Petrov Apr 11 '19 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$
  • $\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$ – Gerhard Paseman Mar 17 '19 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$ – Fedor Petrov Mar 17 '19 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$ – Manfred Weis Mar 17 '19 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$ – Manfred Weis Mar 17 '19 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$ – Fedor Petrov Mar 17 '19 at 22:22
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$
0
$\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$
  • $\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$ – Brendan McKay Mar 17 '19 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$ – Gerhard Paseman Mar 18 '19 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 '19 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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