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

|cite|improve this question
$\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 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 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 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 at 7:25
  • $\begingroup$ @ManfredWeis if we fix a priori the balls which are unique for corresponding girls, this may be not possible. Example: Ann has white,white,blue balls, Mary blue,blue,red, Lisa red,red,white. $\endgroup$ – Fedor Petrov Mar 17 at 13:39
0
$\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.

|cite|improve this answer
$\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 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 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 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 at 21:50
  • $\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 at 22:22
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.

|cite|improve this answer
$\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 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 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 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.