Seventeen people correspond by mail with one another—each one with all the rest. In their letters only three topics are discussed. Each pair of correspondents deals with only one of the topics. Prove that there are at least three people who write to each other about the same topic.
Pigeon Hole Theory
- Thread starter JoeSal
- Start date
- Joined
- Apr 12, 2005
- Messages
- 11,339
Reposting, still with no personal effort demonstrated, rarely encourages anyone to answer your question. What are your thoughts on the problem and solution?
http://math2.org/mmb/thread/39270
http://math2.org/mmb/thread/39270
OK....
There are multiple sets......(1,2) (1,3) (1,4).....(1,17); (2,3) (2,4) (2,5)....(2,17)...etc. These sets represent each par of individuals who are corresponding by email. Each set has a possibility of 3 topics.
3 people writing to each other about the same topic suggests to me that
the solution of this problem can be proved through the pigeon hole principle, and it was suggested to me to prove by contradiction, but I am confused on how to relate this to the pigeon hole principle.
A suggested start would be much appreciated. Thanks.
There are multiple sets......(1,2) (1,3) (1,4).....(1,17); (2,3) (2,4) (2,5)....(2,17)...etc. These sets represent each par of individuals who are corresponding by email. Each set has a possibility of 3 topics.
3 people writing to each other about the same topic suggests to me that
the solution of this problem can be proved through the pigeon hole principle, and it was suggested to me to prove by contradiction, but I am confused on how to relate this to the pigeon hole principle.
A suggested start would be much appreciated. Thanks.
pka
Elite Member
- Joined
- Jan 29, 2005
- Messages
- 11,976
I would do it directly. There are \(\displaystyle {{17} \choose 2} = 136\) pairs.
There are only three topics, because \(\displaystyle \left\lceil {\frac{{136}}{3}} \right\rceil = 46\) some topic was written on by at least 46 pairs.
Can you finish?
There are only three topics, because \(\displaystyle \left\lceil {\frac{{136}}{3}} \right\rceil = 46\) some topic was written on by at least 46 pairs.
Can you finish?