2
$\begingroup$

Seventeen people correspond by mail with one another - each one with all the rest. In their letters only three different topics are discussed. Each pair of correspondents deals with only one of these topics. Prove that there are at least three different people who write to each other about the same topic.

Work I have done so far

Each person can talk to maximum $16$ people on $3$ topics $\implies$ at least one topic will be spoken about $6$ times by Pigeonhole principle.

This part is clear to me. I do not understand how to complete the proof by showing that there are at least three different people who write to each other about the same topic.

$\endgroup$

2 Answers 2

1
$\begingroup$

Consider the person that talks about a topic with other $6$. Take that group of people, and consider that if some pair talks about that same topic then we're done. So consider they don't talk about that topic. They're now a group of $6$ people talking about $2$ topics.

If we apply the same process you did at the start, we have that anyone talks about one of the two remaining topics at least $3$ times. If any pair of those three remaining people talk about that topic, say topic number two, we're done. If there is no pair of those three remaining people talking about topic number two, then they're all talking about topic number three. But then we're done too, because they're a triangle of people talking about the same topic.

It's basically applying what you did three times, until you have a trivial case of a triangle.

$\endgroup$
2
  • $\begingroup$ Finally, I have grasped your solution $\endgroup$ May 20, 2021 at 3:04
  • $\begingroup$ @SanjayAdhith Glad it helped :) $\endgroup$
    – AnilCh
    May 20, 2021 at 7:32
0
$\begingroup$

So there is someone who corresponds with $6$ other people on topic $1$. If any pair of these $6$ people correspond with one another on topic $1$, then we done. So suppose that each of these $6$ people only correspond on topics $2$ or $3$ ... Well that's a $2$ coloring of $K_6$, which must have a $K_3$, so we are done.

For more details see https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Examples

$\endgroup$
2
  • $\begingroup$ What do you mean by 2 colouring of K6, which must have a K3? I am confused by that. $\endgroup$ Dec 20, 2020 at 11:45
  • $\begingroup$ $K_n$ denote the graph with $n$ vertices and with every pair of vertices joined (the complete graph on $n$ vertices). We then think in terms of colouring each edge with $1$ of $2$ colours & see if there are any "monochromatic triangles". $\endgroup$ Dec 20, 2020 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.