I have no idea what I’m doing and you can’t stop me.

Author, Trans Woman, Hypno Domme, Hopeless Romantic, Sadist, newly out system.

Pronouns are She/It, perpetually happy HRT gave me titties and sad it didn’t give me tentacles.

I had shame once.

Ξ

Θ Δ

Dating: @lunasorcery

18+ only


lunasorcery
@lunasorcery

Puzzle:
Including reflections as unique solutions, how many ways can you tile a 2×N rectangle with dominoes?

Choose your adventure:
If you’d like to find joy in exploring for yourself, you can stop reading here; enjoy!
If you’d like to see the answer, along with a rough proof, click below.

show solution Let’s have Fn represent the number of tilings of a 2×N rectangle. We can see that F0 and F1 are both 1 — there’s only one way to tile a zero-width rectangle (with zero tiles), and only one way to tile a 2×1 rectangle (with one tile).

For larger rectangles, consider the following:

The end of a 2×N rectangle can be filled with dominoes in two ways — a vertically-oriented domino, or two horizontally-oriented dominoes.

If we place a domino vertically at the end of our 2×N rectangle, we’re left with a 2×(N-1) space, which can be filled Fn-1 ways.

Similarly, if we place a pair of dominoes horizontally at the end of our 2×N rectangle, we’re left with a 2×(N-2) space, which can be filled Fn-2 ways.

From this, we can conclude that Fn = Fn-1 + Fn-2, and with initial conditions of F0 = 1 and F1 = 1, this gives us the Fibonacci sequence!


You must log in to comment.

in reply to @lunasorcery's post: