1

11 people will learn 11 languages. The teacher can teach two people two languages in each lesson. What is the minimum number of lessons required for 11 people to learn all 11 languages? (one person can learn the same language several times)

My thoughts are below but I am not sure whether it is true or false.

Let's start by considering the number of pairs of people that can be formed from the 11 people. We can use the formula for combinations, which is:

nCr = n! / (r! * (n-r)!)

where n is the total number of people and r is the number of people in each pair. In this case, we have:

11C2 = 11! / (2! * (11-2)!) = 55

So there are 55 pairs of people that can be formed from the group of 11.

Now, each lesson can teach two people two different languages. So in each lesson, we can potentially cover two of the 11 languages.

If we want to minimize the number of lessons required to cover all 11 languages, we should try to cover as many languages as possible in each lesson. To do this, we should pair up people who don't already know the same language.

In the first lesson, we can choose any pair of people and teach them two different languages. In the second lesson, we need to choose another pair of people such that at least one person in the pair has not yet learned one of the languages taught in the first lesson.

We can continue this process, by choosing pairs of people such that at least one person in each pair has not yet learned one of the languages taught in the previous lessons.

Since each lesson can potentially cover two new languages, we will need at least ceil(11/2) = 6 lessons to cover all 11 languages. This is because we need at least 6 pairs of people to cover all 11 languages, and each pair can be taught in a separate lesson.

Therefore, the minimum number of lessons required for 11 people to learn all 11 languages is 6.

deepblue
  • 163
  • 4
  • Just to be clear, do you mean that during a single lesson both Alice and Bob can learn both German and French, and that's all that can be learned during a single lesson? – Arthur Apr 13 '23 at 13:21
  • 5
    6 is certainly too low: there are $11$ people (Say $p_1,\dots,p_{11}$) that each have to learn $11$ languages (Say $l_1,\dots,l_{11}$), so you need to fulfill the $121$ pairs $(p_1,l_1),\dots(p_1,l_{11}),(p_2,l_1),\dots\dots,(p_{11},l_1),\dots,(p_{11},l_{11})$ and each lesson can fulfill at most $4$ such pairs, so the minimal number of lessons is at least $\lceil\frac{121}4\rceil=31$. But you'd have to see if there is a possible configuration of 31 lessons. – student91 Apr 13 '23 at 13:30
  • 2
    You have not found a minimum, because you haven't shown that it can be achieved. Otherwise, all that you have is a lower bound. $\quad$ EG Even in student91's approach, we only know that 31 is a lower bound. As it turns out, it cannot be achieved (why?) – Calvin Lin Apr 13 '23 at 13:30
  • 4
    What's the source of this question? It's been posted 2 days ago, and has been deleted though still showing up in google search. – Calvin Lin Apr 13 '23 at 13:34
  • 1
    As a trivial remark, each person needs to attend at least $6$ classes (since $5\times 2<11$). As was pointed out to you when you posted this earlier, start with smaller numbers than $11$. – lulu Apr 13 '23 at 14:01
  • a friend of mine's teacher asked her. I don't know original source. – deepblue Apr 13 '23 at 14:09
  • Hints: 1/ With the ideas here (including comments), show that $(11^2 + 11) / 4 = 33$ is a lower bound. 2/ Show that this can be achieved, hence it is the minimum. – Calvin Lin Apr 13 '23 at 16:28
  • @CalvinLin I am unable to make an example with 7 people and 7 languages, do you happen to have a hint for the construction? – student91 Apr 13 '23 at 16:30
  • @student91 (Presumably you are already considering the student X lesson table). Hint: Try smaller odd $n$ and find a pattern, though I'm guessing you already did that.. $\quad$ Further hint: To achieve the minimum, each student and lesson has to have exactly 1 repeat. (IE It cannot be just that student A took all languages twice). Let the double-lesson happen on the diagonal. (The rest should come "naturally" after that.) – Calvin Lin Apr 13 '23 at 16:32

