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**