Thursday, November 18, 2021

Aesthetic Tiling with 3-Color Mapped 6x10 Pentomino Solutions


Finding 3-color mapped solutions to the 6x10 pentomino puzzle

There are exactly 12 planar shapes that can be formed by connecting 5 squares edge to edge with no overlap. These shapes were made famous by mathematician Solomon Golomb in 1953 who coined the term pentomino, provided mathematical and visual descriptions of the 12 pieces, and offered some games and puzzles using the set. A common puzzle challenge is to use all 12 pentominoes to tile a rectangle with no gaps or overlap. The set of 12 pentominoes contains 12 x 5 = 60 squares, and indeed one popular puzzle is to fit them into a 6x10 unit rectangle (Fig. 1). In 1960 mathematician Colin Brian and physicist Jenifer Haselgrove found that there are exactly 2339 possible pentomino arrangements that could fill a 6 x 10 rectangle.[1]

Figure 1: Tiling a 6 x 10 rectangle

A nice method of presentation is to color the pentominoes so that the boundaries demark the characteristic shapes, and in particular when the coloring can be done with only three colors such that similar colored pieces do not touch. Patrick Hamlyn showed that of the 2339 solutions only 94 could be colored in this way.[2] Further analysis performed in 2014 by Alexandre Muñiz breaks down the possible 3 color solutions and finds that only 53 of these 94 solutions color the pentominoes to “balance”, where balance indicates that the colors are distributed evenly to three groups of four pentominoes.[3]  In preparing an educational video on pentominoes, it struck me that the 3 color solution would be the nicest to show, so I purchased a set of pentominoes produced by Discovery Toys that conveniently came in three bright colors (Fig. 2).

Figure 2: Three color set by Discovery Toys

After many unsuccessful trials I decide to find out analytically if a 3 color solution was possible for this set. I found a list of the 2339 solutions online and wrote some Visual Basic code that was able to confirm the work of Muñiz finding just 53 balanced 3-color solutions out of 13,507,725 possible such combinations for the 6x10 tiling. See this appendix for images of these 53 solutions.

However I also found that for each of the 53 balanced 3-color solutions there was exactly only one way to compose the 3-color sets of 4 pentominoes each. An example of a balanced 3-color solution is shown in Figure 3.  

Figure 3: Example of balanced 3-color solution

Another insight and curious finding was that of the 53 solutions, 5 pairs share color grouping, meaning there exists exactly 48 possible ways to select color groupings that allow a balanced 3-color solution. If one were to make a 3 color solution 6 x 10 pentomino puzzle, the choice in design is either 1 or at most 2 possible solutions for that set (Fig. 4). 

Figure 4: one and two solution puzzles (laser cut acrylic and wood)
available here: 3-Color Pentominoes

Given that there are 5775 ways to place 12 items into 3 groups of 4 independent of order, it is now clear that unless the makers of the Discovery Toys pentominoes purposefully designed the set to allow a 3-color solution, it is unlikely (1 out of 120) a random selection of a color set will allow for such. It turns out that with the coloring provided in this Discovery Toy set, it is impossible to construct any of the 53 balanced 3 color solutions.

Tiling a rectangle with balanced 6x10 3-color solutions

These 48 solutions can produce an aesthetic tilling of an 8 x 6 rectangular configuration of 6 x 10 solutions, making a rectangle 60 unit squares wide by 48 unit squares tall. Coloring is still the only method used to allow the recognition of the pentomino shapes, so we still require that each pentomino not touch the side of a similarly colored neighbor, but we relax the coloring restriction to what I will call loose coloring, in which we allow corners of similar colored tiles to touch. Using such loose coloring allows the eye to discern the boundaries between the 6x10 balanced color solutions, and at the same time one can still clearly demark the individual pentomino tiles. There are more than N=48! ways to order these 48 tiles, so it seems likely that solutions might exist for the above describes criteria. A search using a simple backtracking algorithm coded in Visual Basic found the following solution after checking 103 million configurations (Fig. 5).

Figure 5: Aesthetic tilling of an 8 x 6 rectangular configuration of 6 x 10 solutions

[1] Golomb, Solomon W. (1994). Polyominoes (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-02444-8

[2] Clarke, Andrew L. Polyominoes  

[3] Muñiz, Alexandre. The Happiest and SaddestTilings, June 15, 2016 

Friday, October 1, 2021

The Mirascope

I saw my first mirascope upon my initial visit to the Exploratorium when I was eight. I can still recall my astonishment. The exhibit entices you to pick up an illuminated spring, about four centimeters high and two centimeters in diameter— yet when you reached out to touch it, the spring is simply just not there! This was some serious physics magic! Sometimes mistaken for a hologram, this image is not produced using a LASER with the physics of interference and diffraction, but instead produced only by mirrors and reflection.

Here is a demonstration of a mirascope:

The physics of the mirascope is fairly simple and yet the resulting 3D ghostly image is astonishing in its appreance. The mirascope consists of two parabolic mirrors facing each other in a clamshell fashion. The key to the design is that the focal point of each parabolic mirror sits at the vertex of the other, and a hole is made in the top mirror's vertex where the image is produced. To understand how reflection of light can create such an image, consider the special geometry of a parabola. A ray diagram illustrates how parallel rays of light that reflect off a parabolic curve will all meet at its focus (figure 1). This is the operating principle of satellite dishes or any parabolic reflector. It of course works in reverse: a light source located at the focus will reflect off the curve and leave the dish as parallel rays, a phenomena used by microwave communication antennas and searchlight reflectors.

figure 1: Parallel rays reflect and converge at the focal point F
Placing two parabolic mirrors into the mirascope configuration (as seen in figure 2) puts the object to be viewed at one focus. The light leaving the object at this focal point reflects off the top mirror into parallel rays directed down. These rays then hit the bottom mirror which reflects them a second time to converge at the top focal point, creating the image at the top.

figure 2: Diagram included on the packaging
of the Opti-Gone Mirage
Amazingly, the mirascope was discovered by accident. Here’s a brief summary of the account (as described in these student conference proceedings by Adhya and Noé, page 367).  Sometime around 1969 a custodial worker at UC Santa Barbara was cleaning out a storage closet in the physics department. The closet contained a collection of carefully stacked WWII surplus searchlight reflectors— parabolic mirrors, each with a hole in its center for an arc lamp to protrude through. Serendipitously, these reflectors were stacked and stored in a clamshell fashion. The worker, Caliste Landry, found that there was dust “floating” in air at the top hole of one of the reflectors that “could not be cleaned”. He reported what he found to one of the young physics faculty members, Virgil Elings, who figured out the physics of the situation. Elings and Landry were awarded a patent two years later for their “Optical Display Device”. The rights of the patent were acquired by Opti-Gone International in 1977, and for decades Opti-Gone was the main seller of mirascopes which they marketed under the name “Mirage”. Elings went on to found Digital Instruments Inc. in the 1990s, where he attained many patents on scanning probe microscopy—  however, the mirascope patent, a physics toy, was his first!