We worked with "nonthreatening rook diagrams" and proved our first theorem ever...
Consider the family of boards of growing sizes as shown below. We will call their length to be the number of exposed NW squares (so the sizes here are 2 and 3).
Now, how many rook diagrams for these boards are there? Let us call R(n) the number of rook diagrams in such a board of length n. We computed:
R(1)=2, R(2)=3, R(3)=5... It does remind us of Fibonacci numbers!
So, let's remember that hte Fibonacci numbers satisfy F(n+1)=F(n)+F(n-1), and F(3)=2, F(4)=3, F(5)=5... So if we can prove that R(n+1)=R(n)+R(n-1), then knowing that R and F start similarly, we get that always R(n)=F(n+2)...
To prove that R(n+1)=R(n)+R(n-1) we look at the ways to place a rook into the first row:
One more question: here are two star pictures: which is taken closer to the equator?
Consider the family of boards of growing sizes as shown below. We will call their length to be the number of exposed NW squares (so the sizes here are 2 and 3).
R(1)=2, R(2)=3, R(3)=5... It does remind us of Fibonacci numbers!
So, let's remember that hte Fibonacci numbers satisfy F(n+1)=F(n)+F(n-1), and F(3)=2, F(4)=3, F(5)=5... So if we can prove that R(n+1)=R(n)+R(n-1), then knowing that R and F start similarly, we get that always R(n)=F(n+2)...
To prove that R(n+1)=R(n)+R(n-1) we look at the ways to place a rook into the first row:
As the picture shows, these two ways yield R(n) and R(n-1) as numbers to place the rooks - QED.
What about the rook number for this board?
One more question: here are two star pictures: which is taken closer to the equator?
No comments:
Post a Comment