Current Events > probably the coolest math problem i've worked on in my undergrad experience

(+) Yeah! (+)

How many ways can one tile a 2x20 grid using Tetris pieces?

anyone care to guess?
---

4
---

bout tree fiddy
---

500

Fam_Fam posted...

500

closest one so far, but still off by quite a bit
---

Pretty sure there are 35 ways to do it.
---

well you can't use Z/S/T so it's not as many as it first seems
---

tiornys posted...

Pretty sure there are 35 ways to do it.

Scratch this, I'm not thinking about the square blocks correctly.
---

kirbymuncher posted...

well you can't use Z/S/T so it's not as many as it first seems

... Yes you can.

kirbymuncher posted...

well you can't use Z/S/T so it's not as many as it first seems

yeah that's true, i just thought the result for any 2x2n sized grid was cool af. especially when you work for like 45 minutes trying to get the recurrence relation system of equations

and i doubt the result is actually anything crazy deep or something, but it was still like "oh shit" when we found the 5th non-trivial answer
---

clearaflagrantj posted...

kirbymuncher posted...

well you can't use Z/S/T so it's not as many as it first seems

... Yes you can.

no, you can't. he's correct, actually
---

clearaflagrantj posted...

kirbymuncher posted...

well you can't use Z/S/T so it's not as many as it first seems

... Yes you can.

How do you transition from a single tile hanging end to a double tile end without leaving an open space?
---

tiornys posted...

clearaflagrantj posted...

kirbymuncher posted...

well you can't use Z/S/T so it's not as many as it first seems

... Yes you can.

How do you transition from a single tile hanging end to a double tile end without leaving an open space?

Well I'm a dumbass

any other guesses before i post it?
---

If I didn't screw up my stars and bars counting, 1021.
---

tiornys posted...

If I didn't screw up my stars and bars counting, 1021.

Nope, this is wrong too, I'm double counting a bunch of stuff.
---

424

Do I win
---

tiornys posted...

tiornys posted...

If I didn't screw up my stars and bars counting, 1021.

Nope, this is wrong too, I'm double counting a bunch of stuff.

No, actually I've convinced myself that I'm not double-counting. So 1021, and here's the reasoning:

Can't use S, Z, or T shapes. That leaves lines, which must always be in pairs covering a 2x4 grid, L's, which similarly must be paired in a 2x4 grid, or squares. Squares have to be paired with other squares but they can float freely among any 2x4 grids of L's or lines. So, we have 6 cases: 0 squares, 2 squares, 4, 6, 8, or 10 squares.

If 0 squares, there are 5 2x4 blocks filled with lines or L's. L's can come in two polarities, so that's three choices per 2x4 block, for 15 possibilities.

If 2 squares, there are 4*3=12 ways to pick the 2x4 grids. Multiply by the 6!/(2!4!) ways of arranging the 2 squares around the 4 2x4 grids, and that's 180 more possibilities.

If 4 squares, there are 3*3=9 ways to pick the 2x4 grids. Multiply by the 8!/(4!4!) ways of arranging 4 squares around the 3 2x4 grids for 630 possibilities.

If 6 squares, there are 2*3=6 ways to pick the 2x4 grids. Multiply by the 8!/(2!6!) ways of arranging 6 squares around 2 2x4 grids for 168 possibilities.

If 8 squares, there are 3 ways to pick the 2x4 grid. Multiply by the 9 ways of arranging 8 squares on either side of the 1 2x4 grid for 27 possibilities.

10 squares adds 1 more possibility, total of 1021.

edit: aaaaand this is wrong because you can combine lines and L's to make longer grids.
---

Starting with a grid with a flat bottom, let's look at the pieces that can be dropped in.

Z/S and T: these all create illegal states and can be ignored.

L/J: After dropping an L/J, there will be an excess height of 2 on the left/right column, and 1 completed row. The only legal moves are to drop another L/J to restore the grid to a flat state with its height increased by 3 more completed rows, or drop an I to flip the column with the height differential while completing 2 rows.

I: After dropping an I, one column will have a height differential of 4. The only move is to drop one more I, increasing the height by 4 overall.

O: After dropping an O, you've simply increased the height by 2.

We see that the only legal states of the grid are to have a height differential of 0, 2, or 4. We now summarize the legal moves in each state, and the state that you advance to after playing the piece. A suffix of L or R indicates the side of a height differential and, in the case of an I block, the side the block is dropped on. The author regrets the overloading of capital L in this case but points his finger at GameFAQ's lack of Unicode support. We also leave the rotation of L/J pieces ambiguous as there is only one valid rotation for each state.

0:
O -> 0 (+2)
L -> 2L (+1)
J -> 2R (+1)
IR -> 4R (+0)
IL -> 4L (+0)

2L:
L -> 0 (+3)
IR -> 2R (+2)

2R:
J -> 0 (+3)
IL -> 2L (+2)

4L:
IR -> 0 (+4)

4R:
IL -> 0 (+4)

We have now defined all of the legal state transitions and their effect on the number of completed rows. Perform a depth-first search, terminating the branch when you hit a node that has more than 20 completed rows. Every time you encounter a 0-state node with height 20, count it and terminate the branch.

I am not doing this the combinatorics way.
---

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

---

Pretty cool. I decided my tools (breaking down every case) were too inefficient for the time I had available. Neat to see an elegant way of deriving the solution.
---

i am going to miss this class

also yo @Frostshock you should totes help me with my linear/nonlinear programming problem :))
---

you taking discrete math?
---

no. combinatorics, interest theory, linear/nonlinear programming, and physical organic chemistry. last semester, no time/room for discrete.

edit: wasn't sure if you were asking currently if or if i'd planned on it
---

that's a pretty neat answer
---

So I was bored and coded this.



You can see how the ratio of the terms approaches phi² = phi + 1.
---

organicbamf posted...

(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)

You only need the first two as initial conditions. And a recursion is definitely the best way to go with this problem.

Let a_n be the number of ways to tile a 2x2n grid. Then by considering the left-most blocks, we get

a_n = a_{n-1} (from square) + a_{n-2} (from two I's) + 2(a_{n-2}+a_{n-3}+...+a_0) (from L and I interpolation and symmetry), with a_0=a_1=1.

This appears to be the square of the Fibonacci number F_{n+1} and letting b_n=(F_{n+1})^2, it's easy work out that b_n satisfies the same recurrence as the a's with the same initial conditions.