Eight children, who did not know each other, came to the dance class. To introduce them to each other, teacher decided to choose four children each minute and let them dance in a circle. During this minute, each of the children in a circle will get to know a neighbor on the left and on the right. What is the minimal number of minutes the teacher needs to make all eight children know each other?
(Arsenii Nikolaiev)
Solution
Consider any child from this group. They need to get to know seven other children, and participating once in a dancing circle they meet maximum two new acquaintances. Thus, each child should participate in at least four dancing circles. In each dancing circle, there are no more than four children participating. Then, there were at least circles. Now we are going to give an example in which eight circles are enough for everybody to know each other. We enumerate children from 1 to 8 and make the next ordered groups: 1234, 5678, 1357, 2468, 1526, 3748, 2736 and 1845. Here we assume that the last child stands in a circle near the first one.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.