32
$\begingroup$

Story

I was bored sitting in front of my computer and using a rectangle to select icons on my screen. I could select $1$, $2$, $3$, $4$, but not $5$ icons.

grid1

(Black squares are the icons. Note that it is possible to find rectangles with $1$, $2$, $3$ ad $4$ black squares in respectively.)

So I rearranged the icons into the following arrangement:

grid2

So in this arrangement, there exists a rectangle that includes $i$ black squares, where $1 \le i \le 6$. However, on the other hand, $6$ is not the maximum. For example, we can actually achieve $7$ with this arrangement.

grid3

Problem Formulation

$a$ is a $n$-iconic number if there exists an arrangement function $f:\{ x \in \mathbb{Z} | 1 \le x \le n\}^2 \rightarrow \{ 0, 1\}$, such that for $1 \le i \le a$, there exists a quadruple $(\alpha_i, \beta_i, \gamma_i, \delta_i)$ such that $$\sum_{j = \alpha_i}^{\beta_i} \sum_{k = \gamma_i}^{\delta_i} f(j, k) = i$$

Find the maximum $n$-iconic number.

If $a$ is an iconic number with an arrangement function $f$ with an additional criterion $$\sum_{j = 1}^n \sum_{k = 1}^n f(j, k) = a$$ then $a$ is $n$-perfect iconic

Is the maximum $n$-perfect iconic number the same as the maximum $n$-iconic number?

Find the maximum $n$-perfect iconic number.

Small Cases

For $n = 4$, the greatest iconic number and the greatest perfect iconic number is $12$, by the following construction:

grid4

$\endgroup$
2
  • $\begingroup$ You seem to be using the letter $n$ for two different things. Also, $a_i$ and $a_n$ don't seem to correspond. $\endgroup$
    – S. Carnahan
    Jul 25, 2011 at 1:12
  • $\begingroup$ @ S. Carnahan: Thanks for pointing that out. Edited. $\endgroup$ Jul 25, 2011 at 2:00

5 Answers 5

15
$\begingroup$

I'm getting an upper bound of $n^2 - O(n^{\frac{4}{3}})$, as follows.

Given $n$, choose $a$ with $0 < a < n$. Any rectangle containing more than $n^2-an$ icons must have both length and width at least $n-a+1$. But it's easy to count such rectangles; there are $\frac{1}{4}a^2 (a+1)^2$. So, the maximum iconic number is bounded by $n^2 - an + \frac{1}{4}a^2 (a+1)^2$, for any $a$.

Choosing $a$ on the order of $n^{\frac{1}{3}}$ gives the bound $n^2 - O(n^{\frac{4}{3}})$.

$\endgroup$
2
  • $\begingroup$ Sorry, I'm new here... I think I should have made this a comment. Could a moderator fix it for me (and then delete this)? -- Brian $\endgroup$ Aug 1, 2011 at 0:38
  • 2
    $\begingroup$ Welcome to MO Brian! There is no need to fix this, new users can only comment on their own posts until they accumulate a few mathoverflow points. Also, you can edit this answer later if you want to add more observations. $\endgroup$ Aug 1, 2011 at 0:58
14
$\begingroup$

Brian's upper bound of $n^2-O(n^{4/3})$ is tight. To check the lower bound consider placing an icon in the following four regions:

  • On points with coordinates $(a,b)$ which satisfy $a\le n-\lfloor\sqrt[3]{n}\rfloor$ and $\lfloor\sqrt[3]{n}\rfloor\le b\le n-\lfloor\sqrt[3]{n}\rfloor$.
  • On points with coordinates $a=n-\lfloor \sqrt[3]{n}\rfloor -1$ and $b \le \lfloor \sqrt[3]{n}\rfloor -1$
  • On points with coordinates $n-2\lfloor \sqrt[3]{n}\rfloor\le a\le n-\lfloor \sqrt[3]{n}\rfloor -1$ and $b\geq n-\lfloor \sqrt[3]{n}\rfloor $
  • On points with coordinates $a \geq n-\lfloor \sqrt[3]{n}\rfloor$ and $\sqrt[3]{n}\le b\le \sqrt[3]{n^2}-\sqrt[3]{n}+1$
The idea is that one can choose rectangles so that from the total you are subtracting any number that can be written as $p (n-2\lfloor\sqrt[3]{n}\rfloor)+q$, where $q$ can be any $3$ digit number in base $\lfloor\sqrt[3]{n}\rfloor$ and $p\le n-\lfloor\sqrt[3]{n}\rfloor$.

