#8 LESS THAN 4^16

You are given a 4x4 grid with 16 cells. Each cell can have one out of four colors. How many combinations are possible if directly vertical and horizontal neighbored cells must not have the same color?

Correct answer: 6000732

Explanation:

There are five patterns an individual row may have: abab, abca, abcb, abac, abcd. There are 12 of the first kind, 24 of each of the others. We form a matrix a_ij of the number of type j that can legally be adjacent to one of type i, and use this matrix as follows to produce the answer: 
[1 1 1 1 1] [ 7  3  5  5  4 ]     [12]
            [ 6 11  7  7  8 ]     [24]
            [10  7 11  8  8 ] ^ 3 [24] = 6000732.
            [10  7  8 11  8 ]     [24]
            [ 8  8  8  8  9 ]     [24]
Of course it is also possible to write a simple computer program which checks all possible combinations ;-)

Back to Problem Overview

Back to Main Page
© Andreas Rottler


visitors:
month:
today:
online:
since 12.11.2002