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
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
Inch by inch, row by row (spoiler)
