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 1 of 5: Count turning points

Previous step Next step

m\le n(n-1)

Detailed analysis

Call $P_1,\ldots,P_m$ turning points. Every turning point is vertically adjacent to exactly one other turning point, so at each fixed $x=k\in\{1,\ldots,n\}$ their number is even and at most $n-1$ . Therefore $m\le n(n-1)$ .