Problem 9:
Each square of an $n×n$ chessboard is either red or green. The board is colored such that in any $2×2$ block of adjacent squares there are exactly $2$ green squares and $2$ red squares. How many ways can the chessboard be colored in this way? Note the number of ways for a $2×2$ chessboard is $6$ and the number of ways for a $3×3$ chessboard is $14$ which is bigger than $2^3$.
BdMO National Higher Secondary 2009/9
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
-
Cryptic.shohag
- Posts:16
- Joined:Fri Dec 17, 2010 11:32 pm
- Location:Dhaka, Bangladesh
- Contact:
Re: BdMO National Higher Secondary 2009/9
Though it was a problem of combinatorics, most of us solved it as a sequence that year.... :p
God does not care about our mathematical difficulties; He integrates empirically. ~Albert Einstein
-
Shadmanmajid
- Posts:2
- Joined:Sun Jan 20, 2013 10:51 pm
Re: BdMO National Higher Secondary 2009/9
Is the answer $2^n-(n-1)n$ ?
-
samiul_samin
- Posts:1007
- Joined:Sat Dec 09, 2017 1:32 pm
Re: BdMO National Higher Secondary 2009/9
Isn't it a Catalan reccurtion?