Each girl among $100$ girls has $100$ balls; there are in total $10000$ balls in $100$ colors, from each color there are $100$ balls. On a move, two girls can exchange a ball (the first gives the second one of her balls, and vice versa). The operations can be made in such a way, that in the end, each girl has $100$ balls, colored in the $100$ distinct colors. Prove that there is a sequence of operations, in which each ball is exchanged no more than 1 time, and at the end, each girl has $100$ balls, colored in the $100$ colors.
Problem
Source: ARO 2021 11.8
Tags: combinatorics
VicKmath7
23.04.2021 16:03
@below thanks
RagvaloD
23.04.2021 17:27
Lemma. Let $k$ is natural number and every girl has $k$ balls, and all girls have exactly $k$ balls of one of $100$ colors. Then every girl can choose exactly one ball, such that all chosen balls have different colors.
Proof of Lemma: We say, that girl is friendly with color if she has ball with this color. Note, that every $m=1,2,...,100$ girls are friendly with at least $m$ colors by PHP. Then with Hall`s Marriage theorem we can give to every girl one ball, and all these balls have different colors. End of Proof.
Let girls go to $100 \times 100$ field and every girl choose own column on field. By Lemma then can choose $100$ balls of different colors and put them in first row. Then by lemma, they can for $k=99,98,...,1$ choose balls of different colors and put it in second, third,...,100th row.
In the end we will have table, where in every row we have all balls of different colors, and in every row we have all balls of some girl. We can note, that from diagonal symmetry follows that every column has balls of different colors and this symmetry corresponds to $4950$ permitted exchanges.
MelonGirl
08.07.2022 08:38
Similar to this classic problem from 102 combinatorial problems Quote: An $m \times n$ array is filled with the numbers $\{1,2,\ldots,n\},$ each used exactly $m$ times. Show that one can always permute the numbers within columns to arrange that each row contains every number $\{1,\ldots,n\}$ exactly once.
JAnatolGT_00
22.09.2022 23:02
Lemma. If there are $m$ balls of each color and each girl has $m$ of them, then we may pick one ball from each girl in such way, that all picked balls have different colors. Proof. Consider bipartite graph with sets of vertices $G$, each assigned to a girl, and $C$, each assigned to a color, where edge exists in case if respective girl has ball of respective color. By Pigeonhole principle each $k-\text{element}$ subset of vertices from $G$ ($k=1,2,...,100$) is summary connected with at least $k$ different vertices from $C,$ so by Hall's marriage theorem there exist a $G-\text{perfect}$ $\text{matching}$ as desired. Numerate girls by $1,2,...,100$ and perform $100$ moves, on each pick one ball from every girl, with $100$ balls of all colors in summary. If $B_{x,y}$ denotes ball picked from girl $x$ on move $y,$ then it's enough to exchange all balls $B_{x,y},B_{y,x}$ for $x\neq y.$
skyboy2007
25.12.2022 17:02
it is correct for 2 balls then we add 2 ball from 2 color and we will see it is ok with only one move so it is correct for 10000 balls
EthanWYX2009
11.09.2024 14:56
Nice! We construct bipartite graph $G=(\mathcal G,C,E),$ here $|\mathcal G|=|C|=100.$ and $g\in\mathcal G,$ $c\in C,$ $(g,c)\in E$ iff girl $g$ owns ball with color $c.$ Note that the graph is $100$-regular. Therefore by induction and Hall Lemma there exists perfect matches $PM_1,\ldots ,PM_{100}$ such that $E=\cup^+PM_i.$ Now we arrange balls in a $100\times 100$ table, each column is owned by a girl, each column correspond a perfect match. Now obviously we need to turn the table $90$ degree, which can be easily done by swapping $(a,b)$ and $(b,a),$ $\forall 1\le a<b\le 100.\Box$
alba_tross1867
07.11.2024 23:33
We prove by Hall's marriage theorem ( pigeonhole given that $|S|\cdot k$ ) and induction that given that that every girl has $k$ balls and every color has $k$ balls, one can find a girls perfect matching. Arrange balls accordingly in a $100\times100$ grid, such that each column is a girl, and each row is the $i$-th perfect matching. Swap ball in $(a,b)$ with $(b,a)$. q.e.d.