Screensaver-inspired Lego dropping

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 224
Joined: Tue Jun 17, 2008 11:04 pm UTC

Screensaver-inspired Lego dropping

Postby lightvector » Tue Feb 02, 2016 6:56 am UTC

This was inspired by watching a screensaver of falling Lego blocks. At the moment this problem seems well out-of-my-league though to solve precisely. I'm curious if anyone has any thoughts as to an analytic approach that might work, or knows about existing results on a problem like this or theorems that might be applicable or related.

Consider an NxN horizontal grid as the ground surface of a 3D rectangular volume that extends up an arbitrary height above that ground. One at a time, drop 1x2 Lego blocks into this volume from above, uniformly randomly choosing among among all possible grid-aligned positions and orientations (N*(N-1)*2 in total). Lego blocks fall until they hit the ground or any earlier Lego block directly beneath them, and then they attach and stop falling. Keep dropping until every grid location on the ground has at least one Lego block directly above it whose height is at least H, and then consider the density of Legos below that height: the proportion of the NxNxH volume below that height that's occupied. In the limit as N and H both go to infinity, it seems to me that with probability approaching 1 the density of Legos should converge to something. What is this density?

I tried directly simulating it with varying values of N as large as 4096 and H around values like 100000, (and also with a toroidal boundary condition for the NxN plane rather than the sharp boundary condition described above), and based on the rate that the small-N bias fades away and the variation in the results, it seems like the density is a little less than 34.7%, but probably not less than 34.4%. Is there any better way to compute this value?

With a friend I also tried solving the 2x2 torus (letting H go to infinity). After modding out by symmetry, noting that two adjacent blocks must always both be the max height so far, and that a 1-square pit is already guaranteed wasted space, the state becomes only 1-dimensional, so it seems solvable, except we couldn't quite figure out how to proceed after writing down the recurrences that hold between the steady-state probabilities of these states.

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests