The faces of an Icosahedron i.e; a regular polygon with 20 faces (each face is a equilateral triangle) are coloured with blue and white in such a way that no blue face is adjacent to another blue face. What is the maximum number of blue faces can be coloured ? $$ $$ I have tried in this way- Since a Icosahedron has 20 faces and we have to colour with 2 colour blue and white, if we colour with only face with blue and other 19 faces with white , we have 20 ways. Similarly if we colour 2 faces with blue colour, then it has 3 adjacent faces , so we can colour $ 16 \times 4=64 $ ways but I am not sure please help me. 
Asked
Active
Viewed 694 times
1
MAS
- 10,638
-
1Are you trying to answer "What is the maximum number of faces we can color blue, with no two adjacent?" or "In how many ways can we color some faces blue, with no two adjacent?" You ask the first, but then start work on the second... – Misha Lavrov Apr 08 '17 at 23:54
-
yes I need ' maximum number of faces we can colour with no adjacent faces by two colours' – MAS Apr 08 '17 at 23:58
-
1A nice bit of trivia: If you construct the icosahedron from three orthogonal golden rectangles aligned to the x y z axes, then you can align the 8 blue triangles in the answers below so that the centers form the vertices of a cube. – Josh B. Apr 09 '17 at 00:45
2 Answers
5
One thing that helps when thinking about the icosahedron graph-theoretically (that is, when you just care about which faces and vertices and such are adjacent, not about angles and side lengths and so on) is to flatten it out:
So now we can start thinking about the problem properly. This makes it easier to try coloring some faces in Paint or something to see what happens. Keep in mind, though, that in this picture, the entire outside of the diagram represents the last face of the icosahedron.
It's always a good idea to think about some easy upper bounds first. To begin with, we can color at most half of the faces ($10$ faces) blue, because we can't ever color a face and its neighbor blue. (And we could divide the faces up into pairs of neighbors.)
But if we tried to color $10$ faces blue, we'd run into a different problem: of the $5$ faces around a vertex, we can color at most $2$ blue. In fact, this tells us that we can color at most $\frac25$ of the faces ($8$ faces) blue in general. (To justify this, consider that if we add up the number of blue faces around every vertex, we can get at most $24$: twice the number of vertices. But this counts every blue face $3$ times, because every face has $3$ vertices, so there can be at most $8$ blue faces.)
This seems like a pretty good upper bound for now. So we can start trying to color the icosahedron, and it will either work or we'll run into a problem that we can hopefully generalize to get a better upper bound.
In this case, it turns out to work.
Misha Lavrov
- 142,276
0
You can get eight blue faces as shown below. The diagram is a net that you can cut out and fold into an icosahedron. The top five triangles meet to form one vertex, the bottom five form another and the ends of the band of ten triangles attach together. The faces with B in them are the ones colored blue, so we can get at least eight. To show that you can't do better, the only way to get more than four blue in the band of ten is to have all five at the bottom (or top) be blue, but then all the bottom triangles must be white and only two of the top ones can be white. If you have four blue in the central band, you can only have two of the top five and two of the bottom five, which makes eight.
Ross Millikan
- 374,822