Rectangle and Squares | PRMO 2019 | Question 24

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)}\)

\(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}-.....\)

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

then 703=\(19 \times 37\) then largest factor =37.

Subscribe to Cheenta at Youtube