0
$\begingroup$

I noticed a stable stacking behavior of elements on a grid, and I'm looking for a general understanding of that property.

Consider the following grid:

o o o x o
o o o y o
o o o o o
o o o o o

Let’s assume that:

  • The grid has a constant width of n elements,
  • The elements flow left-to-right, top-to-bottom,
  • New elements are added from the top left.

Now here’s what I find interesting: x will stay on top of y whenever we add a new item. In fact, all vertical stacking is conserved.

Here’s the grid after we add z:

z o o o x
o o o o y
o o o o o
o o o o o
o

Next we add 1:

1 z o o o
x o o o o
y o o o o
o o o o o
o o

Notice how x is still on top of y. And I bet that 1, x and y will remain vertically aligned as well. I find this remarkable!

I'd like to know about a proof of this behavior, and which is the mathematical framework that provides a general understanding of it.

PS: I made computer simulations to explore this behavior: https://www.achrafkassioui.com/notes/stacking-property/

Thank you!

$\endgroup$
0
$\begingroup$

We just need to understand what happens whenever you add a new element at the top left corner. As far as I'm concerned, the rules you provided were pretty unclear. But judging from the example you provided, when you insert a new element you basically

  1. Shift every column one position to the right "circularly" (the last column becomes the first column)
  2. Shift every element in the first column down by one position
  3. Put the new element in the now "empty" top-left corner

Every step in the above insertion procedure will always preserve the "vertical" order of every column, since every column basically always move as an atomic block. Another side remark, after exactly $n$ insertions, you will obtain your initial grid shifted down by one position, with the $n$ elements you inserted in the top line. So you also have some sort of "horizontal order" stability. Every $n$ element inserted, you're in the same column as $n$ insertions prior, and your left and right neighbours (if they exist) are also the same.


A little bit more formally, say you have an infinite sequence of elements $(x_k)\in X^{\mathbb N}$. For simplicity let's work with integers, $x_k=k$. Your problem can be summed up as how to display the $N$ first integers in a grid of width $n$ such that integers on the topmost lines are bigger than in lines below, within a line the leftmost are bigger than on the right, and there are no "holes" in the grid. This basically just a matter of performing the euclidean division on integer $k$. Intuitively, every slice of $n$ consecutive integers will constitute a line. The quotient yields the line number, while the remainder is the column number.

For any $0\le k<N$, there exists two integers $I_{k,N},J_{k,N}$ such that

  • $0\le I_{k,N}$
  • $0\le J_{k,N}< n$
  • $N-1-k=I_{k,N}\times n+J_{k,N}$

If you index your grid columns/lines from $0$, and want to display the integers $0,\ldots,N-1$, then integer $k$ should be put on the $I_{k,N}$-th line and the $J_{k,N}$-th column.

It is pretty straightforward to see that the only integer $l$, $0\le l< N$, that satisfies $I_{l,N}=I_{k,N}+1$ and $J_{l,N}=J_{k,N}$ must be $l=k-n$: \begin{align*} &N-1-l=I_{l,N}\times n+J_{l,N}=(I_{k,N}+1)\times n+J_{k,N}=N-1-k+n\\ &\iff l=k-n \end{align*} That relationship remains unchanged even when you vary the value of $N$ (given that both $k$ and $l$ are still displayed in the grid). Say you have $N\neq M$ such that $0\le k,l< M$. Then by definition $M-1-k=I_{k,M}\times n+J_{k,M}$. We deduce $M-1-l=M-1-k+n=(I_{k,M}+1)\times n+J_{k,M}=I_{l,M}\times n+J_{l,M}$. In other words we still have $I_{k,M}+1=I_{l,M}$ and $J_{k,M}=J_{l,M}$. In other other words, $k$ is still right above $l$.

That in particular means that every column will be "preserved", no matter how many more elements you display/insert. For that matter, you could also remove elements.

The "horizontal" stability is even more straightforward, the grid is just one long sequence of consecutive integers that you sliced into smaller lines. The number on your right will always be the same, until successive insertions have pushed you on the last column, at which point the next insertion will reunite you with your right neighbour. Likewise for your left neighbour. If you really want to, you can go through the values of $I_{k,N}$ and $J_{k,N}$ again.


More generally, are there any mathematical framework concerned with the study of these types of problem? Honestly, I don't know. "Stacking elements in a grid" doesn't ring a bell at all. The closest thing I can think of, is a problem that is concerned about how to arrange small boxes inside a bigger box, so as to occupy the maximum volume in the big box. That particular problem would be part of computational geometry I guess.

Actually, the right answer for you probably depends what you want to do from there. If the important part was working on the grid, then you could try to have a look at digital geometry, which can be summarized as geometry in $\mathbb Z^d$ rather than $\mathbb R^d$. For grids of more arbitrary shapes, maybe check out lattices or even graph theory? Technically, your grid can also be interpreted as an image, so image processing is also on the table here.

Ultimately, if you're not studying maths purely for the maths, it all hinges on what you want to do with the maths. One nice thing about maths is that you have a multitude of points of views, some of which are adapted to study your problem, some of which aren't. It's the ability to switch formally from one point of view to another that makes it such a nice and powerful tool. Without a rough idea of what it is you want to do, it is that much harder to direct you to the right "mathematical framework".


In your page of simulations you ask what would have a mathematician done?. If a real mathematician reads this, feel free to correct me. But I believe that they'd establish a rigorous model of whatever system/object they want to study, then formulate the property they want to prove under formal terms in that model.

You yourself observed that by making your grid a line, inserting new elements was just a way to move the line to the right. That's fairly easy to describe "mathematically" as an ordered sequence of elements. All I did above was then to work out from that order of elements, to then go back to the fixed width grid. In doing so, you can work on the properties you have as an ordered sequence to deduce properties in terms of the grid.

$\endgroup$
  • $\begingroup$ The rules I provided should be familiar to web users. For example, that's how a classic grid on the web works: new items are added at the start of the list, and the web browser reflows the items left-to-right (for left-to-right languages) and top-to-bottom. Regarding your other observations, I got similar ones by doing computer simulations here achrafkassioui.com/notes/stacking-property and I am looking for a deeper analytical understanding. $\endgroup$ – Ache Oct 27 '17 at 21:14
  • $\begingroup$ @Ache What kind of deeper analytical understanding? The most formal thing I can think of would just be modulo arithmetic, although it would probably get boring pretty fast. As far as logic/intuition goes, the whole thing boils down to simply, each column always moving together. $\endgroup$ – N.Bach Oct 27 '17 at 21:54
  • $\begingroup$ I don't know, otherwise I'd have found it. Any pointer to which framework studies the stacking of elements on a grid, the different kinds of transformations we can do, the stability of a given shape under given transformations, etc. $\endgroup$ – Ache Oct 27 '17 at 22:31
  • $\begingroup$ In the playground section of the experiments linked above, I added a preset called "Column" that visualizes your description of the system. $\endgroup$ – Ache Oct 28 '17 at 2:10
  • $\begingroup$ @Ache for some reason I can only see the presets "cross" and "together", I'll check it out later. I've also added a few elements to my answer, but I doubt it will satisfy you in any way... in the sense that I can't come up with any "deeper" meaning than what you basically observed on your own already. The only "deeper" interpretation I have to offer, is that we're basically working on a representation of a line. Are there any other, more interesting interpretations? No clue. $\endgroup$ – N.Bach Oct 28 '17 at 2:36

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.