Number of regions in NxN board with diagonals
Source: MEMO 2015, problem T-4
August 28, 2015
combinatorics
Problem Statement
Let be a positive integer. In each of the unit squares of an board, one of the two diagonals is drawn. The drawn diagonals divide the board into regions. For each , determine the smallest and the largest possible values of .[asy]
draw((0,0)--(3,0)--(3,3)--(0,3)--cycle);
draw((1,0)--(1,3), dotted);
draw((2,0)--(2,3), dotted);
draw((0,1)--(3,1), dotted);
draw((0,2)--(3,2), dotted);
draw((1,0)--(0,1)--(2,3)--(3,2)--(2,1)--(0,3));
draw((1,1)--(2,0)--(3,1));
label("",(0.35,2));
label("",(1,2.65));
label("",(2,2));
label("",(2.65,2.65));
label("",(0.35,0.35));
label("",(1.3,1.3));
label("",(2.65,0.35));
label("Example with , ",(0,-0.3)--(3,-0.3),S);
[/asy]