[Guest]

On a certain island, every two people are either friends or foes, the king wants to hold a certain competition in which out of the 6 competitors 3 people are chosen (randomly) every round to perform a certain task, but the king's condition is that in every team of 3 there will not be 3 friends or 3 foes, find the king a group of 6 people for this competition...

[Guest]

This puzzle is simple, if psychology is used in place of math. Theoretically, if every other person is either a friend or foe, two groups will form. Both groups of friends that are enemies of each other. Take two from on and one from the other.

[dark_magician_92]

On a certain island, every two people are either friends or foes, the king wants to hold a certain competition in which out of the 6 competitors 3 people are chosen (randomly) every round to perform a certain task, but the king's condition is that in every team of 3 there will not be 3 friends or 3 foes, find the king a group of 6 people for this competition...

sorry anza, but i dint get what we have to do in the question

[superprismatic]

On a certain island, every two people are either friends or foes, the king wants to hold a certain competition in which out of the 6 competitors 3 people are chosen (randomly) every round to perform a certain task, but the king's condition is that in every team of 3 there will not be 3 friends or 3 foes, find the king a group of 6 people for this competition...

I must not understand something. Is it not possible that every pair of persons on the island are enemies? In which case there is no solution to the problem. Perhaps you have some unspecified rules about enemy/friend relationships.

Edited January 1, 2011 by superprismatic

[Guest]

Hmm let me explain:

Each two people are either friends with each other or enemies.

You job is to pick six people, they can be friends or foes or anything you want, the condition is that when you pick 3 from those 6 you will not get three enemies or 3 friends, example:

ABDCEF

List of friends:

AB

AC

AD

BC

BD

BF

DF

EF

And the rest are enemies, but this choice is not good because you can see A B and C are all friends (A is friends with B, B is friends with C, C is friends with A) you need a combination that no matter what 3 people you pick there will be at least one friendship and one enemyship...

Draw 6 dots, each representing a person, there is a line between every two dots, red line means they're enemies and blue line means they're friends, you need to color the lines so that there are no red or blue triangles...

[Guest]

I apologize if my answer is too simplistically dumb to consider...

[Guest]

I don't think it is possible to find 6 such people.

Let's say the people are 1, 2, 3, 4, 5, 6.

1 will have atleast 3 friends or 3 foes among 2 - 6.

Let's say (1, a) (1, b) (1, c) are friends.

Then, (a, b) (a, c) (b, c) are enemies.

But, (a,b) and (a,c) enemies mean (b, c) must be friends.

[superprismatic]

I don't think it is possible to find 6 such people.

Let's say the people are 1, 2, 3, 4, 5, 6.

1 will have atleast 3 friends or 3 foes among 2 - 6.

Let's say (1, a) (1, b) (1, c) are friends.

Then, (a, b) (a, c) (b, c) are enemies.

But, (a,b) and (a,c) enemies mean (b, c) must be friends.

duke2cool: I think we both misunderstand what AZ is thinking. Taking his example in post #5,

A and B are friends, B and F are friends, but A and F are enemies. So, two of B's friends

are enemies.

I don't think a solution is possible because everyone on the island may be

friends with everyone else. In that case, a solution is impossible because there simply

are no enemies. So, some assumptions about the friend/enemy makeup of the island must

be made in order for a solution to exist.

[plasmid]

It can't be done, and here's a proof.

Suppose a solution does exist. Well, we know that you can take any three people and there will either be two friend relationships and one enemy relationship, or one friend relationship and two enemy relationships. That means that if we're given three people from the solution set, we know that there will be some way that we can label them A, B, and C in such a way that A is friends with B and A is enemies with C. (I don't really care how B and C get along.)

Now consider A's relationships with the other three people who I still haven't given names to yet. A must be either friends with at least two of those three people or enemies with at least two of those three people. For now, I'll consider the case where A is friends with at least two of them, and I'll name those two people D and E. (If A were enemies with two people, then you could use the same logic I'm about to use below but just substitute C whenever I used B.)

Consider the relationship between A, B, and D. Since A is friends with B and A is friends with D, then B must be enemies with D. Then consider A, B, and E. By similar logic, B must also be enemies with E.

The problem is that now we can't assign any relationship between D and E that works. A is friends with both D and E so they must be enemies, but B is enemies with both D and E so they must be friends. Therefore you can't assign a relationship between D and E that will satisfy the puzzle.

Sry if the colors came out blah

Edited January 1, 2011 by plasmid

[plasmid]

After reading duke2cool's answer more closely, I see that it's actually a correct proof of impossibility as well. I just didn't completely follow it on the first readthrough.

[Guest]

Duke and plasmid got it...