Painting Rooms
To make the room colors contrasting, Robin decides to paint in such a way that no two rooms connected by a door have the same color.
Here is the blueprint of her house, where she used numerous colors:
Can she achieve her goal using just her two favorite paint colors, red and yellow?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Moderator note:
Trying to color any loop of an odd numbers of rooms with only two colors (so the same color doesn't get used in adjacent rooms) will always fail:
This is as opposed to coloring an even number of rooms:
This is because the alternating red-yellow-red-yellow pattern is allowed to return to the original color at the starting room when the loop has an even number of rooms.
More generally, a floor plan can be colored with 2 colors if and only if every loop of rooms involve an even number of rooms. We've established the only if part above. How can we show the if part?
Consider the room in the middle that doesn't touch any exterior walls. WLOG we can paint this red.
Then the two tiny rooms below it (painted orange and red in the picture) would both need to be yellow (to be different from the red room). However they share a door, so they would need to different colors from each other.
Therefore, no there is no way to achieve the above using only red and yellow paint.