## November 2003

<<October
**November**
December>>

Solution:

Let *K ⊂ R*^{2} be a convex compact body of perimeter 2*q* and diameter *d*. Let *r* be a positive integer. As *Sn*(*K, r*) we denote the smallest number *s* such that for any curve φ ⊂ *K* of length greater than *s* there is a line intersecting the curve φ in at least *r* + 1 different points.

We will first show:

Fix the compactSn(K, r) ≥rq, ifris even;

Sn(K, r) = (r- 1)q+d, ifris odd.

*K*and the number

*r*. Let 2

*q*be the perimeter of

*K*and

*d*be the diameter of

*K*. Put

*s*=

*rq*if

*r*is even and

*s*= (

*r*- 1)

*q*+

*d*if

*r*is odd.

Let φ : [0; 1] →

*K*be the curve of length greater than

*s*. By the definition of the length we can choose the numbers 0 =

*α*

_{0}< · · · <

*α*= 1 such that the length of the broken line with the sequence of vertices φ(

_{n}*α*

_{0}), . . . , φ(

*α*) is greater than

_{n}*s*. Let

*l*

_{1}, . . . ,

*l*be the lengths of the segments of the broken line and

_{n}*α*

_{1}, . . . ,

*α*be the angles with these segments and the

_{n}*x*-axis. For an angle

*θ*∈ [0;2π] as

*l*(

*θ*) we denote the sum of the lengths of the projections of the segments

*l*onto the line

_{i}*L*= {(

_{θ}*x*,

*y*) : (

*x*,

*y*) = (

*t*cos

*θ*,

*t*sin

*θ*)}. Thus l(

*θ*) = ∑

*l*| cos(

_{i}*θ*-

*α*)|. As

_{i}*k*(

*θ*) we denote the length of the projection of

*K*onto the line

*L*. We shall need the following fact.

_{θ}*Fact.*

Remark that for every

∫^{2π}k(θ)dθ= 4q_{0}

*ε*> 0 there is a convex polygon

*K*of perimeter 2

_{ε}*q*such that |

_{ε}*q*-

*q*| <

_{ε}*ε*and for each

*θ ∈*[0;2π] holds |

*k*(

_{ε}*θ*) -

*k*(

*θ*)| <

*θ*where

*k*is the length of the projection of

_{ε}*K*onto the line

_{ε}*L*. Hence it suffices to prove the fact only in the case when

_{α}*K*is a convex polygon. Let

*k*

_{1}, . . . ,

*k*be the lengths of the segments of the broken line and

_{n}*α*

_{1}, . . . ,

*α*

_{n}be the angles with these segments and the

*x*-axis. Then

Now we are able to prove the bounds. At first suppose that

∫^{2π}k(θ)dθ=_{0}

1∫∑^{2π}k|cos(_{i}θ-α)|_{i}dθ=2 _{0}

1∑∫^{2π}k|cos(_{i}θ-α)|_{i}dθ=2 _{0}

1∑∫^{2π}k|cos(_{i}β)|dβ=2 _{0}

2 ∑k= 4_{i}q

*r*is even. To the rest of the proof it suffices to show that there is an angle

*θ'*such that

*l*(

*θ'*) >

*rk*(

*θ'*). Suppose the contrary. Then

4rq=

r∫^{2π}k(θ)dθ≥0

∫^{2π}l(θ)dθ=0

∫^{2π}l(θ)dθ=0

∫^{2π}∑ l(_{i}|cosθ-α)|_{i}dθ=0

∑ ∫^{2π}l(_{i}|cosθ-α)|_{i}dθ=0 ∑4

∑ ∫^{2π}l(_{i}|cosβ)|dβ=0 l> 4_{i}s= 4rq

The contradiction.

Now suppose that

*r*is odd. Add to the broken line the segment connecting its ends. Let the length of the segment be

*l*

_{0}and

*θ*be the angle with the segment and the

_{0}*x*-axis. To the rest of the proof it suffices to show that there is an angle

*θ'*such that

*l*(

*θ'*) >

*rl*| cos(

_{0}*θ'*)| + (r - 1)(

*k*(

*θ'*) -

*l*

_{0}| cos(

*θ'*)|) = (

*r*- 1)

*k*(

*θ'*) +

*l*

_{0}| cos(

*θ'*)|. That is because each line not intersecting

*l*

_{0}and the vertices of the broken line intersects the broken line an even number of times.

Suppose the contrary. Then

4(Which yields the contradiction sincer-1)q+4l_{0}=

∫^{2π}( r-1)k(θ)+l_{0}|cos(θ)|dθ≥∫^{2π}l(θ)dθ=0 0

∫^{2π}∑l|cos(_{i}θ-α)|_{i}dθ=0

∑∫^{2π}l|cos(_{i}α-α)|_{i}dα=0

∑∫^{2π}l|cos(_{i}β)|dβ=0 ∑4l> 4_{i}s= 4rq+ 4d

*l*

_{0}≤

*d*.

The matching lower bounds: if

*r*is even, let the curve go

*r*/2 times around the perimeter, curving slightly to avoid any straight lines but remaining convex. The attached picture illustrates the case where K is a square (rather than a pentagon). If

*r*is odd, let the curve go almost (

*r*-1)/2 times around the perimeter, then down the diagonal, again always curving slightly. The 2 reason we go "almost" (

*r*-1)/2 times around the perimeter is to ensure that any straight line

*L*which intersects this curved diagonal twice, will intersect the perimeter-curve at most

*r*- 2 times rather than

*r*- 1.

For our particular case,

*r*= 5, 2

*q*= 5, and

*d*= 2sin(2π/10) = 1.618, so that the bound is (

*r*- 1)

*q*+

*d*= 11.618.

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com