Problem Background*
The mat at your karate dojo composed of 160 square interlocking foam tiles. Along each edge of each tile, there are has five "teeth" (10cm long) and five spaces-for-teeth (again 10cm long) so that the tiles will interlock. The overall mat is 10 tiles long 16 tiles wide. When the dojo first receives tiles from the factory, they measured $1$m along their width and length. After years of use, however, they were worn down and stretched out. Different areas of the mat were stretched out more than others. Eventually, gaps began to appear at the perimeter of the mat where tiles were pulling away from each other.
As part of the annual dojo clean-up, the mat was completely taken apart and the tiles all thrown into a pile (scrambling their order). A few tiles that had extra damage (broken teeth, etc) so they were discarded and replaced with brand new tiles delivered from the factory.
As you begin to reassemble the mat, you notice the following: For any two tiles selected at random, you can force their edges to interlock. But when more tiles are added to the mat, the gaps start to form again, and you’re not able to force them closed.
As a test, you assemble a strip of 10 of the most worn-out tiles and a strip of 10 brand new tiles and lay the two strips side by side. The strip of worn-out tiles appears to be one "tooth" (or $10$cm) too long. Based on this, you estimate the most-worn out tiles are now $1.01$m along each edge. Furthermore, you stack one of the new tiles on top of old tiles, line up one corner, look at the opposite corner, and confirm that older tile has expanded by about $1$cm in both length and width.
*inspired by true events.
Formulation
Feel free to abstract the problem into an $M\times N$ mat, where tiles have $P$ teeth along each edge, and tile edges grow by (at most) a factor of $Q$ upon being stretched out.
Some Other Assumptions:
- the tiles were stretched out equally in both width and length. They are still square; they haven't become rectangular.
- The tiles were not skewed. Still square; not rhomboidal or trapezoidal.
What procedure or algorithm could be used to re-assemble the tiles in a way that will minimize the formation of any gaps?
