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 3 of 5: Initial odd case

m=6=3(3-1)

Detailed analysis

The sequence $(0,1),(1,1),(1,2),(2,2),(2,1),(3,1),(3,3),(4,3)$ has six turning points, so $m=6=3(3-1)$ , and it satisfies all conditions.