Question

A group of 10 friends decides to head up to a cabin in the woods (where nothing could possibly go wrong). Unfortunately, a number of these friends have dated each other in the past, and things are still a little awkward. To get the cabin, they need to divide up into some number of cars, and no two people who dated should be in the same car.

a. What is the smallest number of cars you need if all the relationships were strictly heterosexual? Represent an example of such a situation with a graph. What kind of graph do you get?
b. Because a number of these friends dated there are also conflicts between friends of the same gender, listed below. Now what is the smallest number of conflict-free cars they could take to the cabin?
Friend A B C D E F G H I J
Conflicts with BEJ ADG HJ BF Al DJ B CI EHJ ACFI
c. What do these questions have to do with coloring?

Answer 1

a) 3

b) 3

c) because of the permutations and combinations involved

Explanation:

a) Determine the smallest number of cars needed

The number of cars are the same as conflict free cars

hence we can group the friends without conflict into the same car

1st car we will have : ACFI in it

2nd car we will have : GD in it

third care we will have : BEJH in it

∴ number of car needed = 3

b) number of conflict free cars = 3

c) Coloring is important in the question because of the permutations and combinations involved