We can find 3 scholars talking together (using one common language)

  • Context: MHB 
  • Thread starter Thread starter Albert1
  • Start date Start date
  • Tags Tags
    Language
Click For Summary

Discussion Overview

The discussion revolves around a combinatorial problem involving 9 scholars at an international seminar, focusing on their language capabilities and communication. Participants are tasked with proving that it is possible to find 3 scholars who can communicate using a common language, given certain conditions about language proficiency and communication among groups of scholars.

Discussion Character

  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants reiterate the problem statement regarding the language capabilities of the scholars and the communication conditions.
  • One participant shares an attempt at a solution, although the details of this attempt are not provided.
  • Hints are offered by participants, suggesting that there may be multiple approaches to the problem.
  • A later reply thanks another participant for their attempt and explanation, indicating engagement with the proposed ideas.

Areas of Agreement / Disagreement

The discussion appears to be unresolved, with multiple participants contributing different hints and attempts without reaching a consensus on a solution.

Contextual Notes

Limitations include the lack of detailed mathematical steps in the attempts shared, and the problem's dependence on the definitions of communication and language proficiency among the scholars.

Albert1
Messages
1,221
Reaction score
0
Having 9 scholars attend an international seminar,
the following informations are given:
(1) each member can at most speak 3 different languages
(2) any 3 members at least 2 can communicate
prove:we can find 3 scholars talking together (using one common language)
 
Mathematics news on Phys.org
Albert said:
Having 9 scholars attend an international seminar,
the following informations are given:
(1) each member can at most speak 3 different languages
(2) any 3 members at least 2 can communicate
prove:we can find 3 scholars talking together (using one common language)
hint:
dot1,---and dot9 represent 9 scholars
constructing a segment "a" between dot1 and dot2 means member 1 and member 2
can communicate with each other using language "a"
note :
(1) each member can at most speak 3 different languages
(2) any 3 members at least 2 can communicate
 
My attempt:
View attachment 7243

I use Alberts hint. Please cf. the attached diagram.
The conditions given are:

$(1).$ Each of the 9 scholars speaks at most three languages.
$(2).$ In a group of any three scholars, at least two scholars share a common language.

Graphical translation: Connecting scholars (dots) with language segments (lines).

According to condition $(1)$ each scholar on the diagram is allowed to have a maximum of three segments attached.

Condition $(2)$ implies, that no matter what group we form, there must be at least one interconnection (segment) in the group. (A group is e.g. $\{1,2,3\}$ meaning, that scholar no. $1$, $2$ and $3$ are in the group). There are $84$ possible groups, but we only need to consider some of them in order to prove the statement, that there are indeed at least three scholars, who share one common language.

In what follows, let´s suppose, that there are no three scholars sharing a common language.

Let´s start with scholar $1$:

Suppose scholar $1$ is connected with scholar $2$ by segment $a$, meaning that they can communicate in language $a$.

Obviously, there is no loss of generality by choosing a connection between scholar $1$ and $2$. But any new connection between two of the nine scholars from now on excludes language $a$, because any other “$a$-connection” would imply, that at least three scholars share the common language $a$.

All $7$ groups of the form $\{1,2,j\}$ with $3 \le j \le 9$ fulfill both conditions.Next, we look at the $6$ groups of the form $\{1,3,i\}$ where $4 \le i \le 9$. One of them is $\{1,3,4\}$. For this group to fulfill the requirements, we need at least one connection between two of the three members. We can WLOG connect $3$ and $4$ with segment $b$, that is: scholar $3$ and $4$ share a common language, which we call $b$.
(We could have connected $1$ and $4$ or $1$ and $3$. In both cases, we would need a new language $b$ and the end result of our procedure would be exactly the same).
The group $\{1,3,5\}$ doesn´t have any language connection. So either we connect $1$ and $5$ or $3$ and $5$ (or $1$ and $3$). In any of these cases this requires a new language ($c$). Let´s choose the connection $1$ to $5$.The same considerations for the group $\{1,3,6\}$: We need at least one connection. We choose, WLOG, $3$ and $6$ (language $d$).In $\{1,3,7\}$, we choose $1$ and $7$ with language $e$.In the group $\{1,3,8\}$, we have only one option left, because scholar $1$ already is occupied with $3$ languages ($a$,$c$,$e$).

So $3$ is connected with $8$ by language $f$, and scholar $3$ is then also occupied with $3$ languages ($b$,$d$,$f$).

But the group $\{1,3,9\}$ cannot fulfill the two conditions, because any single connection between two of the three scholars implies a fourth language segment, which is not allowed (red lines). Hence, we are forced to use one of the existing language segments e.g. $a$. This contradicts our assumption. Done.
 

Attachments

  • 9 students sharing languages.png
    9 students sharing languages.png
    5.8 KB · Views: 106
Albert said:
hint:
dot1,---and dot9 represent 9 scholars
constructing a segment "a" between dot1 and dot2 means member 1 and member 2
can communicate with each other using language "a"
note :
(1) each member can at most speak 3 different languages
(2) any 3 members at least 2 can communicate
thanks Ifdahl for your attempt and explanation
a complete solution:
View attachment 7245
the above diagram is a complete solution:
no matter what situation happened, we can find 3 scholars talk together using
common language
we also know that if there are only 8 schoalrs under the same assumption
the statement is not always true
 

Attachments

  • 3 scholars talk together using common languages.jpg
    3 scholars talk together using common languages.jpg
    16.1 KB · Views: 114
Last edited:

Similar threads

Replies
4
Views
6K
  • · Replies 5 ·
Replies
5
Views
1K
  • · Replies 40 ·
2
Replies
40
Views
8K
  • · Replies 7 ·
Replies
7
Views
3K
  • Sticky
  • · Replies 0 ·
Replies
0
Views
4K
Replies
2
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K