Pentominoes and other Polyominoes - Numberphile

NUMBERPHILE

Video by Brady Haran, James Hennessy and Pete McPartlan

[Doktor_Vem]

Never before today did I ever realise or even consider the fact that "domino" is the same type of word as "tetromino" or "pentomino". It makes perfect sense in hindsight, but before you think about it it's like invisible

[theadamabrams]

Just in case anyone was confused at 6:21, the limit "C" is not the "c" from cλⁿ/n. In fact, it's exactly λ. So we do know for sure that there is a number λ such that lim_(n→0) Aₙ¹ᐟⁿ = λ, but from that fact alone Aₙ might asymptotically be cλⁿ/n or might be λⁿ/n² or λⁿ/log(n) or any number of other formulas that would still have the same limit for Aₙ¹ᐟⁿ, and we don't know which more detailed formula for Aₙ is correct.

[greensombrero]

I could solve it - but it's the holiday season and I had some Christmas wine, and I never drink and derive.

[nightshadefns]

What a lucky day to remember that Numberphile exists to be greeted with a fresh new video!

[petersage]

"The answer is we don't know." What a wonderful gift for a curious child!

[toolebukk]

This video is a gift! One year or so ago I dabbled with thisnexact thing, and never got anywhere and put it away and forgot about it! Thank you Soph!

[DarkAlgae]

because i'm a biologist, i associate the reflections with chirality and consider them different... but for some reason I consider the rotations all the same (possibly because Tetris allows rotation of the tetrominos). from a maths standpoint, am i right in thinking that this would be an arbitrary bias? or is there a mathematical hierarchy between reflection and rotation?

[wayfinder]

what you called the "f" is called the r-pentomino in the game of life, where it is the smallest methusalem (ie a pattern with an uncommonly large lifespan)

[slowbro]

There is a boardgame called BLOCKUS that uses these, and its very fun

[Gardinnas]

I did my master's thesis research a few years ago on tree polyominoes and a few techniques I did some progress regarding some of the questions asked in the video. They would have probably been answered if I familiarized myself with the analytical tools and went all the way. It's a nice throwback!

[bobbielala]

@numberphile
Thanks for the video, as always inspirinbg.

No formula, however after doodling a number of pages it occurred to me that one can define smallest bounding boxes for every polyomino.
This might help to break up the problem in smaller problems (computationally at least)
For N = 4, the possible bounding boxes are 4x1, 3x2 plus 2x2
For N = 5, the possible bounding boxes are 5x1, 4x2, 3x3 plus 3x2
For N = 6 the possible bounding boxes are 6x1, 5x2, 4x3, plus 3x3, 4x2 and 3x2
For N = 7 the possible bounding boxes are 7x1, 6x2, 5x3, 4x4, plus 5x2, 4x2, 4x3 and 3x3

It seems to me that finding these bounding boxes for a given N is relative easy.
Set 1 = { Nx1, N-1x2, N-2x3 .. } and it stops when N-a > b (square)
Set 2 = the bounding boxes smaller than those in Set 1 that can fit a N-polyomino (e.g. for N = 7, 2x3 is too small but 3x3 will work.

Then one can use these bounding boxes to search for polyominoes that fit per box.
The size of the boxes can help to constrain the search.

There are still mirrors and rotational shapes that are similar, so that postprocessing needs to be done.
Note that these "mirrors" must have the same bounding box so finding them could be faster,

so far my 2 cents,
Rob

[hammerth]

This kind of problem reminds me of the chemistry problem of finding all the valid isomers of an organic compound.

That quickly becomes a pointless exercise though as the number of options grows very quickly.

[stechuskaktus]

Thank you, now I feel a lot better about not getting anywhere when I tried my hand at a Ponder This puzzle involving polyminos.

[MichaelPiz]

I immediately started thinking of the Soma cube. In a class years ago, I had to write a program to solve for the number of unique, non-rotated solutions to it. Fun!

[aukeholic]

I would argue, that in 2-D, reflections are different because 'hands-on' you can only go from one to the other by going through the 3rd dimension

[summerlovinxx]

this honestly reminds me of the art gallery problem. it's hard to predict how a previous change might affect a future state, given the limitations on where each section can exist without repetition. I limited myself to using square cells, and the pattern Sophie showed popped up! repetitions aren't great, but reflections and rotations are the worst offenders lol. I'm personally partial to free form; the change in frame of reference is on the viewer, not the pieces themselves. we abritrarily determine what we think they look like, so it keeps the full list concise and readable.

[JeffDayPoppy]

Thank you for finally doing this video!!! I've been waiting 25 years to learn more about this.

[rosiefay]

Good question. As well as free (all rotations and reflections count as the same) and fixed (all rotations and reflections count as different), there is one-sided (think of the shape as having a front and a back; rotations count as the same but you are not allowed to reflect because that would put it back to front). You could also regard the unit as being not a square but an oblong (180° turns and horizontal and vertical reflections are allowed, but 90° turns and diagonal reflections aren't) or a rhombus (180° turns and diagonal reflections are allowed, but 90° turns and horizontal and vertical reflections aren't).

[mfx]

Teacher went away and found a paper, much kudos to that teacher I'm sure many (not all) would either wing it or just say I don't know.

[wyboo]

that constant reminds me of Khinchin's constant. if x is an arbitrary real number with simple continued fraction [a0; a1, a2, ...], then lim_{n -> infty} (a0•a1•...•an)^(1/n) is a constant for almost all x

if An=a0•a1•...•an, then that's lim_{n -> infty} An^(1/n) is a constant

almost certainly unrelated, but the video reminded me of it