Ponder This Challenge - November 2003 - Line intersecting curve in a pentagon

Ponder This Challenge:

This puzzle is adapted from one published by S. B. Gashkov. The updated version is due to Sasha Ravsky, Gyozo Nagy, Gabor Sagi and the puzzlemaster.

Give the exact value for s, and an approximation correct to three decimal places, making the following statements true; provide justification for both the upper and lower bounds.

P is a regular pentagon one meter on each side. Consider a curve C of
some specified length T, lying within P, containing no straight line segments.
For any curve whose length T exceeds s, there is a straight line that intersects
the curve at least six times. But for any T less than s, there is a curve of
length T such that any straight line hits it at most five times.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  Solution:

  Let K ⊂ R2 be a convex compact body of perimeter 2q 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 compact K and the number r. Let 2q 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 < · · · < αn = 1 such that the length of the broken line with the sequence of vertices φ(α0), . . . , φ(αn) is greater than s. Let l1, . . . , ln be the lengths of the segments of the broken line and α1, . . . , αn be the angles with these segments and the x-axis. For an angle θ ∈ [0;2π] as l(θ) we denote the sum of the lengths of the projections of the segments li onto the line Lθ = {(x, y) : (x, y) = (t cos θ, t sin θ)}. Thus l(θ) = ∑li| cos(θ - αi)|. As 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 ε > 0 there is a convex polygon Kε of perimeter 2qε 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 k1, . . . , kn be the lengths of the segments of the broken line and α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 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

  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 l0 and θ0 be the angle with the segment and the x-axis. To the rest of the proof it suffices to show that there is an angle θ' such that l(θ') > rl0| cos(θ')| + (r - 1)(k(θ') - l0| cos(θ')|) = (r - 1)k(θ') + l0| cos(θ')|. That is because each line not intersecting l0 and the vertices of the broken line intersects the broken line an even number of times.

  Suppose the contrary. Then

  Which yields the contradiction since l0 ≤ 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, 2q = 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

Solvers

• Dan Dima (11.6.2003 @08:53:00 AM EDT)
• Michael Brand (11.7.2003 @03:21:02 AM EDT)
• Alan O'Donnell (11.7.2003 @07:19:57 AM EDT)
• Vladimir Sedach (11.7.2003 @01:21:06 PM EDT)
• Graeme McRae (11.7.2003 @07:56:58 PM EDT)
• Sarang Aravamuthan (11.7.2003 @07:34:30 PM EDT)
• Alex Wagner (11.11.2003 @01:19:00 PM EDT)
• R. Nandakumar (11.15.2003 @04:34:06 AM EDT)
• Hagen von Eitzen (11.17.2003 @10:57:27 AM EDT)
• John Ritson (11.19.2003 @11:52:18 PM EDT)
• Steve Plate (11.20.2003 @01:02:11 AM EDT)
• Niraj Jha (11.21.2003 @12:30:54 AM EDT)
• Daniel Bitin (11.30.2003 @12:40:08 PM EDT)