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 4 of 5: Inductive construction

Previous step Next step

(n-4)(n-5)+n^2-(n-4)^2-4=n(n-1)

Detailed analysis

For odd $n\ge5$ , place a translated copy of an extremal path for $n-4$ inside the dotted $(n-4)\times(n-4)$ square, and use every allowed lattice point in the surrounding four strips except $(n,2),(n-1,n-2),(2,3),(1,n-1)$ . The segments alternate and meet as required.