1

This picture made me wonder what is the largest common rectangle in the picture below ( if any ( without allowing rotation)? Next question given n distinct letters what is the largest possible 2d covering ( i.e. putting letters in a grid ) before there are 2 common rectangles of one with side having length of n letters.

Is it possible to create arbitrary large 2d grids without having 2 common squares of sides $n^2$ length?

I guess these are questions analogous to greatest common sequence.

I could only find $ \begin{array}{lcr} \mbox O & O \\ \mbox O & G \\\end{array} $

enter image description here

jimjim
  • 9,675
  • What is a "common rectangle"? – Gerry Myerson Mar 17 '14 at 12:07
  • See http://math.stackexchange.com/questions/710728/describing-the-sequence-a224239 for the number of ways to cut a grid into square sub-grids. Taking the contents of the grids into account, like searching for identical contents, looks like a slightly more intricate task. – Wouter M. Mar 17 '14 at 12:26
  • @GerryMyerson : I don't know how better to describe it, in case of 1D, consider a sequence, it is longest common sequence that can be found in more than 1 place in the sequence . – jimjim Mar 17 '14 at 20:50
  • Any thoughts about my answer? – Gerry Myerson Mar 19 '14 at 12:27

1 Answers1

2

I think there is one piece that is easy to answer, "Is it possible to create arbitrary large 2d grids without having 2 common squares of sides $n^2$ length?"

I'll interpret this as asking, given $n$ distinct symbols, is it possible to create an arbitrarily large grid without having two identical squares of side $n$?

But of course there are only finitely many distinct order $n$ squares on $n$ symbols, namely, $n^{n^2}$. As soon as your grid is large enough, it will have more than $n^{n^2}$ order $n$ squares, so, by the Pigeonhole Principle, it will have two identical order $n$ squares. Indeed, the number of order $n$ squares in an order $t$ square grid is $(t-n+1)^2$, so as soon as $t\gt n^{n^2/2}+n-1$, there will be a repeated order $n$ square.

For example, for $n=2$, any $6\times6$ grid must have a repeated $2\times2$ square. I wonder whether a $5\times5$ grid can avoid a repeated $2\times2$. There are 16 different $2\times2$ squares on 2 symbols, and a $5\times5$ grid has 16 $2\times2$ squares, so there's enough room for them all to be different --- but is it actually possible?

Gerry Myerson
  • 179,216