Staircase tiling

This is a picture of an n = 7 n=7 staircase polyomino tiled by 10 straight polyominos from a set of size 1 through 4.

What is the minimum number of straight polyominoes from a set of size 1 through 12 required to tile an n = 100 n=100 staircase polyomino?


The answer is 468.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Jeremy Galvagni
May 6, 2018

Here's a re-ordering of the pieces from the example. It really doesn't matter how they are oriented as long as one uses the maximum number of the largest size pieces. I will discuss filling the rows one by one starting with the longest. The rest will be triangles filled in by smaller pieces.

100 / 12 = 8 r 4 100/12=8r4 which means if we fill the longest 5 rows with 8 copies each it will leave a copy of the n=4 staircase that will be filled by 4 small straights. Pieces used: 8 5 + 4 = 44 8*5+4=44 and rows 100 to 96 filled.

The next 12 rows can be filled by 7 7 copies leaving a n=11 staircase that will be filled by 11 11 straights. Pieces used: 12 7 + 11 = 95 12*7+11=95 Rows to 84 filled.

The next 12 rows can be filled by 6 6 copies leaving a n=11 staircase that will be filled by 11 11 straights. Pieces used 12 6 + 11 = 83 12*6+11=83 Rows to 72 filled. Continuing

12 5 + 11 = 71 12*5+11=71 will fill to row 60

12 4 + 11 = 59 12*4+11=59 will fill to row 48

12 3 + 11 = 47 12*3+11=47 will fill to row 36

12 2 + 11 = 35 12*2+11=35 will fill to row 24

12 1 + 11 = 23 12*1+11=23 will fill to row 12

12 0 + 11 = 11 12*0+11=11 will fill the final 11 rows.

Total = 44 + 12 ( 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 ) + 11 8 = 468 44+12*(7+6+5+4+3+2+1+0)+11*8=\boxed{468}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...