Polyominoes on Chessboards - Numberphile

[00:01] videos I did um a video about how many polyominos there are. I did one about animal tic-tac-toe and this is number three, which we're specifically going to look at the smaller polyominos. So, as a quick recap, a polyomino is made of n

[00:17] squares. So, a oneino is one square. A two or a domino is two squares joined together. And then for three oros, we've got the line and then the little L and so on. It's >> like Tetris pieces is a common version.

[00:33] >> Yeah, the Tetris pieces are tetrooinino and the word tetris comes from tetrooino tennis. A fun fact for the day. So we're going to look at specifically how we can arrange these polyominos. Um and I've got a question. So we let's suppose

[00:47] we've got a chessboard and I'm going to draw one out. So we've got an 8 by8 grid draw one out. So we've got an 8 by8 grid and let's suppose we remove two corners. So, we're going to get rid of that one. And we're going to get rid of that one.

[00:59] My question to you is, can you cover this with dominoes? So, you might put, say, one covering these two squares like that, and then you might choose the next >> But because those things are seven long, we're going to have to

[01:14] >> We're going to turn one. >> Well, yes. So, we've got this one here. it possible to cover the whole chessboard with dominoes? >> Well, it's an even number. Yeah, good. Good. This is a good start. Um,

[01:28] >> so it's definitely not obviously impossible, but unfortunately it >> I'm going to show you why it's not possible and prove it by coloring in a chessboard. So, let's color in a chessboard in a standard chessboard

[01:41] coloring. And now, what do you notice about these two dominoes that we have here? Well, they both cover one white and one pink square. In fact, wherever we put the domino, if we put it here, here, it

[01:54] always covers one square of each color. But if you were to look at the grid, there are more pink squares than white squares because the two we've removed are both white. So, actually, in total, we're trying to cover 62 squares. And of

[02:09] them, 32 are pink, but only 30 are white. But each domino covers one of each color. So, it can't be possible because we have a different number of you've convinced me. >> So, if instead of removing these two

[02:24] squares, we removed these two. So, the top two white squares. >> Reinstated that one. It would still be impossible cuz we'll still have a different number of pink and white squares. So, what if we removed one pink

[02:36] and one white square? Well, this in this case actually is possible. And one of the best ways of showing anything in maths is possible is by doing it. So, if maths is possible is by doing it. So, if we removed this square and this square,

[02:48] which is now one white and one pink, we could cover it with dominoes just by this. [Music] [Music] >> The two you removed here of um alternate

[03:02] >> that there was a nice sort of symmetry to it. What if you'd moved like a uh one here and one of the alternate color here cute like >> Yeah. So that is actually a really good

[03:17] >> Yeah. So that is actually a really good question. Um and the answer is that we can do it >> um in this situation. >> so there's no pink and white I could have removed at random spots on the

[03:30] board that would have pinned you in and >> No. Um, and the proof for this one is a little more involved, but I can quickly give you a taste of what it might be like. So, let's say we've removed this one and this pink one. The

[03:47] reason why this is possible is that we can draw a path through all of the squares and it's always going to be possible in this situation. And then the way you can arrange the dominoes is just by lying them along the path. So with

[04:01] dominoes, this is possible because you can always lie them along the path. You'll never need to go around a right angle because dominoes are only two forced. >> Have fun animating that Pete.

[04:15] All right. I'm not animating that. That's a Pete special. >> So we've dealt with dominoes. Now let's look at dominoes. Specifically, we're going to look at this long troomino with three squares. Right. Well, immediately

[04:28] this isn't going to be possible because this has 62 squares and 62 is not a multiple of three. So that's a fairly fairly easy thing. Can't do that. Um so instead now I'm going to again go back to my 8 by8 grid. Um but I'm only going

[04:43] to remove one square. So we've got 63 squares. Hopefully 21 of these will work. Can it be done? >> Well, you got a good poker face cuz you

[04:55] if you're smiling cuz it can be done or it can't be done. Um, my feeling is >> Oh, Brady, you're correct. It can't be done. Um, now instead of coloring in our

[05:12] chest wall with two colors, white and pink, I'm going to use three colors, >> Yep. >> Uh, and I'm going to color it this way. >> Uh, and I'm going to color it this way. So this will be green, pink, white

[05:25] >> or brown and >> or brown. Someone who spent too long doing pure maths where colors no longer actually mean colors and white is a default for absence of. And now similar to before, if we were to put our trino

[05:38] anywhere on a grid, it's always going to cover one green, one pink, one brown. there? >> Uh, same problem as last time. only work if there were 21 of each, but a quick add up. So, well, in terms of

[05:54] green, we've got two + 5 is seven plus this is going to be eight is 15 + 5 is 20 + 22. So, you've got 22 green ones. And then

