From: Yura Aksyonov [SMTP:aksyonov@starlab.ifmo.ru] Date: 1999-02-22 Subject: Y-pentomino Hello Torsten! > >But I still have some questions about one-sided Y-pentomino and in your > >results this problem is still opened. It is easy to prove that boxes can > >be only (5*M)x(5*N) and since there is known 5x10 prime, other primes > >can be just (10*M+5)x(10*N+5). > How did you prove this? Fairly easy to prove: Consider pentominos that adjacent to a border with I4 part. They can't be placed uninterruptedly, also they can't be separated by more than one cell. # # #1 #1 #1 #11 #11 #11 #1 #1x #1 #1 #1x #1 #x #2x or #x or #x #21 #x #x #2 #2 #2 #2 #22 #22 # #2 #2 #2 #2 In place xxx no Y-pentominos can be placed (actually in second variant they can but without continuation). So boundary Y-pentominos can be separated ONLY by one cell. Consider also that corner Y-pentominos can be placed only like this: ###### but not like this: ###### #a #aaaa #aa #xxa #a # #a # Consequently both sides of box should divide by 5, only (5*M)x(5*N) rectangle may be filled with Y-pentominos. Furthermore there's set of fixed Y-pentominos placed at border. Here's example with 10x5 box: abbbb aa.bc a...c a..cc ....c d.... dd..e d...e df.ee ffffe Fixed pentominos somehow accelerate computing. The fact number two is even simplier. There is known prime 5x10, all not odd (5*M)x(5*N) boxes can be composed of 5x10 prime, so other primes may be only odd i.e. (10*M+5)x(10*N+5). [...] Finally few words about myself. I'm Yura Aksyonov, male, age 21, 5th year student of St. Petersburg (Russia) Institute of Fine Mechanics and Optics (IFMO). My speciality is programming and my special interest is amusing mathematics. Regards Yura ----------------------------------------------------------------------- From: Yura Aksyonov [SMTP:aksyonov@starlab.ifmo.ru] Subject: Handed Y-pentomino problem is solved Date: 1999-03-06 Hello Torsten. Finally I proved impossibility of tiling (5+10*N)x(5+10*N) box with handed Y-pentominos. The proof is again very simple. And I like it, it's beautiful. ============================================================ First, consider dissection of rectangle into crosses (maybe they're called X-pentominos but I don't know). As example I show the dissection of 15x15 rectangle. +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |00|00|00 00 00| |00|00 00 00| |00|00 00 00| + +--+--+ +--+ +--+--+ +--+ +--+--+ +--+ |00 00| |00| | |00| | |00|00| + +--+ +--+--+ +--+ +--+--+ +--+ +--+--+ |00| aa | | | | | | |00| +--+--+ +--+ +--+--+ +--+ +--+--+ +--+ + |00| | | | | | | | |00 00| +--+ +--+--+ +--+ +--+--+ +--+ +--+--+ + | | | | | | | | |00| +--+ +--+ +--+--+ +--+ +--+--+ +--+ +--+ |00| | | | | | | | | + +--+--+ +--+ +--+--+ +--+ +--+--+ +--+ |00 00| | | | | | | | |00| + +--+ +--+--+ +--+ +--+--+ +--+ +--+--+ |00| | | | | | | |00| +--+--+ +--+ +--+--+ +--+ +--+--+ +--+ + |00| | | | | | | | |00 00| +--+ +--+--+ +--+ +--+--+ +--+ +--+--+--+ | | | | | | | | |00| +--+ +--+ +--+--+ +--+ +--+--+ +--+ +--+ |00| | | | | | | | | + +--+--+ +--+ +--+--+ +--+ +--+--+ +--+ |00 00| | | | | | | | |00| + +--+ +--+--+ +--+ +--+--+ +--+ +--+--+ |00| | | | | | | |00| +--+--+ +--+ +--+--+ +--+ +--+--+ +--+--+ |00|00| | |00| | |00| |00|00| +--+ +--+--+ +--+ +--+--+ +--+ +--+--+--+ |00 00 00|00| |00 00 00|00| |00 00 00|00|00| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ Fig. 1. All partial crosses are covered by fixed pentominos (I mentioned them in previous proof) and other area consist of complete crosses. There is formula for getting the number of crosses in 5Mx5N rectangle. 5x5 - 1 5x10 - 4 5x15 - 7 5x5N - 3N - 2 5Mx5N - M*(3N - 2) + (M - 1)*2N = 5MN - 2M - 2N Now I claim that if there's possible tiling, all pentominos except border ones can be paired so each pair covers pair of adjacent crosses. And since for odd rectangle there is odd number of crosses, no tiling is available for it. To prove pairness of pentominos consider empty cross, upper and left crosses of which are covered. Consider the most left cross with given characteristics (if there are some of them, consider highest). On the fig. 1 corresponding cross is marked with aa. Now, let's work with the chosen cross. First fact is that cross to the southwest is filled, otherwise chosen cross is not most left with given characteristics. I showed it on fig. 2. |00| |00 00 00| | | +--+ +--+--+ +--+ +--+ |00 00 00|xx|00| | +--+ +--+ +--+--+ +--+ |00|00| | | | + +--+--+ +--+ +--+--+ 00 00| | | | | + +--+ +--+--+ +--+ + |00| | | | +--+--+ +--+ +--+--+ + | | | | | | | +--+ +--+--+ +--+ +--+ | | | | | Fig. 2. Now consider pentomino that covers xx cell. There are at most two variants of placing it (depending on whether lower and right crosses are free or not). First variant: |00| |00 00 00| | | +--+ +--+--+ +--+ +--+ |00 00 00|11|00| | +--+ +--+ +--+--+ +--+ |00|00|22 11 11| | | + +--+--+ +--+ +--+--+ 00 00|22|11| | | + +--+ +--+--+ +--+ + |00|22 22 11| | | +--+--+ +--+ +--+--+ + | | |22| | | | +--+ +--+--+ +--+ +--+ | | | | | Fig. 3. There is only one variant to place second pentomino. And 1 and 2 covers exactly two crosses. Second variant: |00| |00 00 00| | | +--+ +--+--+ +--+ +--+ |00 00 00|11|00| | +--+ +--+ +--+--+ +--+ |00|00|11 11 11|11| | + +--+--+ +--+ +--+--+ 00 00| |xx| | | + +--+ +--+--+ +--+ + |00| | | | +--+--+ +--+ +--+--+ + | | | | | | | +--+ +--+--+ +--+ +--+ | | | | | Fig. 4. Here are five variants to place second pentomino that covers xx cell: 1) 1 2) 1 3) 1 4) 1 5) 1 1111 1111 1111 1111 1111 2222 2222 2 2 2 2 2 2222 22 2 2 22 2 2 3, 4 and 5 variants are obviously impossible. And 1 is impossible too: 000100 001111 002222 0xxx2 It is impossible to cover xxx cells. So, again only one variant is possible (second). And again two pentominos covers exactly two crosses. That's it. I proved that if it's possible to fill rectangle with pentominos, interior ones could be combined into pairs. Consequently no odd tiling is possible. ============================================================ Now consider 10x10 rectangle. +--+--+--+--+--+--+--+--+--+--+ |00|00|00 00 00| |00|00 00 00| + +--+--+ +--+ +--+--+ +--+ |00 00| |00| | |00|00| + +--+ +--+--+ +--+ +--+--+ |00| | | | |00| +--+--+ +--+ +--+--+ +--+ + |00| | | | | |00 00| +--+ +--+--+ +--+ +--+--+ + | | | | | |00| +--+ +--+ +--+--+ +--+ +--+ |00| | | | | | + +--+--+ +--+ +--+--+ +--+ |00 00| | | | | |00| + +--+ +--+--+ +--+ +--+--+ |00| | | | |00| +--+--+ +--+ +--+--+ +--+--+ |00|00| | |00| |00|00| +--+ +--+--+ +--+ +--+--+--+ |00 00 00|00| |00 00 00|00|00| +--+--+--+--+--+--+--+--+--+--+ Fig. 5. Tiling of crosses with Y-pentominos is equivalent of tiling following area with "dominos": oo oooo oooo oo There are 8 variants. And for any other area tiling can be reduced to tiling some other area with "dominos". For example, tiling of NxN quadrant is equivalent to tiling of following area: oo ooooo ooooooo oooooooooo oooooooooooo . . . . . No wonder that you couldn't classified NxN tilings, there are really lots of variants. ============================================================ And finally, I don't understand your statement about n*N strips: "if it tiles a n*N (strip) -> 5|n" ??? For one side open strips n can be 5, 10, 15 ... But for two side open strips n can be 2, 4, 5, 6, 7, ... (all naturals except 1 and 3) ============================================================ Now I think all problems of handed Y-pentomino are solved. Regards, Yura