วีดีโอ

Is there a difference between minimal inscribed polyominos and convex polyominos? Edit: Never mind, I see in the definition where you say it must have minimal area. I'm trying to find an algorithm that can generate convex polyominoes for a puzzle game I'm working on. The closest thing I found was a paper by Paolo Massazza titled On the generation of convex polyominoes but the math is too far above my level. He has some psudocode, but I can't get it to work. Any chance you could make a video on this topic?

You can solve the n by k cases for small k using matrix exponentiation. To get an exact formula you can use the eigenvectors of the matrix. I did it for the 2 by n case and got the same formula that you got.

here's a definition for an open which doesn't over count, the definition will be found when clicking "read more" the new definition for an open can be anything if a loop isn't possible, else pick anything that isn't the mosaic which makes a loop

I am from Poland - can you please tell me what the "backburner" word should mean? Is it connected with "backlog" like in the comment about Gian Carlo Rota and Richard Feynman? I know what is afterburner :)

8:45 - its not true i dont believe that a brute force algo was not able to compute 5,1 5,2 and 5,3 - 5x3 is less options than 4x4 which it had computed... i would use monte carlo method and have complexity of O(10000) giving me 3 decimal places after decimal point as the relative values are reaching 1.

I have an idea for an algorithm that should solve this in about O(n*m*3^min(n,m)) Start at full width, adding one piece at a time, scanning along rows. Each state comes with a record of connections which looks like "(..()().(())..)" with each open bracket being connected to it's closing bracket and the dots not connected to anything. All you need to do is work out how many ways to add a tile without making a loop. Repeat. This lets you calculate the number of solutions with no loops.

Any chance you'll do a video on your approach with generating functions? Could you also get out asymptotics from your expression?

Always looking forward to your videos :)

Thank you! I have tried to read lots of papers on enumerating polyominoes and just not gotten through all the set theoretic notation to discover the core ideas. This is marvelous.

Wow, this was amazing! I'm wondering what sorts of apps or coding environments you're using to do all of this? I've been working on a Sudoku App. However, because I'm interested in all of the many different rulesets of different flavors of Sudoku I've ended up needing to do some polyomino adjacent math. This video was very helpful. Thank you!

When we were kids, my brother was an extremely curious kid - mostly interested in numbers and logic. He invented riddles to solve for himself and tried to figure them out - A pretty smart boy. Since we owned a Game Boy back in the days, he wondered exactly about the question how many shapes there are of number n. He never knew the term polyomino and called his riddle the "Tetris Problem". Alongside his tries to find a solution for prime numbers, he couldn't figure this one out. Weeks and weeks on end he tried. Years later I also gave it a try and failed as well. It's funny, because this problem got me into Tetris later in life and from there I learned about polyominos. I also bought the Golomb book. It's so fascinating to see how much my brother as a 11-13 year old figured out by himself. I enjoyed this video very much!

ERRATA: At 13:28 the second shaded triangle on the n=4 case on the top should be moved to the second unshaded triangle from the top.

Shouldn't the hexagons be in a shape of a hexagon, instead of a triangle?

At 13:28 there are no triangles touching the left side of the n=4 example.

Fascinating! Great video, thanks!

Is it also always 4 for normal polyforms in n×m Aztec diamonds where n≠m?

The links in the description are broken.

I finally got around to watching this video, and I can say that I’m glad I did!

If you start sketching ideas for a problem, go to save your file, and realize you already have a file of the same name from when you did the same thing two years ago ... you may have a backburner problem.

genius!

I'm curious how the numbers chance if you add in two additional tile types: one where you have both corner cuts and ones where you have the two cross-cuts where one passes over the other (a bridge). For the n,2 case it wouldn't allow for any new shapes but it would change the denominator [now there are 8 tiles] and numerator [anything that uses the cross-cut or the corner cut can also use the dual] but doesn't allow for any new shapes. Definitely for 4 and up it adds new shape possibilities.

