playing with chessboards

An 11 11 x 11 11 chessboard is taken and two of it's squares are colored red and the rest are colored blue. We consider two arrangements to be similar if one can be obtained from another by rotation of the plane of the board.How many dissimilar color schemes are possible???


The answer is 1830.

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

Eddie The Head
Apr 11, 2014

Clearly there are ( 121 2 ) = 7260 \dbinom{121}{2} = 7260 possible ways to select the position of the red squares.

But as quarter turns are allowed,the number of possibilities is much less than this

There are two types of configurations:-

1. Color schemes that are diametrically opposite:- 1.\textbf{Color schemes that are diametrically opposite:-}

Color schemes in which two red squares are diametrically opposite in the chessboard appear in 2 equivalent(or similar forms).This is because these forms can be obtained by rotating the chessboard via two quarter-turns.Some example of diametrically opposite squares are given in the diagram below.

img2 img2

Each position in the chessboard except the center square will have one and only one opposite square which will constitute can equivalent arrangement.So the numbers of pairs of such equivalent squares = 121 1 2 = 60 \frac{121-1}{2} = 60 .Note that we divide by two to prevent over-counting.

Since there the equivalent forms is counted twice the number of distinct arrangements of squares in the equivalent position = 60 2 = 30 \frac{60}{2} = 30 .

2. Color schemes that are not diametrically opposite:- 2.\textbf{Color schemes that are not diametrically opposite:-}

The color schemes that are not diametrically opposite can appear in 4 equivalent forms.Each equivalent form can be obtained by a quarter turn of the chessboard.The total number of such forms is 7260 60 = 7200 7260-60 = 7200 .An example of not diametrically opposite square is shown below

img3 img3

So the number of distinct forms = 7200 / 4 = 1800 7200/4 = 1800

Hence the total number of possible arrangements subject to the given constraints is 1800 + 30 = 1830 1800+30 = \boxed{1830}

If you explained it using Polya Enumeration Theorem aka Burnside's Lemma, it will be easier to see how this relates to a more general scenario.

Calvin Lin Staff - 7 years, 1 month ago

Log in to reply

Should I do a post onpolya enumeration?

Eddie The Head - 7 years, 1 month ago

Log in to reply

Certainly!

Calvin Lin Staff - 7 years, 1 month ago
Pio Esguerra
Apr 30, 2014

We'll use Burnside's lemma which states that when a group G \mathcal{G} acts on a set X X then the number of orbits formed by the action, which is the number of equivalent configurations, is given by 1 G g G F i x ( g ) \displaystyle\frac{1}{|\mathcal{G}|}\sum_{g\in\mathcal{G}}{Fix(g)} where F i x ( g ) Fix(g) is the set of elements of X X that are fixed by g G g\in\mathcal{G} .

Here, our G \mathcal{G} is the set of four transformations: identity, rotation by 90 degrees clockwise, rotation by 90 degrees counterclockwise, and the 180 degree rotation. Our X X is the set of ( 121 2 ) = 7260 \displaystyle\binom{121}{2}=7260 ways that we can place our 2 red squares.

The identity fixes all 7260 configurations. The two 90 degree rotations do not fix any of the configurations. The 180 degree rotation fixes configurations where the two red squares are diametrically opposite each other, of which there are 60. Thus, the number of orbits is:

1 4 ( 7260 + 60 ) = 1830 \displaystyle\frac{1}{4}(7260+60)=\boxed{1830}

Shaun Yeoh
Aug 6, 2014

There are a total of 121 C 2 121C2 ways to pick two of the 121 121 squares to paint red, but these are not all distinct if we consider rotations indistinguishable.

There are 2 2 cases to consider:

color schemes which have the two red squares:

1. diametrically opposing

  • There 120 / 2 ! = 60 120/2! = 60 color schemes of the 1st case

2.non-diametrically opposing.

NOTE: (pick any square other than the center and the diametrically opposing square )

120 120 choices, then divide by 2 2 since we could have picked them in either order

  • There are 121 C 2 60 = 7200 121C2 - 60 = 7200 paintings of the 2nd case.

Each painting of the 1st case has 2 distinct rotations which are indistinguishable color schemes, and each painting of the 2nd case has 4 distinct rotation

Thus the total number of distinct color schemes is 60 / 2 + 7200 / 4 60/2 + 7200/4 = 1830 \boxed{1830}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...