Coloring a polyhedron

Probability Level 2

This 3D solid is colored on each of its 18 faces.

What is the minimum number of colors needed so that no two edge-sharing faces are the same color?

Note : Faces that share a vertex but not an edge can be colored the same.

2 3 4 5

5 solutions

Zain Majumder
Apr 8, 2018

Clearly, not all faces can be the same color, so there must be at least two colors. Here is a two color solution:

Besides finding an actual solution, is there another way to prove that 2 is the minimum number of colours required?

John Frank - 3 years, 2 months ago

I think the solution that you want is just below it

akshat rai - 3 years, 2 months ago

You can simplify this problem by using a strip of paper rather than a figure, with the end connecting to the beginning. If there are an odd number of sections on the paper and you want to alternate between two colors, this is simply impossible. However, doing this with an even number of sections is possible. The same principle can be applied here. Since the top and bottom view of the figure have an even number of symmetry lines, using only two colors is possible.

Anonymous Person - 3 years, 1 month ago

The original version of the problem was much much better. I wish the people at Brilliant would not always change things, at least not this much.

Marta Reece - 3 years, 2 months ago

What was the original problem? I haven't seen it.

Zain Majumder - 3 years, 2 months ago

Where can we see it

Anas Abu Halaweh - 3 years, 1 month ago

HOLLY COWS I was thinking the exact same thing! Even the colors were the same!

Half-god Dragon - 3 years ago

Shreyansh Mukhopadhyay
Apr 9, 2018

We see that in this figure

No three faces can be found such that all of them atleast shares an edge with each of the other two.
There exist two faces which share an edge.

So the minimum number of colors is $\boxed2$

That logic doesn't work. More colors may be needed in some cases even if both of the conditions are fullfilled. For instance, if there is an odd amount of edges beginning from the same vertice, you'll need more than 2 colors to satisfy the problem.

Joel Lahenius - 3 years, 2 months ago

I think you misunderstood. I mean to say that even if a face 'A' is adjascent to more than 1 face, then none of the faces which are adjascent to face 'A' are adjascent to each other.

Shreyansh Mukhopadhyay - 3 years, 2 months ago

As Joel said, this isn't sufficient. You are saying that any triangle-free graph is 2-colorable. But the proper statement is that a graph needs to be without odd cycles to be 2-colorable.

Consider the 10-sided solid formed by gluing together 2 five-sided pyramids to a shared base. Each face of this figure is adjacent to exactly two other faces: the two next to it on its pyramid, and its counterpart in other pyramid. But since it has an odd cycle, it cannot be 2-colored.

Richard Desper - 3 years, 2 months ago

Alexander Lancaster
Apr 8, 2018

it is extrodinary superb

Kapilkannaa Govindhasamy - 3 years, 1 month ago

English is very ambiguous, if you read the problem statement as no "two edge" sharing faces, then the answer is 1 color

Francis Van Dun - 3 years, 1 month ago

This figure is unique because that every point connecting 2 or 4 faces, even number, then 1212, two colors is enough. eg.Octahedra But the cube is different, one point with 3 faces, so it needs 3 colors. These are the simple examples, for the complex ones with many faces, (1)all even number, (2)some are even number, some are odd number, it needs lots time to think.....

明文赵 - 3 years, 1 month ago

Jennifer Smith
Apr 8, 2018

Since all vertices have an even number of faces surrounding them, and since moving from one face to a neighboring face is the same as moving around a vertex, then only two colors are needed to not encounter the paradox where a face must not be its own color, as would be encountered if any of the vertices had an odd number of faces surrounding them.

Robert DeLisle
May 1, 2018

Coloring a polyhedron

5 solutions

0 pending reports