Problem 4

Let

n

be a fixed positive odd integer. Take

m+2

distinct points

P_0,P_1,\ldots,P_{m+1}

in the coordinate plane such that: (1)

P_0=(0,1)

P_{m+1}=(n+1,n)

, and for

1\le i\le m

, both coordinates of

P_i

are integers between

1

and

n

inclusive; (2) for

0\le i\le m

, segment

P_iP_{i+1}

is parallel to the

x

-axis if

i

is even and to the

y

-axis if

i

is odd; (3) for

0\le i<j\le m

, segments

P_iP_{i+1}

and

P_jP_{j+1}

share at most one point. Determine the maximum possible value of

m

Step 2 of 5: Base case

m=0

Detailed analysis

For n=1, the two prescribed endpoints P_0=(0,1), P_1=(2,1) form the horizontal segment required for i=0, so m=0=n(n-1).