Tiling Rectangular Boxes
For each positive integer n, consider a 2 by n rectangle. It can be tiled with n blocks, where each block is 1 by 2. How many different ways can it be tiled? What if instead of a 2 by n rectangle we were to consider a 3 by n rectangle (where now of course n would have to be an even integer). How many ways could this be tiled with 1 by 2 blocks?
Note the blocks look like [][], and can be oriented either horizontally or vertically.
Communicated by A. Kanevsky.
Dez: correct (sjm1 AT williams.edu)
no, it’s more than that….
2^(n/2)
Jim: no worries — I could tell what you were doing and it seems right modulo minor details on 11 versus 10
Jim: correct! Not posting as it’s the soln
The following post is from Jim (he had the correct answer, which I’ve deleted):
I have a fun riddle for you that I was asked in a job interview onece. “There is a frog at the bottom of a flight of 10 steps. (he is on the ground, step 0, not step 1). This frog can traverse the stairs in steps of 1 or 2 or any combination thereof. He may only travel up, never down. In how many different ways can the frog traverse the stairs assuming that he must land exactly on the 10th step at the end of his journey? (ie, he cannot overshoot 10 and try for 11, and he must climb all 10 stairs)” The answer is….
I have a fun binary riddle for you too if you like:
“There is a building with 100 stories. You have one plate right now and you want to determine the marginal floor from which if you dropped the plate out the window it would break. Obviously you cant start at the top, buecause if it breaks at the 100th floor then you don’t know the marginal case (ie. it may have cracked at the 43rd floor but not the 42nd floor and the 43rd floor is then the marginal case). So with one plate you have to start at 1 and move up until it breaks, thus the worst case is 100 trials.
“Now assume that you have 2 plates, what is the optimal method such that you minimize your worst case # of trials, while ensuring that you will eventually find the answer?
“Secondly, assume you have an unlimited number of plates, What is the minimum worst case # of trials?”
The blocks are identical and cannot be distinguished. you must cover all spaces in the 2xn rectangle, so stacking them up won’t work
are the blocks identical? That is if I use say the most trivial solution which is to stand all the blocks up vertically and line all n of them up, is that 1 possible way or is that n! ways?