Programming Competition problem

[R0mai]

Hi guys,

Today was the national student competition's for high school students programming category in Hungary. There was a problem which I couldn't solve. This round was a paper round, we weren't allowed to use anything.
Here is the problem :
We have a 2*N sized pavement. We can cover this with 1*1 and 1*2 sized pieces. How many ways can we do it if N=2, N=3, N=4, N=5, N=6, N=7, N=8.
Example for N=3 :

 __________
|      |   |
|______|___|
|   |      |
|___|______|

Can anybody solve it? :)

[firedraco]

Is stuff like:


11 2
3 44
and

1 22
33 4

different?

[R0mai]

Yep, for N=2 the solution is 7.

[firedraco]

Hm, then what I would do is start with 1s in all spots, and then go through and replace each one with a 2x1 block, and sort of keep doing that (I hope that's clear). Then, do it for N=2,N=3, maybe N=4, and try to find a formula for it.

Oh and also, does stuff like:


1 2 3
1 2 3 work?

Random Guess: (2^[N+1])-1

[R0mai]

Yes you can rotate the 2*1 pieces.
If I remember correctly, I got 21 for N=3, I tried drawing down every position. I don't know if it's the correct answer, they haven't published the solutions yet.

[firedraco]

Hm, just had an idea. Couldn't you get the answer for N=2, then N=3 do something like this:


N2 N
N2 3

And since there are 3 ways to do the N3, then N=3 is at least 3*(N=2 answer). There will be other answers since you can make 2*1s extend into the N2 area^[1], but you can get a lower bound.

[1] Which would be 3*(N=1) I think.

[chrisname]

Hungary

You're Hungarian? Hm, your English is good.

[R0mai]

You're Hungarian? Hm, your English is good.

Thanks :)

[Bazzy]

Do you name your variables using the Hungarian notation?
^{_{I always wanted to ask such a stupid question}}

[R0mai]

Do you name your variables using the Hungarian notation?

No, and we are not constantly hungry eiher :).

[chrisname]

we are not constantly hungry eiher :).

Lol...

[PanGalactic]

No, and we are not constantly hungry eiher :).

Well, there goes that theory.

[tition]

Well, there are two distinct cases:
Either
1. you have some place in your arrangement a 2x1 block standing up vertically (left-right side of length 2, top bottom side of length one)
or
2. you have no 2x1 block standing up.

Let us think for a while on case 1. If you have a block "standing up" at position k, it splits the picture in two parts, say something like *****|** (the vertical line represents position k, in this case this is position 6). Then the number of ways to make a partition is equal to the number of ways to solve your problem for a (2 x K-1) block times the number of ways to do it for a (2 x (N-K) ) block.

Now, suppose you have solved the problem for an 2 x M block in case you never have a vertical 2x1 block. Call that function int AnswerNoVertical2by1blocks(int length). Then the function you are looking for can be given as:

int FinalAnswer(int StartingIndexOfBlock, int EndingIndexOfBlock)
{ int result=0;
  // in the below, the index int i represents the SMALLEST index for which 
  // you have a vertical 2 by 1 block
  for(int i=StartingIndexOfBlock;i<=EndingIndexOfBlock;i++)
  { result+=AnswerNoVertical2by1blocks(i-StartingIndexOfBlock)*FinalAnswer(i+1,EndingIndexOfBlock);
  }
  return result;
}

[tition]

Now, how do we find the function int AnswerNoVertical2by1blocks(int length) ?

Since we cannot put vertical block, it is the same as splitting one horizontal stripe of height 1 squared.

In how many ways can we split a horizontal stripe of length int length? This is a trick from the math competitions arsenal: the answer is a Fibonacci number. Let us see why:

Suppose the number of ways to split a horizontal stripe 1xN is F(N). We have two options for the left-most block: it is either 2x1 or 1x1. Therefore:

F(N)=F(N-1)+F(N-2)

which is exactly how you define Fibonacci numbers. Note F(1)=1, F(2)=2.
Therefore:

int AnswerNoVertical2by1blocks(int length)
{ int n=Fibonacci(length);
  return n*n;
}

And finally,

int Fibonacci(int N)
{int fib_small=1;
  int fib_large=1;
  for (int i=1;i<N;i++)
  { int temp= fib_large;
    fib_large+=fib_small;
    fib_small=temp;
  }
  return fib_large;
}

[tition]

It might be possible to solve this problem in a "closed" form modulo some reasonable combinatorial functions, but hey, why should we when we have computers :)

Cheers!

[R0mai]

tition :

This was a paper round, we didn't have computers. We didn't had to write a program (not even in pseudo code) which solves the problem.
The problem should be possible to solve without any help (even without a pocket-calculator), on paper.

[tition]

Well, up to the 8th (shifted) Fibonacci number:

F(1)=1
F(2)=2
F(3)=3
F(4)=5
F(5)=8
F(6)=13
F(7)=21
F(8)=34

Once you know FinalAnswer(1), you easily get FinalAnswer(2), and so on. The program above is very easy to carry out by hand.

[tition]

I jost woke up and an "easier" solution came to my mind, perhaps it was even the solution you were expected to give.

Let the way to pave a 2xN block be denoted by G(N). Then

[Edit:] Just found the below is wrong.
G(N)= 2G(N-1)+3G(N-2).

There is a way to solve such "recurrence relations" directly, in "closed form", see http://en.wikipedia.org/wiki/Recurrence_relation . But, just for fun, let us do it by hand :)

To explain why G(N)= 2G(N-1)+3G(N-2), just note that either the first 2 x 1 block is like this | or like this :, which is two combinations, so G(N)=2G(N-1)+..., but you also have the option for starting with a horizontal 2x1 block, like this _ or like this -, or with a two lying horizontal blocks =, which accounts for the coefficient 3.

[Edit:] Or you can start with ._ on the bottom and - on the top. Which makes the above simple "solution" wrong. A famoust quote (heard it attributed to Einstein): One should make matters as simple as possible, but never simpler!

Therefore

G(0)=1
G(1)=2
G(2)=7
G(3)=2*7+3*2      = 14+(7-1)= 14+6= 20
G(4)=2*20+3*7     = 40+(20+1)     = 61
G(5)=2*61+3*20    = 122+(61-1)    = 182
G(6)=2*182+3*61   = 364+(182+1)   = 547
G(7)=1094+182*3   = 1094+ (547-1) = 1640
G(8)=1650*2+547*3 = 3300+ (1640+1)= 3941

[R0mai]

wow tition, that's very nice and clean and obvious now.

Thank you for dreaming about this problem :).

I'll let you now when the official evaluating guide comes out.

_{*Now banging head to the wall...*}

[tition]

oh.. crap... My "solution" is wrong: I edited to indicate where. Well, I should then revert to my first proposal for a solution :((((

Sry for my stupidity!