Icon Arrangement on Desktop - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:36:52Z http://mathoverflow.net/feeds/question/71156 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71156/icon-arrangement-on-desktop Icon Arrangement on Desktop Kenneth Hung 2011-07-24T21:31:36Z 2011-08-18T23:29:01Z <h2>Story</h2> <p>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.</p> <p><img src="https://lh5.googleusercontent.com/-l3UqBRYypPM/TixduOesvII/AAAAAAAAAnI/sZK1hrqBmWY/Icons1.png" alt="grid1"></p> <p>(Black squares are the icons. Note that it is possible to find rectangles with $1$, $2$, $3$ ad $4$ black squares in respectively.)</p> <p>So I rearranged the icons into the following arrangement:</p> <p><img src="https://lh6.googleusercontent.com/-tAaE_4tPOc8/TiyHGeNM9VI/AAAAAAAAAnc/f06oCkVuFiI/Icons2.png" alt="grid2"></p> <p>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.</p> <p><img src="https://lh3.googleusercontent.com/-mcle_k-DQlc/TiyJjMDaRqI/AAAAAAAAAng/fcpdXXA4Aqg/Icons3.png" alt="grid3"></p> <h2>Problem Formulation</h2> <p>$a$ is a <em>$n$-iconic number</em> if there exists an <em>arrangement function</em> <code>$f:\{ x \in \mathbb{Z} | 1 \le x \le n\}^2 \rightarrow \{ 0, 1\}$</code>, 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$$</p> <blockquote> <p>Find the maximum $n$-iconic number.</p> </blockquote> <p>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 <em>$n$-perfect iconic</em></p> <blockquote> <p>Is the maximum $n$-perfect iconic number the same as the maximum $n$-iconic number?</p> <p>Find the maximum $n$-perfect iconic number.</p> </blockquote> <h2>Small Cases</h2> <p>For $n = 4$, the greatest iconic number and the greatest perfect iconic number is $12$, by the following construction:</p> <p><img src="https://lh3.googleusercontent.com/-vwjZLdLR4Qs/Ti0-EAYJNGI/AAAAAAAAAoA/DlxPhvYZahQ/Icons4.png" alt="grid4"></p> http://mathoverflow.net/questions/71156/icon-arrangement-on-desktop/71179#71179 Answer by Gjergji Zaimi for Icon Arrangement on Desktop Gjergji Zaimi 2011-07-25T03:59:19Z 2011-08-01T19:46:06Z <p>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: <ul> <li>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$.</li> <li>On points with coordinates $a=n-\lfloor \sqrt[3]{n}\rfloor -1$ and $b \le \lfloor \sqrt[3]{n}\rfloor -1$ <li>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$</li> <li>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$</li> </ul> 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$.</p> <p>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.</p> <p>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$.</p> http://mathoverflow.net/questions/71156/icon-arrangement-on-desktop/71231#71231 Answer by James Cranch for Icon Arrangement on Desktop James Cranch 2011-07-25T14:50:11Z 2011-07-25T14:50:11Z <p>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:</p> <p><img src="http://www.srcf.ucam.org/~jdc41/best5.jpg" alt="Best five-by-five arrangement"></p> <p>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.</p> http://mathoverflow.net/questions/71156/icon-arrangement-on-desktop/71257#71257 Answer by Per Alexandersson for Icon Arrangement on Desktop Per Alexandersson 2011-07-25T20:12:36Z 2011-07-25T20:12:36Z <p>This seems to be a (sort of) 2-dimensional version of Golombs ruler, which itself is hard: <a href="http://en.wikipedia.org/wiki/Golomb_ruler" rel="nofollow">http://en.wikipedia.org/wiki/Golomb_ruler</a></p> http://mathoverflow.net/questions/71156/icon-arrangement-on-desktop/71772#71772 Answer by Brian Lawrence for Icon Arrangement on Desktop Brian Lawrence 2011-08-01T00:34:26Z 2011-08-01T00:34:26Z <p>I'm getting an upper bound of $n^2 - O(n^{\frac{4}{3}})$, as follows.</p> <p>Given $n$, choose $a$ with $0 &lt; a &lt; 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$.</p> <p>Choosing $a$ on the order of $n^{\frac{1}{3}}$ gives the bound $n^2 - O(n^{\frac{4}{3}})$.</p> http://mathoverflow.net/questions/71156/icon-arrangement-on-desktop/73191#73191 Answer by Karl Waugh for Icon Arrangement on Desktop Karl Waugh 2011-08-18T23:29:01Z 2011-08-18T23:29:01Z <p>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 </p> <p>(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) </p> <p>(for i=4 a 4x1 rectangle, a 3x2 rectangle with an L shape in it and a 2x2 full rectangle) etc.</p> <p>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. </p> <p>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)</p> <hr> <p>my other feeling is that if you wrap around it might be easier to solve?</p>