Skip to Main content Skip to Navigation
Conference papers

Tiling an Interval of the Discrete Line

Abstract : We consider the problem of tiling a segment {0, . . . , n} of the discrete line. More precisely, we ought to characterize the structure of the patterns that tile a segment and their number. A pattern is a subset of N. A tiling pattern or tile for {0, . . . , n} is a subset A P(N) such that there exists B P(N) and such that the direct sum of A and B equals {0, . . . , n}. This problem is related to the di cult question of the decomposition in direct sums of the torus Z/nZ (proposed by Minkowski). Using combinatorial and algebraic techniques, we give a new elementary proof of Krasner factorizations. We combinatorially prove that the tiles are direct sums of some arithmetic sequences of speci c lengths. Besides, we show there are as many tiles whose smallest tilable segment is {0, . . . , n} as tiles whose smallest tilable segment is {0, . . . , d}, for all strict divisors d of n. This enables us to exhibit an optimal linear time algorithm to compute for a given pattern the smallest segment that it tiles if any, as well as a recurrence formula for counting the tiles of a segment.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Eric Rivals Connect in order to contact the contributor
Submitted on : Wednesday, December 13, 2006 - 3:24:25 PM
Last modification on : Friday, August 5, 2022 - 3:02:17 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 8:57:27 PM




Olivier Bodini, Eric Rivals. Tiling an Interval of the Discrete Line. CPM: Combinatorial Pattern Matching, Jul 2006, Barcelona, Spain. pp.117-128, ⟨10.1007/11780441_12⟩. ⟨lirmm-00120188⟩



Record views


Files downloads