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
SUMMARY

The discussion centers on a mathematical proof involving 9 scholars at an international seminar, where each scholar can speak a maximum of 3 different languages. The key premise is that among any group of 3 scholars, at least 2 can communicate with each other. This leads to the conclusion that it is possible to find a group of 3 scholars who can converse in a common language. The proof relies on combinatorial reasoning and the pigeonhole principle to establish the existence of such a group.

PREREQUISITES
  • Understanding of combinatorial mathematics
  • Familiarity with the pigeonhole principle
  • Basic knowledge of graph theory concepts
  • Ability to analyze language communication models
NEXT STEPS
  • Study the pigeonhole principle in depth
  • Explore combinatorial proofs in mathematics
  • Learn about graph theory and its applications in communication
  • Investigate language models and their implications in multilingual settings
USEFUL FOR

Mathematicians, educators, linguists, and anyone interested in combinatorial proofs and language communication dynamics.

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: 104
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: 111
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