[EventHorizon]

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 February 13, 2009 by EventHorizon

[Guest]

n is a variable right?

[EventHorizon]

n is a variable right?

n, m, and x are all variables

[Guest]

1) 6

Edited February 13, 2009 by Largaroth

[EventHorizon]

Please use spoilers, so others can look over posts without seeing answers.

Edited February 13, 2009 by EventHorizon

[Guest]

k

[Guest]

2) 9

[Guest]

3) mx or is it m^x

Edited February 13, 2009 by Largaroth

[Guest]

Are those correct?

[EventHorizon]

Are those correct?

1)correct

2)nope

3)nope

Though I haven't yet worked out the solutions for 2 and 3 completely.

Edited February 13, 2009 by EventHorizon

[bonanova]

1. 5

2. 7

3. m(x-1) + 1

[Guest]

can you explain why you think that. I'm only in algebra 1...

[EventHorizon]

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 February 13, 2009 by EventHorizon

[Guest]

2) 27

[EventHorizon]

2) 27

I have a smaller number than that for number 2.

[bonanova]

Misread the OP, thought the liking was a quality like colored socks.

It's a graph with colored edges, and we need a monochrome loop.

[EventHorizon]

Misread the OP, thought the liking was a quality like colored socks.

It's a graph with colored edges, and we need a monochrome loop.

that's right. So, what are some of the answers?

[Guest]

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 February 21, 2009 by Flaar

[EventHorizon]

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....

[EventHorizon]

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).

[EventHorizon]

Hmm....seems even that may not be solvable. What I had is simply an upper bound. Looks like this thread is done.

[bonanova]

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.

[bonanova]

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

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 + [sumⁿ_k=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.

[EventHorizon]

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

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 + [sumⁿ_k=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).

[bonanova]

I'll think about it ...

[Guest]

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:)