Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i stumbled upon the following question: There are $2n$ students in a school $(n ∈ N, n ≥ 2)$. Each week $n$ students go on a trip. After several trips the following condition was fulfilled: every two students were together on at least one trip. What is the minimum number of trips needed for this to happen? (Proposed by Oleksandr Rybak, Kiev, Ukraine)

If you search the web for this problem you find a more number theoretic proof and the answer is 6. But i have a different approach where i'm not sure if the idea is correct and how to give a clean proof.

Think about a graph which has $2n$ nodes. Now if two students are on the same trip a new edge is drawn for those two nodes. So the question for the minimum number boils down to the question what is the minimum number $m$ of trips needed to generate a complete graph.

One trip with $n$ students causes $\binom{n}{2} = \frac{n(n-1)}{2}$ edges to be drawn in the graph. The complete graph, which means the end result where every two students were together on at least one trip, has $\binom{2n}{2} = n(2n-1)$ edges. So we wanted to know the minimum number $m$ which fulfills $$m \frac{n (n-1)}{2}\ge n(2n-1) \Leftrightarrow m (n-1)\ge 2(2n-1)$$

Now here i'm kinda stuck. If you put our minimum $n=2$ in the inequality you get $m\ge 6$, which must be a lower bound needed to be fulfilled by all $n$. E.g. for $n=5$ one gets $m\ge5$ but this minimum doesnt hold for $n=2$, so $m=6$ must be a minimum for all $n$. On the other side the following equality holds $$6(n-1)\ge 2(2n-1) \Leftrightarrow n\ge 2$$

So, am i finished here or is the proof wrong or am i missing something? The idea seems feasable, but it feels more like toying around than having a nice argument flow.

Thanks for any toughts on this.

share|improve this question

1 Answer 1

The problem with your answer is that you're solving an easier question. In your version of the problem, you can place any edges in the graph. Your analysis assumes you can place $n \choose 2$ edges wherever you please.

But in the original version of the problem, the $n \choose 2$ edges cannot be wherever you please. They must be in fact in one big group--they must form the complete graph $K_n$ on some $n$ vertices. Therefore, just because $6{n \choose 2} \ge {2n \choose 2}$ does not mean necessarily that you can place $6$ copies of $K_n$ to cover the entire graph $K_{2n}$, i.e. it does not mean $6$ trips is necessarily the minimum.

In fact, according to your analysis, $5$ is the minimum as long as $n > 2$. But this is not correct. Consider the case $n = 3$. Then the question is whether five triangles can cover the graph $K_6$. But by edge counting, these five triangles would have to be completely disjoint (i.e., they would be unable to share any edges). And since each vertex has an odd number of edges going out of it, it is impossible to make the triangles which contain that vertex completely disjoint.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.