How many ways are there to color vertices of a $12-polygon$ with two colors that no other polygones can be built using vertices which are same in color?

The book gave the answer $906$ so we can conclude that rotation can make distinct cases.It is clear that we can have $12,6,4,3-polygon$ and if we reduce $3$ and $4$ polygon cases the others will also reduced.For calculating them I tried to use inclusion–exclusion principle but it takes much calculations so how should I solve that?

  • $\begingroup$ Are you coloring the edges or the verticies ? $\endgroup$ – Donald Splutterwit Jun 11 '17 at 10:01
  • 1
    $\begingroup$ (The plural of vertex is vertices) $\endgroup$ – Mariano Suárez-Álvarez Jun 11 '17 at 10:02
  • $\begingroup$ @DonaldSplutterwit sorry vertexes. $\endgroup$ – user454216 Jun 11 '17 at 10:02
  • $\begingroup$ @MarianoSuárez-Álvarez fixed sorry for my poor English. $\endgroup$ – user454216 Jun 11 '17 at 10:05
  • 2
    $\begingroup$ No need to be sorry! That's how we all learned. $\endgroup$ – Mariano Suárez-Álvarez Jun 11 '17 at 10:06

The condition that no polygon with vertices of the same color can be formed is equivalent to this:

  • None of the inscribed triangles are monochromatic
  • None of the inscribed squares are monochromatic

This is clearly equivalent to coloring a $4\times 3$ grid with black and white so that no row or column is monochromatic.

there are clearly $(2^3-2)^4=6^4=1296$ way to paint the rows so that they are not monochromatic.

We just have to subtract the number of ways to do this that form a monochromatic column.

Given a fixed column there are $2\times 3^4$ colorings that make it monochromatic.

Given two fixed columns there are $2$ colorings in which they are monochromatic of the same color and there are $2\times 2^4$ colorings in which they are monchromatic with distinct colors. So in total $2^5+2=34$

There are $3\times 2$ colorings in which all three columns are monochromatic.

By inclusion-exclusion there are $3(2\times 3^4) - 3(34)+6=390$ colorings in which no row is monochromatic and at least one column is.

Hence the answer is $1296-390=906$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy