Difference between revisions of "2016 UNCO Math Contest II Problems/Problem 10"

(Created page with "== Problem == == Solution == == See also == {{UNCO Math Contest box|year=2016|n=II|num-b=9|after=Last Question}} [[Category:]]")
 
(Solution)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
 +
 +
How many distinct plane wallpaper patterns can be created by cloning the chessboard arrangements described in Question 9?
 +
 +
Each periodic wallpaper pattern is generated by this method: starting with a chessboard arrangement from Question 9 (the
 +
master tile), use copies of that tile to fill the plane seamlessly, placing the copies edge-to-edge and corner-to-corner. Note that
 +
the resulting wallpaper pattern repeats with period 8, horizontally and vertically. When the tiling is done, the chessboard edges and corners vanish, leaving only an infinite periodic pattern of black and white pawns visible on the wallpaper. Regard two of the infinite wallpaper patterns as the same if and only if there is a plane translation that slides one wallpaper pattern onto an exact copy of the other one. You may slide vertically, horizontally, or a combination of both, any number of squares. (Rotations and reflections are not allowed, just translations.)
 +
Note that the wallpaper pattern depicted above can be generated by many different master tiles (by regarding
 +
any square 8 × 8 portion of the wallpaper as the master tile chessboard). The challenge is to account for
 +
such duplication. Remember that each master tile has exactly four pawns of each color.
 +
You may give your answer as an expression using factorials and/or combinations (binomial coefficients).
 +
You are not asked to compute the numeric answer.
  
 
== Solution ==
 
== Solution ==
 +
There are <math>\frac{1}{32}\Big\{\frac{64!}{56!4!4!} + 3\frac{ 32!}{28!2!2!}+ 12\frac{16!}{14!1!1!}\Big\}= 9682216530</math> different wallpaper patterns.
  
 
== See also ==
 
== See also ==
 
{{UNCO Math Contest box|year=2016|n=II|num-b=9|after=Last Question}}
 
{{UNCO Math Contest box|year=2016|n=II|num-b=9|after=Last Question}}
  
[[Category:]]
+
[[Category: Intermediate Combinatorics Problems]]

Latest revision as of 04:07, 13 January 2019

Problem

How many distinct plane wallpaper patterns can be created by cloning the chessboard arrangements described in Question 9?

Each periodic wallpaper pattern is generated by this method: starting with a chessboard arrangement from Question 9 (the master tile), use copies of that tile to fill the plane seamlessly, placing the copies edge-to-edge and corner-to-corner. Note that the resulting wallpaper pattern repeats with period 8, horizontally and vertically. When the tiling is done, the chessboard edges and corners vanish, leaving only an infinite periodic pattern of black and white pawns visible on the wallpaper. Regard two of the infinite wallpaper patterns as the same if and only if there is a plane translation that slides one wallpaper pattern onto an exact copy of the other one. You may slide vertically, horizontally, or a combination of both, any number of squares. (Rotations and reflections are not allowed, just translations.) Note that the wallpaper pattern depicted above can be generated by many different master tiles (by regarding any square 8 × 8 portion of the wallpaper as the master tile chessboard). The challenge is to account for such duplication. Remember that each master tile has exactly four pawns of each color. You may give your answer as an expression using factorials and/or combinations (binomial coefficients). You are not asked to compute the numeric answer.

Solution

There are $\frac{1}{32}\Big\{\frac{64!}{56!4!4!} + 3\frac{ 32!}{28!2!2!}+ 12\frac{16!}{14!1!1!}\Big\}= 9682216530$ different wallpaper patterns.

See also

2016 UNCO Math Contest II (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Last Question
1 2 3 4 5 6 7 8 9 10
All UNCO Math Contest Problems and Solutions