Block recomposition (Humpty Dumpty)
define two operations: SELECT and TRANSLATE.
Start with an initial configuration of identical tiles, \(C\)
SELECT a random set of tiles, below the green ones have been selected.
TRANSLATE them to the right by 4 and up by 1. Generally any translation is allowed with condition that no overlap between two tiles results.
Again, SELECT some tiles at random. Here the purple tiles are selected.
Again, TRANSLATE: right 2, down 4.
Remove all trace of the operations that occured.
Here's the problem.
If you are handed this end configuration without any knowledge of the operations and only the knowledge of the initial configuration \(C\) then what is the minimal number of (SELECT & TRANSLATE) operations required to return the tile configuration back to \(C\). Proof? For the general case?
Is this a known problem?