LogFAQs > #878304639

a lot of good effort yo, i dunno how to do it any other way than a recurrence relation tbh


So your starting positions are placing an I block, J block, L block, and O block. In fact those are the only ones you can place. Call the sum of those positions a_n.
If you place an O block, you get the same configuration as before, so call that next position a_(n-2)
if you place an I block, call this next position b_n, you are forced to place another I block. So this is actually like doing 2 O blocks, so b_n = a_(n-4).
If you place a J block, you have n-1 tiles on top and n-3 tiles on bottom. Call this configuration c_n. from there you have two choices: an I block, giving n-3 on top and n-5 tiles on bottom. This is the same configuration, except one iteration further, so this first choice results in c_(n-2). Otherwise you must place a J block, which leaves n-4 tiles on top, and n-4 tiles on bottom. Which is just a_(n-4). So c_n = c_(n-2) + a_(n-4).
Finally, if you place an L block, by symmetry it results in the exact same outcome as an initial J block placement. So let d_n = c_(n-2) + a_(n-4). Or, for brevity, we can just combine them in the a_n equation.
We now have a system of recurrence relations:

a_n = a_(n-2) + b_n + 2*c_n
b_n = a_(n-4)
c_n = c_(n-2) + a_(n-4)

Now we need a couple of seeds to get the recursion started. Recall that a_n designates a grid size of 2x2n.
a_0 = 1, since is one way to place the pieces on a 2x0 grid--you don't/can't.
a_1 = 0, because no tiles fit
a_2 = 1, a single O block fits on a 2x2 grid
a_3 = 0, again no tiles fit. In fact, no odd numbered n values allow tiling.
a_4 = 4, {O,O}, {L,L}, {J,J}, {I,I}
c_4 = 1, since it's a grid of 3 on top, 1 on bottom, it only fits a J block
c_6 = c_(4) + a_(2) = 1 + 1 = 2

(I'm not sure if the above suffices for all seeds, we did more and I'm trying to cut out unneeded stuff, but I think it does)

So it turns out the pattern is (continuing from above):
a_6 = 9
a_8 = 25
a_10 = 64
etc.

that is, for a_n, take the ((n/2)+1)th fibonacci number and square it (where the seeds are 1 and 1, not starting at 0)
so a_20 = ((20/2) + 1) = 11th fibonacci squared = 89^2 = 7921

---

get ready for a backside attack ;)