Variant: same question but the tiles are T shaped.

Very nice problem! Two potential generalizations that could be interesting: 1) What about different sets of tiles? Either by defining different entry-exit points for the square and then taking all ways of connecting them (e.g., dividing the sides into thirds rather than halves), or just by restricting which shapes of tiles to use (e.g., only the diagonals). 2) Instead of "probability of a closed shape", what about "average area enclosed"? This would need some reasonable way to handle one enclosed shape contained inside another.

this is a good video

I was doing this without realising the benefits, now when i think, they really helped me

I think my first back burner problem was back in high school. I saw some post about a bakery that sold square donuts, and wondered how much more volume you would get with them in the same box out of it. I was just taking calculus around then, so I didn’t know the volume of a torus but figured it out, and was surprised that it was just a plain ratio between them, rather than being some messy function based on the 2 radii of the torus. I wondered if this was true for any polygon, and then had to figure out what exactly a polygonal torus was. I was stuck for a bit until one of my teacher’s mentioned the fact that a torus has the same volume as the cylinder you would get by cutting it open and unbending it. And then I realized that the shapes I was looking at could be unfolded into prisms in the same way, and the volume was just the area of the tube section times the perimeter of the larger polygon. The same way that a torus is the area of a smaller circle times the circumference a larger one. And that ratio was just (tan(π/n)/π)^2 It was a very simple problem, but it was the first time I actually wanted to solve something for no reason other than curiosity and I used whatever knowledge I had at the time to do it. And it lead me to thinking about a lot more than the initial random post that started this, and made me think more like a mathematician. Even know, at least 6-7 years later, online I still use a square Toruhedron (they didn’t have a name so I made one) to represent myself a lot because it means something to me

Bro that intro was so good. I'm not in high school yet, but that made me remind to find something that interest me in math and that would also motivate me to study. One example is those mob farm Minecraft videos. I could not understand a single thing about the spawn rate analysis.

Maybe linking your problem to graph theory could open the way for a general solution in the n*m case : if you consider the vertices to be the sides of the squares and the edges to be the mosaic tiles, it may be possible to consider the probability of a certain non oriented graph having a cycle ( a closed shape in the mosaic case ). Thinking about it in this way may be useful because there are many useful results and definitions in graph theory that could make the problem easier to solve

You would think that on the one hand, it's probability 1 that a tile is enclosed in a shape. Because you can think of it that eventually there will be some huge shape that encloses all of it in between. But then again, the chance such a huge enclosing shape exists will tend to probability 0. Because it takes only 1 tile to mess up that enclosing shape. Definitely an interesting one.

7:18 I got a bigger answer: 32070. I could be wrong but I think you may have forgotten the diagonal rectangle shape that adds 6^2 * 2

Amazing video! I took a combinatorics class in my undergrad and loved it. I'm a bit rusty now though lol. We used the Brualdi textbook and it was not my favorite.

I’ve never realised that the back burner problems I’ve had were probably helping me. In relation to the question, I can see some way to expand into the m,n cases but it would require classifying a whole lot of other properties of the rectangles. No where near as practically as you have done it here.

I hear that probability is the Devil's math.

This is my favorite of the #some3 submissions of 2023, as it is both useful and motivating to me personally.

any cell on the infinite grid will always be surrounded by an infinite amount of shapes and it's not that hard to prove

OK. I’d say (with no proof at all, I just feel like it) that every single cell on the infinite grid is closed in an infinite amount of shapes

A great explanation and I loved how you took us on the journey of your thinking and learning process 😊

My own thoughts on the problem: First, the parity requirement for interior-ness is not well-defined on an infinite grid, since there could be infinitely many closed loops around a given square. Regarding the original problem, perhaps there is some kind of inductive construction based on mosaics with a path from a certain point on the boundary to another. These seem easier to characterize, and might yield interesting insights.

