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

  • Thread starter Thread starter Albert1
  • Start date Start date
  • Tags Tags
    Language
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: 93
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: 99
Last edited:
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
Thread 'Imaginary Pythagorus'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top