MHB What Is the Minimum Number of Rooms Needed in a Hotel Graph Problem?

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion revolves around determining the minimum number of hotel rooms needed for 1000 people, where each person knows at most three others. The problem is framed in graph theory, with the goal of finding the chromatic number of a graph representing the relationships among the individuals. The participants suggest dividing the people into subsets based on how many others they know, leading to a conclusion that four rooms are sufficient. Brook's Theorem is referenced as a method to confirm this result. Ultimately, the minimum number of rooms required is established as four.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Smile)

I am looking at the following exercise:

There are $1000$ people in a hotel and each person knows at most $3$ people.
We want to find the minimum number of rooms,that are needed,so that no person is at the same room with other people,that he knows.

I thought that I could substract from the total number of rooms without restrictions, the number of rooms,that are needed,so that each person is at the same room with persons that he knows.. But...how can I find the last number..? :confused: :confused:
 
Physics news on Phys.org
evinda said:
Hello! (Smile)

I am looking at the following exercise:

There are $1000$ people in a hotel and each person knows at most $3$ people.
We want to find the minimum number of rooms,that are needed,so that no person is at the same room with other people,that he knows.

I thought that I could substract from the total number of rooms without restrictions, the number of rooms,that are needed,so that each person is at the same room with persons that he knows.. But...how can I find the last number..? :confused: :confused:

Let suppose that the set of 1000 people is devided into four subset...

a) the subset which contains all people knowing three other people, it is composed by groups of four people...

b) the subset which contains all people knowing two other people, it is composed by groups of three people...

c) the subset which contains all people knowing one other person, it is composed by groups of two people...

d) the subset which contains all people knowing no other people, it is composed by groups of one person...

If You use four rooms, You first divide the components of each group in a) into them and then You proceed with the component of each group of b) and so one... the minimum number of rooms is four...

Kind regards

$\chi$ $\sigma$
 
Last edited:
evinda said:
Hello! (Smile)

I am looking at the following exercise:

There are $1000$ people in a hotel and each person knows at most $3$ people.
We want to find the minimum number of rooms,that are needed,so that no person is at the same room with other people,that he knows.

I thought that I could substract from the total number of rooms without restrictions, the number of rooms,that are needed,so that each person is at the same room with persons that he knows.. But...how can I find the last number..? :confused: :confused:
We can formulate the question in graph theoretic terms.

A graph is said to be good if it has a $1000$ vertices and if each of its vertices has degree atmost 3.

Let $\mathcal G$ be the set of all the good graphs.

The question is asking us to find $\max_{G\in \mathcal G} \chi(G)$, where $\chi(G)$ is the chromatic number of the graph $G$.

These are my first thoughts. Let me think about how to actually find the above mentioned quantity.

Continuation: Using Brook's Theorem [Brooks' theorem - Wikipedia, the free encyclopedia] it can be easily seen that the required number is $4$.
 

Similar threads

Replies
1
Views
2K
Replies
5
Views
2K
Replies
14
Views
2K
Replies
19
Views
2K
Replies
22
Views
2K
Replies
6
Views
2K
Back
Top