This is a really interesting concept for many math students. It absolutely would not have worked for me, cause ADHD doesn't understand the expression "backburner", but you did leave with itching with a different mosaic problem: given an MxN grid of randomly distribute tiles, what is the average length of the longest continuous line in the grid. I have some python to code now, lmao.

You should submit the (n,2) and (n,3) cases to the Online Encyclopedia of Integer Sequences. They're two interesting sequences of integers, which is exactly what the OEIS tries to collect.

My back burner question for part of my undergrad was about finding numbers that are palindromes in multiple bases, in particular base 2 and 10, like 585 (1001001001). I wanted to know if there are infinite of them, and if I could prove it. I never made much rigorous mathematical progress though but did write code to search for them

Great video! Problems like the mosaic problem are actually very useful in physics. Counting all the mosaics with loops allows you to find the temperature at which a liquid evaporates into a gas in some simple models (we would call the generating function a cluster expansion, and the liquid gas model I was thinking of is called the Ising model). Just goes to show that sometimes your back burner problem might not be as esoteric as it seems at first!

I've still never personally solved my fun math problem. I want a non repeating arangement of coloured tiles where no to tiles the same colour ever touch. I have realised that this is only possible if the shape of the tiles is a non repeating pattern but which shape is the best shape for this puzzle?

Once i saw you write down a recurrence relation my first thought was eould generating functions give me a bice closef form here

I occasionally think up random problems like this, and I generally solve them with a bit of programming (often a Monte Carlo simulation). While I enjoy probabilities, I find them difficult to process when I only ever think about them every few months. It just evanesces from my mind over time, and my understanding lessens. It's rather annoying.

Amazing video🔥🔥🔥

Nice video and problem! But I think you went wrong calculating t_5,2 because overcounting. Think that in the t_4,2 * 6^2 you are arleady counting some mosaics that end in a little diamnod shape and then counting that again in the t_3,2 * 6^(2*3) case. Nevertheless, using the Inclusion-Exclusion Principle there has to be a way of getting t_5,2 correctly. (Btw I'm learning english so if I just make a mistake I'll apriciate if you can teach me what did I wrote wrong and I hope you get my point)

Nitpicks (on the Minecraft side; the math seems fine): - The sugarcane farm at 2:47 won’t work IIRC; I don’t think the lower sugarcane changes block state when it grows - Most crops don’t grow every random tick, not just amethyst. Vines, kelp, sugar cane, and I think bamboo also have a 1-in-n chance to grow per random tick for various n > 1, traditional farmland crops have complicated chances based on soil hydration and neighbors, saplings have *particularly* complicated chances based on possible tree shapes, etc. - Even if you design your observer-based farm correctly, this can still be useful for sugar, bamboo, etc. because for large patches you want to dispatch a flying machine instead of use observers.

Haven't watched the whole thing yet but your point of recontextualization is really important! One of the ways is how you suggest: by having a problem to which that context can be repeatedly applied. Even if you don't have a pet problem, just thinking about new information and connecting it to what you know can help recontextualize things!

As a computer programmer I very often run into people online asking questions like "I'm learning <some language>, what should I write?" Or "I want to contribute to open-source, what project should I contribute to?" As a participant in various nerdy hobbies I run into people asking "okay, I'm new to this hobby and I just bought all the equipment they say I need to get started [ouch!]... now what do I do?" My answer to all of those people is very much related to this video: explore what interests *you*. Have something *you* want to accomplish. Wanting to learn a language, or partake in a hobby, or absorb a mathematical concept, aren't really the kind of goals that you can get invested in for their own sake. They're means to an end. You need to go into the game with an end in mind, something that drives you personally, and then you'll have a reason to knock down everything that stands in your way - and to discover something new that you didn't know you cared about in the beginning. Ordinary people can probably sustain one or two such interests. Really *interesting* people cultivate several and find ways to synthesize them.