Arithmetic Progressions in T-Tetromino Tilings

20x20AP5This page records progress in some student research into this problem: When must tilings of rectangles with T-tetrominos contain an arithmetic progression (AP) of a given length?

For example, the tiling shown to the right, of a 20×20 square, contains the 5-term AP, as shown in red. So, by an AP of T-tetrominos, we mean Ts that are equally spaced, and all in the same orientation.

Not all tilings of a 20×20 square contain a 5-term AP of Ts. In fact, it is possible to find a tiling of that square that doesn’t even have a 3-term AP of Ts.

Challenge 1: Find such a tiling.

I will present one in a subsequent post.

Guiding Question 1: What APs must appear in 4xN rectangles?

For our first exploration, we are looking into tilings of 4xN rectangles, and want to answer this question: Given a value l, is there a value N such that every tiling of a 4xN rectangle must contain an l-term AP? Emily has proven that the answer to this question is “yes,” and details can be found on her
blog posting of October 22.

It was a somewhat dramatic development from the week before. At that research meeting, we noticed that the 2nd and 3rd Tiling-AP numbers were exactly four times the corresponding van der Waerden numbers. And so, even though the first Tiling-AP number did not fit that pattern, we nevertheless suspected that all the others would. And that’s what Emily was able to prove.

Computational Results.

Emily is learning Python as part of this research endeavor. You can read about it in some of her earlier blog posts. Elizabeth, who is already adept at Python, wrote code that could tile arbitrary 4Mx4N rectangles, which we were able to use to explore arithmetic progressions in other rectangles. Unfortunately, Python is somewhat slow, so I contributed a C++ version of Elizabeth’s code, and together we used it to explore:

Guiding Question 2: What rectangle dimensions force 3-term APs?

We use the notation (A, B) -> l to mean that any tiling of an AxB rectangle must contain an l-term AP. We sought to discover all pairs (A, B) such that (A, B) -> 3. Emily had already solved this when one of A or B was 4. We thus knew that (4, B) -> 3 if and only if B >= 36. And by symmetry, (A, B) -> l if and only if (B, A) -> l . This gave us a finite range of other A‘s to explore: 8, 12, 16, 20, 24, 28, 32. We began by running our C code on various size rectangles, but the running times rapidly became prohibitive. For example, it took over 2 hours to explore an 8×36 rectangle, where we verified that every tiling did indeed force a 3-term AP. With Emily’s talk just two days away, Elizabeth and I really wanted to fully characterize these rectangles. Fortunately, after going over the code together, we were able to discover an opportunity to prune the search tree, and speed these explorations up from hours to seconds! See Elizabeth’s post, for details.


Advertisements