Tiling the Line with Triples

Abstract

It is known the one dimensional prototile $0,a,a+b$ and its reflection $0,b,a+b$ always tile some interval. The subject has not received a great deal of further attention, although many interesting questions exist. All the information about tilings can be encoded in a finite digraph $D_{ab}$. We present several results about cycles and other structures in this graph. A number of conjectures and open problems are given.In [Go] an elegant proof by contradiction shows that a greedy algorithm will produce an interval tiling. We show that the process of converting to a direct proof leads to much stronger results.

Keywords

• tiling
• one dimension
• direct proof
• [info] computer science [cs]
• [info.info-cg] computer science [cs]/computational geometry [cs.cg]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]