In celebration of America’s birthday, let’s count more shapes—not in a board game, but in the American flag:
In particular, consider the centers of the 50 stars depicted on the flag. How many distinct parallelograms can you find whose vertices are all centers of stars? (If two parallelograms are congruent but have different vertices, they should still be counted as distinct.)
Here we will code everything up directly and let the same nice computer that helped us find those extra equilateral triangles hiding in plain sight find all of the parallelograms in the vertices. One note, just as we ignored the degenerate, length $0$ equilateral triangles in the classic Fiddler, let's ignore degenerate parallelograms that have zero area. Let's establish the vertices as $$\mathcal{V} = \{ (x,y) \in \mathbb{N}^2 \mid x+y \mod 2 \equiv 0, x \leq 10, y \leq 8 \},$$ which will give us the distinctive 6-5-6-5-6-5-6-5-6 pattern on the American flag.
We could loop through all possible 4-ples of distinct vertices in $\mathcal{V}$ and test for both being a parallelogram and having nonzero area. However, this would require testing over 5 million possible 4-ples ($=50 \cdot 49 \cdot 48 \cdot 47$). Let's instead take a somewhat more reasonable approach and take triples of points (meaning only about 100,000 tests) and first determine the area of the resulting parallelogram using the determinant formulation. That is the area of a parallelogram with three vertices $X = (x_1,x_2)$, $Y=(y_1, y_2)$, and $Z=(z_1,z_2)$ is given by $$A = \left| \det \begin{pmatrix} x_1 & x_2 & 1 \\ y_1 & y_2 & 1 \\ z_1 & z_2 & 1 \end{pmatrix} \right|.$$
If the resulting area is nonzero, then we can test whether the fourth vertex of a parallelogram with vertices $X$, $Y$, and $Z$ is in $\mathcal{V}.$ To do this, we see that if $X$, $Y$ and $Z$ are three vertices of a parallelogram, then the fourth vertex is given by either $U_1 = X + Y - Z$, $U_2 = X + Z - Y$ or $U_3 = Y + Z - X.$ If $U_i \in \mathcal{V},$ for some $i = 1, 2, 3,$ then we can add the parallelogram with vertices $X$, $Y$, $Z$ and $U_i$ to the list of parallelograms.
Looping through all possible distinct triples in $\mathcal{V},$ we find that there are 5,918 non-degenerate parallelograms that can be made using the centers of the stars on the American flag.
No comments:
Post a Comment