Note that this asymptotics rules out most of the sequences mentioned by Gerry in the comments below. It also makes me believe that there is no closed form formula.

If we denote the largest $n$-perfect iconic number by $f(n)$ and the largest $n$-iconic number by $g(n)$, the next question would be to determine $$\alpha=\lim_{n\to \infty} \frac{n^2-f(n)}{n^{4/3}}\geq \lim_{n\to \infty}\frac{n^2-g(n)}{n^{4/3}}=\beta$$ Brian's upper bound says that $\beta\geq \frac{3}{4}$, while my lower bound says that $\alpha\le 3$.

$\endgroup$
2
  • 1
    $\begingroup$ I think the largest $4$-perfect iconic number is $12$, the construction is attached in the problem up there because comments doesn't seem to support graphics. $\endgroup$ Jul 25, 2011 at 10:00
  • $\begingroup$ @Kenneth, I updated the post with a non-trivial bound. $\endgroup$ Aug 1, 2011 at 11:51
9
$\begingroup$

I have done some computer calculations. Here is another small case. The following arrangement, with 19 icons, is best possible for $n=5$, and is also perfect:

Best five-by-five arrangement http://www.srcf.ucam.org/~jdc41/best5.jpg

I've had a quick look at $n=6$. I have a perfect arrangement of 27, and an imperfect arrangement achieving 29. I don't know if either is best possible yet.

$\endgroup$
3
  • 1
    $\begingroup$ There are 10 entries at the Online Encyclopedia of Integer Sequences that start 1, 3, 7, 12, 19, and all of them continue with 27 or 28 or 29 (except for the one where the 6th term is unknown), but none of the descriptions makes any reference to the sort of thing we're looking at here. Still, maybe one of those sequences is what we're looking for. $\endgroup$ Jul 26, 2011 at 2:53
  • $\begingroup$ Is the n=5 arrangement you give the only one realising a = 19? $\endgroup$ Aug 1, 2011 at 2:59
  • $\begingroup$ No, Peter, there are 168 perfect configurations of 19 icons in a $5\times 5$ grid, counting rotations and reflections as distinct. So, assuming there are no small orbits under the action of $D_8$ (which I think is reasonable, since symmetry is a bad thing in this game, but I haven't been bothered to check), there are 21 configurations which are distinct up to symmetry. $\endgroup$ Aug 1, 2011 at 12:33
2
$\begingroup$

This seems to be a (sort of) 2-dimensional version of Golombs ruler, which itself is hard: http://en.wikipedia.org/wiki/Golomb_ruler

$\endgroup$
4
  • $\begingroup$ I (and I'm guessing others) would have put this as a comment rather than an answer. $\endgroup$
    – David Roberts
    Jul 26, 2011 at 2:54
  • $\begingroup$ David, indeed so would I. However I can see how some would view it as an attempt at an answer. Gerhard "There Is Some Grey Here" Paseman, 2011.07.25 $\endgroup$ Jul 26, 2011 at 4:14
  • $\begingroup$ So if we lower the dimension of the problem to 1, would we get Golombs ruler or its equivalent? $\endgroup$ Jul 26, 2011 at 4:39
  • 2
    $\begingroup$ It is not as easy as just considering 1xn-dimensional desktop arrangements, since then one could clearly create all types of rectangles. They just seems to be related in some way, maybe someone can find an explicit injection? (Prefers to write answers, since they can get wikified, and comments gets tracked). $\endgroup$ Jul 26, 2011 at 14:49
0
$\begingroup$

If you added another condition on the problem, namely that rather than just requiring a single occurrence of a rectangle of i elements, but instead to require all non-symmetrical occurrences

(so for i=3, you require there to be a 3 x 1 rectangle containing 3 elements as well as a 2x2 rectangle containing 3 elements)

(for i=4 a 4x1 rectangle, a 3x2 rectangle with an L shape in it and a 2x2 full rectangle) etc.

I believe that would reduce the problem to "placing" each of these rectangles in the 'big square' so that they all agree. Which if easily solved would place lower bounds on the problem as it stands.

This might not help but I feel it should. (I'm sorry this isn't an actual answer but I can't post it as a comment)


my other feeling is that if you wrap around it might be easier to solve?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.