Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

Dividing a gathering for friends

Question

Let’s say there is a gathering where among any three people there are two friends. Is it true that people at such gathering can always be divided into two groups in a way that every two people in one group are friends?

Share this post


Link to post
Share on other sites

1 answer to this question

  • 0
Spoiler

This appears to be an example of the monochromatic triangle problem and its connection to Ramsey's theorem

Specifically, in any group of at least six persons, there will be a subgroup of at least three persons in which there are either no friendships (a scenario excluded by the question) or each person in the subgroup is friends with each other person in the subgroup (the scenario that the question wants to prove is implied by the exclusion of the former). To answer the question, yes it is true.

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×