Wikipedia:Reference desk/Archives/Mathematics/2018 June 23
| Mathematics desk | ||
|---|---|---|
| < June 22 | << May | June | Jul >> | June 24 > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
June 23
editBathroom tiling question...
editFrom sitting on the john and studying the floor...
An 8x8 grid is to be tiled with 1x1, 1x2 and 2x2 squares. How many ways can
- The grid be tiled with no restrictions
- The grid be tiled with no line dividing line passing completely through the square (For each row n & n+1, there is a tile that is across both rows. Similarly for column n& n+1)
- The grid be tiled so that no 2 2x2 squares share a side or halfside.
- Both of the above two limitations...
Naraht (talk) 13:18, 23 June 2018 (UTC)
- Just considering the first problem, if it just pure 1x2 dominoes, that is called the dimer problem in physics or domino tiling in mathematics and is exactly solved, that is, there is an analytic formula. But as far as I know, the monomer-dimer problem, which includes 1x1 and 1x2 tiles, is unsolved analytically. To compute this for 8x8 and all three tile types, one would probably need to do some computer work. --Mark viking (talk) 18:40, 23 June 2018 (UTC)
- AFAIK, the only non-trivial case where a general formula for tilings of an mxn rectangle is known is with dominoes only. (There is a formula for diamonds tiling hexagons though.) What generally happens is that you can find a formula for kxn rectangles for small fixed k, but the formula gets exponentially more complicated as k increases. There is quite a bit of literature on tiling with polyominoes, but I think it's mostly concerns whether tilings exist rather than actually counting them. --RDBury (talk) 11:51, 24 June 2018 (UTC)
- OK, if restricted to 1x2 dominoes for the dimer problem, any idea how to handle the
- The grid be tiled with no line dividing line passing completely through the square (For each row n & n+1, there is a tile that is across both rows. Similarly for column n& n+1)
- limitation?Naraht (talk) 15:22, 25 June 2018 (UTC)
- If a tiling has a cut, then it is really two subtilings of kx8 (or 8xk) and (8-k)x8 (or 8x(8-k)), each of which have no restricions. Then for a given cut, the number of such tilings is the product of the numbers of subtilings. Then iterate over all 14 possible cuts, sum them all, and subtract from the 8x8 result. --Mark viking (talk) 17:52, 25 June 2018 (UTC)
- Unfortunately, that doesn't handle the case where there are two different cuts in the same tiling. The additional cuts being in the same dimension might be added back (and then three cuts added back in etc.), but it would get even more complex if the cuts are not in the same direction.Naraht (talk) 18:50, 25 June 2018 (UTC)
- I don't follow. If all tilings with one or more cuts are disallowed, then it is sufficient to consider all tilings with at least one cut. The subtilings will include all those that happen to produce extra cuts. --Mark viking (talk) 19:11, 25 June 2018 (UTC)
- Mark viking, to do this correctly would require the use of inclusion-exclusion. --JBL(talk) 19:20, 25 June 2018 (UTC)
- After thinking about it, yes I see the double counting now. Thanks to both of you for the correction. --Mark viking (talk) 20:29, 25 June 2018 (UTC)
- Mark viking, to do this correctly would require the use of inclusion-exclusion. --JBL(talk) 19:20, 25 June 2018 (UTC)
- I don't follow. If all tilings with one or more cuts are disallowed, then it is sufficient to consider all tilings with at least one cut. The subtilings will include all those that happen to produce extra cuts. --Mark viking (talk) 19:11, 25 June 2018 (UTC)
- Unfortunately, that doesn't handle the case where there are two different cuts in the same tiling. The additional cuts being in the same dimension might be added back (and then three cuts added back in etc.), but it would get even more complex if the cuts are not in the same direction.Naraht (talk) 18:50, 25 June 2018 (UTC)
- Well, according to Cut-the-knot, the answer is positive: [1] [2]. (Though it wouldn't be if you had asked about a 6-by-6 board.) --JBL (talk) 19:16, 25 June 2018 (UTC)
- The OEIS is wonderful, as always: A028420 is domino-and-monomino tilings of a square, A124997 is fault-free domino tilings of a square. --JBL (talk) 20:40, 26 June 2018 (UTC)
- I subscribe to a faculty mathematics journal. I am reminded of a puzzle I saw there which remains the only one which nobody has submitted an answer to. Can the Wikipedia experts do better?
- The OEIS is wonderful, as always: A028420 is domino-and-monomino tilings of a square, A124997 is fault-free domino tilings of a square. --JBL (talk) 20:40, 26 June 2018 (UTC)
- If a tiling has a cut, then it is really two subtilings of kx8 (or 8xk) and (8-k)x8 (or 8x(8-k)), each of which have no restricions. Then for a given cut, the number of such tilings is the product of the numbers of subtilings. Then iterate over all 14 possible cuts, sum them all, and subtract from the 8x8 result. --Mark viking (talk) 17:52, 25 June 2018 (UTC)
- OK, if restricted to 1x2 dominoes for the dimer problem, any idea how to handle the
- AFAIK, the only non-trivial case where a general formula for tilings of an mxn rectangle is known is with dominoes only. (There is a formula for diamonds tiling hexagons though.) What generally happens is that you can find a formula for kxn rectangles for small fixed k, but the formula gets exponentially more complicated as k increases. There is quite a bit of literature on tiling with polyominoes, but I think it's mostly concerns whether tilings exist rather than actually counting them. --RDBury (talk) 11:51, 24 June 2018 (UTC)
- A year-to-view calendar has the months in a conventional arrangement of three months in each of four rows. The names of the months are printed as normal, but the days (Sunday to Saturday) and the dates (1 to 28, 29, 30, or 31 as the case may be) are printed on removable tiles. You can choose from 1x1 squares (for a single month), 1x2 rectangles (for two adjoining months in a single row) or 1x3 rectangles (covering the whole row) and both sides of the tiles are available for printing. What is the minimum number of tiles you need to print up to ensure your calendar can be used in any year? 86.155.146.159 (talk) 16:47, 30 June 2018 (UTC)