[06:07] So, you've got 22 green ones. And then pink 3 + 6 is 9 + 7 is 16 + 4 is 20 + 1 21. So, we must have 20 white ones. So, this isn't going to work. we've got we've got the wrong number. So, we can't do a corner square. Now, it does raise

[06:22] the question, is there a square that we could remove that would make it possible? For example, if we remove this square instead. square instead. So, this one is going to be brown. And

[06:35] I'll write that in. And what if instead of removing our brown square, we removed a green square? Because currently we have 20 brown squares. So, this would give us 21 brown squares. and then we remove a green square, there would be 21

[06:48] >> So, that could work, right? But no, because if we could remove that square, we could remove that square, do it all, and then just rotate it, and we'd have to an easy fallacy to make in maths. Just

[07:03] different numbers of each square means that we can't do it. It doesn't mean the converse is true. It doesn't mean that the same number of each square means we can do it. Um, and we definitely can't do it here, right? Because otherwise,

[07:17] yeah, we could just superimpose and rotate and then we'd have an answer for >> So, we know we can't do it unless we remove a green square. But we also now know we can't do it if the green square will

[07:33] color. So, what we need is a green square that rotates to another green square that rotates to another green square. It will only be possible if we have a green square that every 90° rotation will land on top of another

[07:47] green square. Thankfully, we do have one of those. So, this square here, you do a of those. So, this square here, you do a 90° rotation goes onto this square >> and goes onto this square and this square. So, whichever rotation, we're

[08:01] always removing a green square. Now, once again, we want to make sure we don't fall into the same fallacy. Just because this not being true means it's means it's possible. >> But we have our method now of showing

[08:18] that something's true which is by doing it. So we can try this drawing another one. >> So we're removing this square. And what we're hoping is that we will be able to get this three. So let's try going here.

[08:31] there. This one's going to have to be across like that. Can we do it? This is across like that. Can we do it? This is the question. And yes, we can do it. So, we can confidently say that this is possible because we've done it. I

[08:45] suppose there is one other question you might have about might have about um and that's about the L-shaped one. Now, the L-shaped one isn't always going to cover one of each color. Um so, it's

[08:57] ends up being easier, but I'll leave that for something for you to try yourself. The final thing I want to move on to is tetrooinino. Now back to our four and there are five tetromeos as you might remember from a previous video. So

[09:10] I'm just quickly going to draw them. Then we've got this one and then the line. So these are all the tetromeos. And the final question is can we put one copy of each of these trimminal into a grid exactly once so that all fits. This

[09:25] grid is going to be 4x5. The side has to be at least four otherwise this isn't going to fit in. So 4x5 is the only possible option. So we've got a 4x5 grid. And once again, we can use the same trick. We're going to go back to

[09:38] our two colors. So, back to pink and brown. So, can we do it? If we look at cover two of each. So, this is two of each. This tetromeo also always going to always going to cover two of each. So, this is currently looking promising.

[09:54] These all cover two of each. And we do have the same number here. But this one's our problem. If we were to lay this T- shape on, it will either have three pink, one brown, or three brown, one pink.

[10:06] >> So, we can't do it. One copy of each of these is going to lead to a different grid, we have the same number. So, it's going to leave you with, Brady. Um, and that is taking it up a level. We've

[10:18] looked at dominoes, we've looked at, we've looked at tetromemos. The five is pen dominoes. Um, and there are 12 of them. Um, I'm sure will now get a screen

[10:30] I know Pete's already done that animation. So, there are pen dominoes and the answer to the question of can they all be fit once each exactly once in a rectangular grid is yes. But I'm not

[10:43] to try and do it. >> No, we're going to do it on screen. Definitely. Definitely. I can't resist. >> I'm not telling you how cuz I don't know the answer off the top of my head. Oh, >> another one for Pete.

[10:57] >> another one for Pete. >> Cool. Our quantitative trading firm. And being global means they offer opportunities to

[11:11] work in offices around the world. At the time of recording this, they've opened applications for internships at their Hong Kong office. Now, I love Hong Kong. It's one of my favorite cities, and you could find yourself here. All expenses

[11:26] paid, including your flights, accommodation, and a salary. Of course, you don't need finance experience, just a curious mind. A passion to learn about distributed systems, programmable hardware, statistics, the sort of stuff

[11:43] I imagine number file fans love. You should be able to speak English and be graduating from university in 2027 or later. Now, I've been to Jane Street offices. They're amazing spaces and they really look after their people.

[11:58] the Jane Street website. There's a link down below along with details of other jobs and programs and opportunities they Check it out. It could be the start of something really big.

[12:18] I mean, who who's not thought at some point, hey, I'm great at this game. And so, when you sit down and you show them what good really means and just how fast you can play this game or just how accurately you can play this game,

[12:33] accurately you can play this game, a gasp. People are a gasp.