30 masters and 30 juniors came onto tennis players meeting .Each master played with one master and 15 juniors while each junior played with one junior and 15 masters.Prove that one can find two masters and two juniors such that these masters played with each other ,juniors -with each other ,each of two masters played with at least one of two juniors and each of two juniors played with at least one of two masters.
Problem
Source: Tournament of Towns oral round p4
Tags: graph theory, combinatorics
22.03.2016 08:54
No. of masters = No. of juniors = $2*15$. Now $15$ is odd. We will prove the assertion for $(2n-1)$ rather than $15$, using Graph Theoretic Language. Let no. of masters and juniors be $2(2n-1)$. Consider two disjoint graphs $G$ and $G'$ each having $2(2n-1)$ vertices. $G$ represents the masters and $G'$ represents the juniors. Now each master plays with exactly one master so each vertex has degree exactly $1$. This implies that $G$ breaks up into $(2n-1)$ disjoint pairs of connected vertices. Similarly $G'$ also breaks into $(2n-1)$ disjoint pairs of connected vertices. Any vertex $A$ in $G$ is exactly connected to $(2n-1)$ vertices of $G'$ as each master plays with $(2n-1)$ juniors. Call these vertices in $G'$ as the splinter of the vertex $A$. Now the problem statement transforms to proving that the union of splinters of $2$ connected vertices in $G$ contains a pair of connected vertices in $G'$. Suppose this is not true. Then the union of splinters consists of at most $(2n-1)$ vertices, one vertex from each connected pair of $G'$. Since the splinter of a vertex in $G$ has cardinal no. $(2n-1)$ so the union of two splinters has cardinal no. $\geq(2n-1)$ with equality iff the two splinters are exactly the same. Now equality is reached for each pair of connected vertices in $G$ since their union of splinters has maximum cardinal no. $(2n-1)$, by earlier observation. So each connected pair in $G$ has the same splinter in $G'$. Consider a vertex in $G'$. It is either connected to both the vertices of a connected pair in $G$ or to none of them otherwise the equality of their splinters is violated. This implies that the vertex in $G'$ is connected to an integer no. of connected pairs in $G$, that is, to an even no. of vertices in $G$ as each connected pair has two vertices. But this contradicts the fact that a vertex in $G'$ is connected to exactly $(2n-1)$ vertices, that is, odd no. of vertices in $G$. This contradiction ends the proof thereby giving the desired result.
14.10.2016 22:01
In your argument, you need to veriry <babu2001> wrote: Now the problem statement transforms to proving that the union of splinters of $2$ connected vertices in $G$ contains a pair of connected vertices in $G'$. To see this, color each vertex of each pair of connected masters and juniors with black and white marker. Even though the union of the vertices of a connected component in $G$ contains a connected component in $G'$, say $g$, it is still possible that only splinter of white vertex contains $g$ where the splinter of the black vertex is disjoint with $g$.
25.04.2018 17:09
Let the pair of two junior players matched each other be $J_{1},J_{2},...,J_{15}$ as well as the pair of two masters be $M_{1},M_{2},...,M_{15}$. We will make use of reductio ad absurdum. Suppose that every $J_{i},M_{i}$ be vertices of graph, draw edge between $J_{i}$ and $M_{k}$ if there is a match. If there are 3 edges or more between $J_{i}$ and $M_{k}$, contradiction. so every pair of $(J_{i},M_{k})$ have 2 edges considering total master-junior games equal to $450=15\times15\times2$. By this condition, for every pair of $(J_{i},M_{k})$, every edges connected to single junior $j\subset J_{i}$ or single master $m\subset M_{k}$. Let the number of former pairs be $x$, later be $y$ which satisfies $x+y=225$. with an arbitrary $J_{i}$, the number of $M_{k}$ which connected 2 edges in $m\subset M_{k}$ is odd because one junior player matched masters 15 times. So $y$ should be odd. this condition holds in $x$ at that time. Contradiction.