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 people who write to each other about the same topic.
Problem
Source: IMO 1964, Day 2, Problem 4
Tags: combinatorics, Ramsey Theory, Coloring, graph theory, IMO, IMO 1964, Extremal combinatorics
14.10.2005 05:52
why are you posted this problème 2 time :
17.10.2005 16:11
Use Pigeon hole principle.(For more advanced cases refer to Ramsey numbers)
25.10.2005 16:30
The Captain wrote: Use Pigeon hole principle.(For more advanced cases refer to Ramsey numbers) Can you explain it a little longer, please. I tried but got stuck
26.10.2005 09:46
Choose a particular person of the group. He/She corresponds with$16$ others. By the Pigeonhole Principle, he/she must write to at least $6$of the people of one topic, say topic $I$. If any pair of these$6$ people corresponds on topic $I$,then he/she and this pair do the trick. Otherwise, these $6$ correspond amongst themselves only on topics$II or III$. Choose a particular person from this $six-group$.There must be $3$ of the $5$ remaining that correspond with that in one of the topics, say topic $II$. If amongst these three there is a pair that corresponds with each other on topic $II$, then he/she and this pair correspond on topic $II$. Otherwise, these three people only correspond with one another on topic $III$, and we are done.
26.10.2005 09:53
The Captain wrote: Choose a particular person of the group. He/She corresponds with$16$ others. By the Pigeonhole Principle, he/she must write to at least $6$of the people of one topic, say topic $I$. If any pair of these$6$ people corresponds on topic $I$,then he/she and this pair do the trick. Otherwise, these $6$ correspond amongst themselves only on topics$II or III$. Choose a particular person from this $six-group$.There must be $3$ of the $5$ remaining that correspond with that in one of the topics, say topic $II$. If amongst these three there is a pair that corresponds with each other on topic $II$, then he/she and this pair correspond on topic $II$. Otherwise, these three people only correspond with one another on topic $III$, and we are done. Yes, it's by far trivial, but I wondered about the advanced cases you mentioned that used Ramsey Numbers. Anyway, thanks for your help.
20.01.2025 01:27
Label the people $v_1, \ldots, v_{17}$. If two people discussed topic 1 connect them with red, if topic 2 connect with blue, if topic 3 connect with green. Note $v_1$ has degree 16, so by pigeonhole principle at least 6 of them is one color WLOG let it be red. If any of the six vertices $v_i, v_j$ are connected with red we have a monochromatic triangle $v_1,v_i,v_j$. If none of them are connected to each other with red, then they must be connected with blue or green. We can repeat the argument to find that there must be a blue monochromatic triangle or a green monochromatic triangle.