1 Answers1

1

I am only able to solve this in a systematic manner for numbers of the form $3+4k$ (i.e. $3,7,11,\dots$). My solution for numbers of the form $1+4k$ (i.e. $1,5,\dots$) is a bit more trial-and-error.

Here are solutions for smaller numbers. Can you make it work for larger numbers? (Hint/remark: I like to draw it as a labeled graph of persons where the labels are the lessons they attend to).

3:

  • $(p_1,p_2,l_1,l_2)$
  • $(p_1,p_3,l_1,l_3)$ (Doubles $(p_1,l_1)$ )
  • $(p_2,p_3,l_2,l_3)$ (Doubles $(p_2,l_2)$ and $(p_3,l_3)$).

Minimum: $\lceil\frac{3\cdot 4}4\rceil=\lceil3\rceil=3$

5:

  • $(p_1,p_2,l_1,l_2)$
  • $(p_1,p_3,l_3,l_4)$
  • $(p_1,p_4,l_5,l_1)$ (Doubles $(p_1,l_1)$)
  • $(p_2,p_4,l_3,l_4)$
  • $(p_2,p_5,l_1,l_5)$ (Doubles $(p_2,l_1)$)
  • $(p_4,p_5,l_2,l_4)$ (Doubles $(p_4,l_4)$)
  • $(p_3,p_5,l_3,l_5)$ (Doubles $(p_3,l_3)$ and $(p_5,l_5)$)
  • $(p_3,?,l_1,l_2)$ (Doubles $(?,l_1)$ and $(?,l_2)$)

Minimum: $\lceil\frac{5\cdot6}4\rceil=\lceil7.5\rceil=8$

7:

  • $(p_1,p_2,l_1,l_2)$
  • $(p_2,p_3,l_2,l_3)$ (Doubles $(p_2,l_2)$)
  • $(p_3,p_4,l_3,l_4)$ (Doubles $(p_3,l_3)$)
  • $(p_4,p_5,l_4,l_5)$ (Doubles $(p_4,l_4)$)
  • $(p_5,p_6,l_5,l_6)$ (Doubles $(p_5,l_5)$)
  • $(p_6,p_7,l_6,l_7)$ (Doubles $(p_6,l_6)$)
  • $(p_1,p_7,l_1,l_7)$ (Doubles $(p_1,l_1)$ and $(p_7,l_7)$)
  • $(p_4,p_6,l_1,l_2)$
  • $(p_5,p_7,l_2,l_3)$
  • $(p_1,p_6,l_3,l_4)$
  • $(p_2,p_7,l_4,l_5)$
  • $(p_1,p_3,l_5,l_6)$
  • $(p_2,p_4,l_6,l_7)$
  • $(p_3,p_5,l_1,l_7)$

Minimum: $\lceil\frac{7\cdot8}4\rceil=14$

On how to derive the minimum $\lceil\frac{n(n+1)}4\rceil$, consider the hints given by lulu, CalvinLin and me:

there are $11$ people (Say $p_1,\dots,p_{11}$) that each have to learn $11$ languages (Say $l_1,\dots,l_{11}$), so you need to fulfill the $121$ pairs $(p_1,l_1),\dots(p_1,l_{11}),(p_2,l_1),\dots\dots,(p_{11},l_1),\dots,(p_{11},l_{11})$ and each lesson can fulfill at most $4$ such pairs, so the minimal number of lessons is at least $\lceil\frac{11^2}4\rceil=31$

Which gives $\lceil\frac{11^2}4\rceil$.

As a trivial remark, each person needs to attend at least $6$ classes (since $5\times2<11$).

(By lulu) Which gives an extra $+11$ for all classes everyone has to take double.

So we arrive at $\lceil\frac{11^2+11}4\rceil$ as was written in the comment by Calvin Lin.

student91
  • 2,913