Problem:
A by square is divided into four by squares. Each of the small squares is to be painted either green or red. In how many different ways can the painting be accomplished so that no green square shares its top or right side with any red square? There may be as few as zero or as many as four small green squares.
Answer Choices:
A.
B.
C.
D.
E.
Solution:
If there is any square painted green, then all the squares above or to the right of it must also be green. Therefore, the possible patterns of colors are:
Thus, there are different ways to paint the squares according to the requirements of the problem.
All the green squares on any row must be to the right. The number of green squares in any row must be at least as large as the number of green squares in any lower row. Therefore, the number of ways to paint squares green is the number of sums with , and can be any number from through . There are such sums:
Therefore, there are ways to paint the by square according to the requirements of the problem.
Query. What if the original square were by by
Answer: .
The problems on this page are the property of the MAA's American Mathematics Competitions