Jump to content
BrainDen.com - Brain Teasers
  • 0


EventHorizon
 Share

Question

There are n people in a room. Between each pair of people, they either hate each other or like each other (e.g., the feeling is always mutual).

(1) What is the minimum number of people, n, such that you are guaranteed to have either a group of three that all like each other or a group of three that all hate each other?

(2) Now we add in the ability to be indifferent (not like or hate). What must n be such that there is guaranteed to be a group of three that all like each other, all hate each other, or are all indifferent towards each other?

(3) Now say there are m different emotions. How many people must there be such that there is guaranteed to be a group of x people that all have the same emotion towards each other?

Edited by EventHorizon
Link to comment
Share on other sites

Recommended Posts

  • 0
1. 5

2. 7

3. m(x-1) + 1

Number the people 1-5.

Let 1 like 5 and 2 and dislike 3 and 4

Let 2 like 1 and 3 and dislike 4 and 5

Let 3 like 2 and 4 and dislike 5 and 1

Let 4 like 3 and 5 and dislike 1 and 2

Let 5 like 4 and 1 and dislike 2 and 3

Essentially they are arranged in a pentagon with adjacent vertices being liked.

Edited by EventHorizon
Link to comment
Share on other sites

  • 0

1) 6

2) 17?

As to number 3, well, if I knew it (assuming a general form even exists and is provable which it very well may not be) I'd publish it in mathematics journal and gain untold amounts of prestige and fame. This is Ramsey theory and given 2 emotions, if i remember correctly, the highest value of "x" that mathematicians have been able to solve was either 4 or 5 (for the larger numbers they have only been able to construct ranges of numbers for) and that was only done with great effort.

Edited by Flaar
Link to comment
Share on other sites

  • 0

As to number 3, well, if I knew it (assuming a general form even exists and is provable which it very well may not be) I'd publish it in mathematics journal and gain untold amounts of prestige and fame. This is Ramsey theory and given 2 emotions, if i remember correctly, the highest value of "x" that mathematicians have been able to solve was either 4 or 5 (for the larger numbers they have only been able to construct ranges of numbers for) and that was only done with great effort.

1) 6

2) 17?

Yup, you got 1 and 2. Very interesting that this is Ramsey Theory. Thanks for pointing that out.

I adapted this from a question in a math class I took quite a few years ago (actually, question 1 is the exact question). I thought I had a method to solve question 3, but it must break down somewhere. I didn't really put much effort into part 3 yet, though it is surprising to me that it is an unsolved question....

Link to comment
Share on other sites

  • 0

I was thinking part 3 is equivalent to the graph theoretical question

The edges of a nondirected graph are colored with m colors.

How many nodes must it have to ensure a monochrome loop of size x.

But now I see two discrepancies.

  1. A colored edge assumes its nodes share a color [emotion], a condition not imposed by OP.
  2. Only requiring a loop is not enough - you need all the edges [star shaped] to be monochrome.
Discrepancy [1] seems to rule out a graph analogy.
Link to comment
Share on other sites

  • 0

Finally read the OP correctly. What I preach!!! :blush:

A helpful term in graph theory is a clique - a monochromatically colored subgraph.

In this case a group of mutual friends [duh] would be a clique, similarly a group of mutual enemies [not-so-duh].

In case [1] friends /enemies - two relationships

a person can have no more than two friends, else they would be a clique [triangle] of enemies.

a person can have no more than two enemies, else they would be a clique [triangle] of friends.

So a person may have no more than four acquaintances [a graph of degree 5].

Thus a group of 6 persons must contain a clique.

In case [2] friends / enemies / don't cares - three relationships

a person can have no more than 5 friends, else they would have a clique of enemies or of don't-cares.

a person can have no more than 5 enemies, else they would have a clique of don't-cares or of friends.

a person can have no more than 5 don't-cares, else they would have a clique of friends or of enemies.

So a person may have no more than fifteen acquaintances [a graph of degree 16].

Thus a group of 17 persons must contain a clique.

Recursively, for 4, 5 and 6 relationships the group sizes are 66, 327, 1958 ...

For n relationships we get 1 + [sumnk=0] n!/k!

[See] where we also find 1 + floor[e*n!].

In case [3] specified clique size

The above hold for cliques of size 3.

There are claimed solutions for cliques of size 4, but nothing higher.

Link to comment
Share on other sites

  • 0
Finally read the OP correctly. What I preach!!! :blush:

A helpful term in graph theory is a clique - a monochromatically colored subgraph.

In this case a group of mutual friends [duh] would be a clique, similarly a group of mutual enemies [not-so-duh].

In case [1] friends /enemies - two relationships

a person can have no more than two friends, else they would be a clique [triangle] of enemies.

a person can have no more than two enemies, else they would be a clique [triangle] of friends.

So a person may have no more than four acquaintances [a graph of degree 5].

Thus a group of 6 persons must contain a clique.

In case [2] friends / enemies / don't cares - three relationships

a person can have no more than 5 friends, else they would have a clique of enemies or of don't-cares.

a person can have no more than 5 enemies, else they would have a clique of don't-cares or of friends.

a person can have no more than 5 don't-cares, else they would have a clique of friends or of enemies.

So a person may have no more than fifteen acquaintances [a graph of degree 16].

Thus a group of 17 persons must contain a clique.

Recursively, for 4, 5 and 6 relationships the group sizes are 66, 327, 1958 ...

For n relationships we get 1 + [sumnk=0] n!/k!

[See] where we also find 1 + floor[e*n!].

In case [3] specified clique size

The above hold for cliques of size 3.

There are claimed solutions for cliques of size 4, but nothing higher.

Yup, cliques are what we are looking for.

Your answers are right. The method you used to get the answer to (2) is what I used as well. Though it has been proven for 3 relationships, I think it may just be an upper bound for more. What do you think? If it has been proven to be right, could the same method be used for (new 3)?

Alright...question 3 does need to be simplified. Let S(x,m) be the number of people you need to gather before there is a group of x people all with the same emotion, where m is the number of emotions.

(new 3) Assume S(x,2) is known for all x. Give a recursive function for S(x,m).

Link to comment
Share on other sites

  • 0

By the looks of the number of pages, the equation may have already been defined but here what I am thinking:

[spoiler='Basic simplification

']If the feelings are always mutual, then we can simplify the problem by picking up a candidate from the group and counting how he feels about others in the group. If we can find at least 3 connections of the same type then we have met the requirement for 1 and 2

only two emotions, then we have 1 candidate and n-1 peers. n-1 should at least be 5. Since 5 divided by the number of emotions gives the smallest size for the group assigned to each emotion. Hence n = 6 at least

three emotions case, we should have the n such that Round((n-1))/3 = 3, giving n = 10

I think the formula is

Round((n-1))/m = x

I am just not sure about the accuracy of this, concerned with the wound operation. but my lunch is over and i have thing to look at:)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...