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 5 of 5: Count and conclude

Previous step Next step

m=n(n-1)

Detailed analysis

The inner path contributes $(n-4)(n-5)$ turning points and the surrounding frame contributes $n^2-(n-4)^2-4$ ; their sum is $n(n-1)$ . Combined with the upper bound, this proves the maximum.