MathDB

In the city of

\textrm{Las Cobayas}

, the houses are arranged in a rectangular grid of

3

rows and

n\geq 2

columns, as illustrated in the figure.

\textrm{Mich}

plans to move there and wants to tour the city to visit some of the houses in a way that he visits at least one house from each column and does not visit the same house more than once. During his tour,

\textrm{Mich}

can move between adjacent houses, that is, after visiting a house, he can continue his journey by visiting one of the neighboring houses to the north, south, east, or west, which are at most four. The figure illustrates one

\textrm{Mich´s}

position (circle), and the houses to which he can move (triangles). Let

f(n)

be the number of ways

\textrm{Mich}

can complete his tour starting from a house in the first column and ending at a house in the last column. Prove that

f(n)

is odd. [asy]size(200);
draw((0,0)--(1,0)--(1,1)--(0,1)--cycle); draw((2,0)--(3,0)--(3,1)--(2,1)--cycle); draw((4,0)--(5,0)--(5,1)--(4,1)--cycle);
draw((0,2)--(1,2)--(1,3)--(0,3)--cycle); draw((2,2)--(3,2)--(3,3)--(2,3)--cycle); draw((4,2)--(5,2)--(5,3)--(4,3)--cycle);
draw((0,4)--(1,4)--(1,5)--(0,5)--cycle); draw((2,4)--(3,4)--(3,5)--(2,5)--cycle); draw((4,4)--(5,4)--(5,5)--(4,5)--cycle); fill(circle((0.5,2.5), 0.4), black); fill((0.1262,4.15)--(0.8738,4.15)--(0.5,4.7974)--cycle, black); fill((0.1262,0.15)--(0.8738,0.15)--(0.5,0.7974)--cycle, black); fill((2.1262,2.15)--(2.8738,2.15)--(2.5,2.7974)--cycle, black);
fill(circle((6,0.5), 0.07), black); fill(circle((6.3,0.5), 0.07), black); fill(circle((6.6,0.5), 0.07), black);
fill(circle((6,2.5), 0.07), black); fill(circle((6.3,2.5), 0.07), black); fill(circle((6.6,2.5), 0.07), black);
fill(circle((6,4.5), 0.07), black); fill(circle((6.3,4.5), 0.07), black); fill(circle((6.6,4.5), 0.07), black);
draw((8,0)--(9,0)--(9,1)--(8,1)--cycle); draw((10,0)--(11,0)--(11,1)--(10,1)--cycle);
draw((8,2)--(9,2)--(9,3)--(8,3)--cycle); draw((10,2)--(11,2)--(11,3)--(10,3)--cycle);
draw((8,4)--(9,4)--(9,5)--(8,5)--cycle); draw((10,4)--(11,4)--(11,5)--(10,5)--cycle);
draw((0,-0.2)--(0,-0.5)--(5.5,-0.5)--(5.5,-0.8)--(5.5,-0.5)--(11,-0.5)--(11,-0.5)--(11,-0.2)); label("

n

", (5.22,-1.15), dir(0), fontsize(10)); label("

\textrm{West}

", (-2,2.5), dir(0), fontsize(10)); label("

\textrm{East}

", (11.1,2.5), dir(0), fontsize(10)); label("

\textrm{North}

", (4.5,5.7), dir(0), fontsize(10)); label("

\textrm{South}

", (4.5,-2), dir(0), fontsize(10)); draw((0.5,2.5)--(2,2.5)--(1.8,2.7)--(2,2.5)--(1.8,2.3)); draw((0.5,2.5)--(0.5,4)--(0.3,3.7)--(0.5,4)--(0.7,3.7)); draw((0.5,2.5)--(0.5,1)--(0.3,1.3)--(0.5,1)--(0.7,1.3)); [/asy]

Problem Statement