Which polyominos (with orientation) of $n$ squares, requires the least number of different colors, $c(n)$, such that if this polyomino is placed anywhere on an optimally colored infinite square grid of $c(n)$ colors, it will have all its squares placed on different colors?
And which polyomino(s) require the most colors, and how many colors as a function of $n$?
Also: How to show that a finite number of colors (depending on n), suffices for any subset of n unit-m-cubes, in Z^m?