Carpeting and Traffic light, what do they have in common?

Nothing ... you may say so. And I completely agree with you. However, what I am talking about is two problems, Carpeting a house and Traffic light setting. They may have some thing in common that might surprise you. I have to be more specific, haven't I?

Carpeting a house: I want to fully carpeting this house with one condition. I want every room that connect to each other have different color. For the room that is not directly connect, may share the same color.

figure 1

For this particular house, kitchen (K) and living room (L) are connected, they have to have different color. Assuming the small area in front of rest room (R) is belongs to kitchen. All bedroom (MB, B1 and B2) can have the same color. In this case, 3 colors is enough. But can I do this with two color?

Remember the small area in front of restroom is belongs to Kitchen, so B1 and B2 are not directly connected, so living room.

figure 2

Let draw this floor plan differently (figure 2):  All the room are connected directly to kitchen, except the master bedroom (MB). We have to choose two different colors for kitchen and living room, say C1 for kitchen and C2 for living room. Then we can use C1 for master bedroom and C2 for bedroom 1 and 2. Using two colors is possible then.



In this particular problem drawing the floor plan differently give us clearer view of the problem. It's may not be necessary in this case because the floor plan are small and simple but for more complex one, redrawing would help.


Traffic light setting: Now I am a traffic light engineer, and I want to setup a traffic light on this intersection, show in figure 3:  Let A, B, and C are two-way streets, while D is one way street. I can setup the light this way:

1. let A go to B and C
2. let B go to A and C
3. let C go to A and B
4. let D go to A, B and C

That mean in one cycle, I have 4 steps and I guarantee that every one have their turn.  But, again, can I do this in 3 steps (hopefully shorten the cycles)? That is not quite easy to answer, isn't it? Let keep it for the next post, stay tuned.