Try this beautiful problem from the Pre-RMO, 2019 based on Rectangle and Squares.
A \(1 \times n\) rectangle \(n \geq 1\) is divided into n unit \( 1 \times 1 \) squares. Each square of this rectangle is coloured red, blue or green. Let f(n) be the number of colourings of the rectangle in which there are an even number of red squares, find the largest prime factor of \(\frac{f(9)}{f(3)}\)
Combinations
Algebra
Integers
But try the problem first...
Answer: is 37.
PRMO, 2019, Question 24
Combinatorics by Brualdi
First hint
\(f(n)\)=\({n \choose 0}2^{n} + {n\choose2} 2^{n-2} + {n\choose 4} 2^{n-4}+.....\) and \((2+1)^{n}\)=\({n\choose0} 2^{n}+ {n\choose1} 2^{n-1} + {n\choose2} 2^{n-2} +.....\) and \((2-1)^{n}\)= \({n\choose0} 2^{n}-{n\choose1} 2^{n-1}+{n\choose2} 2^{n-2}-.....\)
Second Hint
adding gives \(\frac{3^{n}+1}{2}=f(n)\) \(\frac{f(9)}{f(3)}=\frac{3^{9}+1}{3^{3}+1}=3^{6}-27+1\)=703
Final Step
then 703=\(19 \times 37\) then largest factor =37.
Try this beautiful problem from the Pre-RMO, 2019 based on Rectangle and Squares.
A \(1 \times n\) rectangle \(n \geq 1\) is divided into n unit \( 1 \times 1 \) squares. Each square of this rectangle is coloured red, blue or green. Let f(n) be the number of colourings of the rectangle in which there are an even number of red squares, find the largest prime factor of \(\frac{f(9)}{f(3)}\)
Combinations
Algebra
Integers
But try the problem first...
Answer: is 37.
PRMO, 2019, Question 24
Combinatorics by Brualdi
First hint
\(f(n)\)=\({n \choose 0}2^{n} + {n\choose2} 2^{n-2} + {n\choose 4} 2^{n-4}+.....\) and \((2+1)^{n}\)=\({n\choose0} 2^{n}+ {n\choose1} 2^{n-1} + {n\choose2} 2^{n-2} +.....\) and \((2-1)^{n}\)= \({n\choose0} 2^{n}-{n\choose1} 2^{n-1}+{n\choose2} 2^{n-2}-.....\)
Second Hint
adding gives \(\frac{3^{n}+1}{2}=f(n)\) \(\frac{f(9)}{f(3)}=\frac{3^{9}+1}{3^{3}+1}=3^{6}-27+1\)=703
Final Step
then 703=\(19 \times 37\) then largest factor =37.
