In conference there $n>2$ mathematicians. Every two mathematicians communicate in one of the $n$ offical languages of the conference. For any three different offical languages the exists three mathematicians who communicate with each other in these three languages. Find all $n$ such that this is possible.
Problem
Source: 5-th Hong Kong Mathematical Olympiad 2002
Tags: modular arithmetic, combinatorics unsolved, combinatorics
10.01.2007 21:05
For $n$ odd, we give a construction: let $n = 2k+1$ and let both the mathematicians and the languages be numbered $0, 1, \ldots, 2k$. Have mathematicians $i$ and $j$ speak language $(i+j)(k+1) \pmod n$. Then any triple of distinct languages $a, b, c$ is spoken by the mathematicians numbered $a+b-c, a-b+c$ and $-a+b+c$. Now, each language must be spoken by the same number of pairs of mathematicians (just sum over all triples), so it is clearly a requirement that $\frac1n{n \choose 2}$ be an integer, so $n$ odd is necessary. Thus, the answer is exactly the odd integers larger than 2.
11.01.2007 03:03
JBL wrote: For $n$ odd, we give a construction: let $n = 2k+1$ and let both the mathematicians and the languages be numbered $0, 1, \ldots, 2k$. Have mathematicians $i$ and $j$ speak language $(i+j)(k+1) \pmod n$. Then any triple of distinct languages $a, b, c$ is spoken by the mathematicians numbered $a+b-c, a-b+c$ and $-a+b+c$. Ok! Quote: Now, each language must be spoken by the same number of pairs of mathematicians (just sum over all triples), so it is clearly a requirement that $\frac1n{n \choose 2}$ be an integer Why? (because English of mine is not good) Can you concrete?
11.01.2007 18:35
N.T.TUAN wrote: Quote: Now, each language must be spoken by the same number of pairs of mathematicians (just sum over all triples), so it is clearly a requirement that $\frac1n{n \choose 2}$ be an integer Why? (because English of mine is not good) Can you concrete? Let us count the number of pairs of mathematicians who communicate in language $0$. There are $n \choose 3$ triples of languages and $n \choose 3$ triples of mathematicians, so each triple of languages is represented by exactly one triple of mathematicians. There are $n-1 \choose 2$ triples of languages which include language $0$, and so language $0$ is spoken in exactly $n-1\choose 2$ triples of mathematicians. Given a pair of mathematicians $(x, y)$ who speak language $0$, they are members of $n-2$ triples, so the number of such pairs times $n-2$ must be $n-1 \choose 2$. Thus the number of such triples is $\frac{1}{n-2}{n-1 \choose 2}= \frac{n-1}{2}$ which is equal to the value I gave, and which is an integer only when $n$ is odd.
11.01.2007 19:11
JBL wrote: Given a pair of mathematicians $(x, y)$ who speak language $0$, they are members of $n-2$ triples, so the number of such pairs times $n-2$ must be $n-1 \choose 2$. Will you count number of triples $\{x,y,z\}$ (not $(x,y,z)$, i think) mathematicians speak language $0$ by two way?
13.01.2007 20:59
Yes and yes.
25.05.2017 07:57
An equivalent formulation of this problem appeared in China MO 2009. See here.