All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Staircase tilings (Posted on 2014-02-13)
Define the nth 'staircase' as a polyomino with the nth triangular number of squares arranged as a sort of right triangle with a staircase along its hypotenuse. Below is n=3

X
XX
XXX

A straight s polyomino is simply a straight line of s squares.

Find a formula for the minimum number of straight polyominoes from a collection of size 1, 2, ..., s needed to tile the nth staircase.

For example if s=2 and n=3 it takes 4 pieces.

1
22
334

 No Solution Yet Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Inch by inch, row by row (spoiler) Comment 1 of 1
After playing with this a little, I see no advantage to having some polyminos be vertical and others horizontal.  Therefore, each row can be tiled independently.  The nth row uses as many s tiles as possible, and then 1 more tile if n is not a multiple of s.  The nth row therefore uses a number of tiles equal to ceil(n/s), where ceil(x) is the smallest integer greater than or equal to x.  The total number is sum from 1 to n of Ceil(n/s).

Is there a closed form expression?

When s = 1, the incremental tiles required for each row are 1,2,3,4,5,6 ...

When s = 2, the incremental tiles required for each row are 1,1,2,2,3,3,4,4,5...

When s = 3, the incremental tiles required for each row are 1,1,1,2,2,2,3,3,3,4,4,4,5,5..

Consider n = 14, s = 3
Total minimum tiles = 1+1+1+2+2+2+3+3+3+4+4+4+5+5 =
3*(1+2+3+4) + 2*5

let f = [n/s] = largest integer less than or equal to n/s = 4
Then, generalizing from our sample formula,
3 = s
(1+2+3+4) = 1+ 2 + ... + f = f(f+1)/2
2 = (n-sf)
5 = (f+1)

Then the desired formula = sf(f+1)/2 + (n-sf)*(f+1)
= (f+1)*(sf/2 +n - sf) = (f+1)*(n - sf/2)

For instance, let n = 100 and s = 11.
Then f = [100/11] = 9
Minimum number of tiles = (9+1)*(100-99/2) = 10*(50.5) = 505.

Let's get rid of f in the final answer.
We arrive at ([n/s]+1)*(n-s[n/s]/2)

Edited on February 15, 2014, 2:15 pm
 Posted by Steve Herman on 2014-02-14 19:05:23

 Search: Search body:
Forums (0)