2008 persons take part in a programming contest. In one round, the 2008 programmers are divided into two groups. Find the minimum number of groups such that every two programmers ever be in the same group.
Problem
Source: Indonesia TST 2009 First Stage Test 5 Problem 1
Tags: logarithms, induction, inequalities, combinatorics proposed, combinatorics
13.01.2009 18:43
I think the problem is that: There are $ 2008$ participants in a programming competition. In every round, all programmers are divided into two equal sized teams. Find the minimal number of rounds after which there can be a situation in which every two programmers have been in different teams at least once. The answer is $ 11$. Solution 1. After every round consider the biggest set of programmers where the programmers have been in the same team in all rounds so far. Before the first round it consists of $ 2008$ programmers. With every round its size can decrease by at most twice, since the programmers belonging to it are divided among two teams in the new round and at least half of them will again be in the same team. Thus the number of rounds is at least $ \log_{2} 2008$, i.e. at least $ 11$. We shall show that $ 11$ rounds suffice. Order the $ 2008$ programmers in some way and add both at the end and at the beginning $ 20$ imaginary programmers. Number the programmers by $ 11$-digit binary numbers from 0 to 2047, adding leading zeros if necessary. In round $ i$ the programmers are divided into teams according to the $ i$ th digit of their number. In every round the $ k$ th imaginary programmer from the beginning and the $ k$ th imaginary programmer fromthe end are in different teams since their corresponding binary numbers have all digits different. Hence both teams have in every round an equal number of programmers. Also, every pair of programmers belong to different teams in at least one round since their numbers differ in at least one binary digit. Solution 2. Let us prove by induction on $ k$ that if the number of programmers $ 2n$ satisfies the inequalities $ 2^{k - 1} < 2n\leq 2^k$ then $ k$ rounds suffice. If $ k = 1$ then we have $ 2$ programmers and clearly one round is enough. Assume the claim is true for some $ k$. Assume there are $ 2n$ programmers where $ 2^k < 2n\leq 2^{k + 1}$. Divide them into two groups of $ s = 2^k$ and $ t = 2n - s$ programmers, and number them by $ 1, . . . , s$ and $ s + 1, . . . , s + t$ respectively. By the induction hypothesis the programmers in both the first and the second group can be divided into equal-sized teams so that after $ k$ rounds every two (in each group) have competed against each other at least once. For rounds $ 1, . . . , k$ make up two new equal teams by taking one team corresponding to each group and putting them together. Assume without loss of generality that in round $ k$ one team consists of the programmers of the first group with numbers $ 1, . . . ,\frac {s}{2}$ and of the second group with numbers $ s + 1, . . . , s + \frac {t}{2}$. In the new round swap and make up a team of programmers with numbers $ 1, . . . ,\frac {s}{2}$ and $ s + \frac {t}{2} + 1, . . . , s + t$. We can check that every two programmers (also from different groups) have now been in different teams at least once. The other part can be done like in Solution 1.
16.08.2013 21:12
But what if it was: There are $ 2008$ participants in a programming competition. In every round, all programmers are divided into two equal sized teams. Find the minimal number of rounds after which there can be a situation in which every two programmers have been in a same team at least once. The answer here is $4$ (and is independent of the number $2n\geq 6$ of programmers; for $2n=4$, the answer is $3$).