Icon Arrangement on Desktop - MathOverflow

Icon Arrangement on Desktop

2011-07-24T21:31:36Z

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.

(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:

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.

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:

Answer by Gjergji Zaimi for Icon Arrangement on Desktop

2011-07-25T03:59:19Z

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$.

Answer by James Cranch for Icon Arrangement on Desktop

2011-07-25T14:50:11Z

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:

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.

Answer by Per Alexandersson for Icon Arrangement on Desktop

2011-07-25T20:12:36Z

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

Answer by Brian Lawrence for Icon Arrangement on Desktop

2011-08-01T00:34:26Z

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}})$.

Answer by Karl Waugh for Icon Arrangement on Desktop

2011-08-18T23:29:01Z

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?