There are $27$ cardboard and $27$ plastic boxes. There are balls of certain colors inside the boxes. It is known that any two boxes of the same kind do not have a ball with the same color. Boxes of different kind have at least one ball of the same color. At each step we select two boxes that have a ball of same color and switch this common color into any other color we wish. Find the smallest number $n$ of moves required.
Problem
Source: Turkey Junior Math Olympiad 2019 #4
Tags: combinatorics, combinatorics proposed
gnoka
26.12.2019 05:37
Thanks very much！ I'm still confused with this part: At the end of $n$ moves we see that each box is containing two same colors in it. I suppose you mean ''if the same colors are red and yellow, then each box has at least a red ball and a yellow ball.'' Is that right?
CinarArslan
26.12.2019 08:36
electrovector wrote: There are $27$ cardboard and $27$ plastic boxes. There are balls of certain colors inside the boxes. It is known that any two boxes of the same kind do not have a ball with the same color. Boxes of different kind have at least one ball of the same color. At each step we select two boxes that have a ball of same color and switch this common color into any other color we wish. Find the smallest number $n$ of moves required.
junioragd
02.01.2020 12:55
What is the goal?What do we want to happen after $n$ moves?
electrovector
02.01.2020 18:44
Oh sorryyyy! After $n$ moves each box contains a pair in the same color
gnoka
07.01.2020 03:21
get it thank you
mathematist
05.01.2022 21:25
First, we will find that 41 moves is enough . C1, C2, ... , C27 are cardboard boxes and P1, P2, ... , P27 are plastic ones.
We will seperate the boxes into 12 groups containing 2 plastic and 2 cardboards and a group that contains 3 plastic and 3 cardboard boxes.
İn the first group C1 there will be colors {1, 2, ... } ; in C2 there will be {3, 4, ... } ; in P1 there will be { 1, 3, ... } and in P2 there will be {2, 4, ... }. If we change colors 2, 3 and 4 in the first 3 moves that will mean each box containing pairs of 1. we will do the same thing to other 11 groups.
İn the last group, there will be C25{49, 50, 51, ... } ; C26{52, 53, 54, ... } ; C27{ 55, 56, 57, ... } and P25{49, 52, 55, ... } ; P26{50, 53, 56, ... } ; P27{51, 54, 57, ... } if we color color 50s, 53s, 54s, 57s, 55s to 49 there will be pairs of 49 in each of them. So we used 3.12+5=41 moves.
Now we will find that 41 is the min. number. In the boxes in different types, assume that there is a pair of the same colors. Let k be the number of the cardboard boxes requiring just one move. So there will be min. 54 - 2k moves for the other cardboards and min. 54 - k moves for all of the cardboard boxes. This k moves will not generate same colored pairs in plastics so we need different moves for plastic boxes. We will need minimum 27 + k moves for plastics. Because of max(54 - k, 27 + k) = 41 we will need minimum 41 moves.