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 with16 others. By the Pigeonhole Principle, he/she must write to at least 6of the people of one topic, say topic I. If any pair of these6 people corresponds on topic I,then he/she and this pair do the trick. Otherwise, these 6 correspond amongst themselves only on topicsIIorIII. 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 with16 others. By the Pigeonhole Principle, he/she must write to at least 6of the people of one topic, say topic I. If any pair of these6 people corresponds on topic I,then he/she and this pair do the trick. Otherwise, these 6 correspond amongst themselves only on topicsIIorIII. 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 v1,…,v17. If two people discussed topic 1 connect them with red, if topic 2 connect with blue, if topic 3 connect with green. Note v1 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 vi,vj are connected with red we have a monochromatic triangle v1,vi,vj. 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.