Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
You seem to be using the letter $n$ for two different things. Also, $a_i$ and $a_n$ don't seem to correspond. –  S. Carnahan Jul 25 '11 at 1:12
    
@ S. Carnahan: Thanks for pointing that out. Edited. –  Kenneth Hung Jul 25 '11 at 2:00

5 Answers 5

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

share|improve this answer
1  
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. –  Kenneth Hung Jul 25 '11 at 10:00
    
@Kenneth, I updated the post with a non-trivial bound. –  Gjergji Zaimi Aug 1 '11 at 11:51

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

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.

share|improve this answer
1  
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. –  Gerry Myerson Jul 26 '11 at 2:53
    
Is the n=5 arrangement you give the only one realising a = 19? –  Peter LeFanu Lumsdaine Aug 1 '11 at 2:59
    
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. –  James Cranch Aug 1 '11 at 12:33

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

share|improve this answer
    
I (and I'm guessing others) would have put this as a comment rather than an answer. –  David Roberts Jul 26 '11 at 2:54
    
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 –  Gerhard Paseman Jul 26 '11 at 4:14
    
So if we lower the dimension of the problem to 1, would we get Golombs ruler or its equivalent? –  Kenneth Hung Jul 26 '11 at 4:39
2  
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). –  Per Alexandersson Jul 26 '11 at 14:49

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

share|improve this answer
    
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 –  Brian Lawrence Aug 1 '11 at 0:38
2  
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. –  Gjergji Zaimi Aug 1 '11 at 0:58

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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