6
$\begingroup$

Fellows of Math.SE, I have been scratching my head at a solution to an exercise in Donald Knuth's Concrete Math. Here is the problem:

enter image description here

Here is the solution (I hid it in case someone wants to solve this on their own)

Given $n$ straight lines that define $L_n$ regions, we can replace them by extremely narrow zig-zags with segments sufficiently long that there are nine intersections between each pair of zig-zags. This shows that $ZZ_n = ZZ_{n−1} +9n−8$, for all $n > 0$; consequently $ZZ_n = 9S_n −8n+1 = \frac{9n^2 − 7n}{2} +1$.

$L_n$ is the number of regions definable by $n$ lines, which is solved as an example earlier in the text. It equals $S_n + 1$, where $S_n = \sum_{k=1}^n k$. I am having difficulty understanding the recurrence solution. I'll hide my question, just to be extra careful I don't spoil this wonderful problem for anyone.

Where does the "$-8$" come from? Is the recurrence better understood as $ZZ_n = ZZ_{n−1} +9(n-1)+1$? Or does that further convolute the meaning of the recurrence? I figure there must "-8" must have to do with "lost regions" due to the half-lines, but I am having trouble putting my finger on it.

I really love this problem and would love to understand the solution in its entirety! Thank you!

$\endgroup$
  • $\begingroup$ Isn't this typical of "maximum number of intersections of $n$ lines / circles / whatever"? Reviewing that first (which is much simplified) can help you understand this better. $\endgroup$ – Calvin Lin Jul 5 '13 at 16:59
2
$\begingroup$

Your observation is correct. If you believe the first step, then there are $9(n-1)$ intersections of the new zigzag with the existing constelation. Now any two consecutive intersection points cut an existing bounded region into two regions, resulting in a total of $9(n-1)-1$ regions. Similarly the line segment between the first intersection and infinity and the line segment bewteen the last intersection and infinity each cut an existing unbounded region into two. So there are $9(n-1)-1+2$ new regions.

$\endgroup$
  • $\begingroup$ Thank you for clearing this up! That makes perfect sense. $\endgroup$ – A.E Jul 5 '13 at 17:30
3
$\begingroup$

$ZZ_n = ZZ_{n-1} + n + 8(n-1)$.

Add one new straight line first, intersecting the previous $n-1$ lines. This gives the term $n$. Then make the small ziz-zags as suggested in the hint. This adds an additional $8$ regions at each of the $n-1$ intersections.

enter image description here

$\endgroup$
  • $\begingroup$ Thanks! I'm glad I've received multiple interpretations of this solution. In fact I think this may be even more intuitive. $\endgroup$ – A.E Jul 5 '13 at 17:34
  • $\begingroup$ @Orangutango: I don't believe my own solution, because I was imagining being able to zig-zag a straight line more than once - in fact once at each intersection. You may wish to revert to the other solution. $\endgroup$ – bryanj Jul 5 '13 at 18:12
  • 1
    $\begingroup$ I think it still makes sense: $L_n = L_{n-1} + n$ counts the total number of regions that can be constructed by only lines. If you then stretch each line out a tiny amount and create zig-zag segment, you get $n-1$ sections like the one you colored in; one per intersection. Since each of the $n-1$ sections creates 8 additional regions, I believe your recurrence is a proper interpretation. But, I'll revert to the other solution for now. $\endgroup$ – A.E Jul 5 '13 at 18:28
  • $\begingroup$ @Orangutango: Oh - yep, it does work! Right - as long as the ziggy part is really long and really skinny! Thanks for helping me understand my own solution! ;) $\endgroup$ – bryanj Jul 5 '13 at 18:35
  • $\begingroup$ This explaination is really clearer than the answer in CM book, thanks! $\endgroup$ – Xiao Hanyu Jun 27 '15 at 3:58
2
$\begingroup$

What also works is:

When you assume first assume that, for every zig zag line, there are two parallel infinite lines and one infinite line intersecting both (so we extend our line segments).

Now, for the case of the zig zag lines, every parallel line stops at the intersection with the third line, so you have to subtract 2 regions from $L_{3n}$ for every zig zag line. The third line is bounded in two directions, so you have to subtract two additional regions for each zig zag line. The last step is to subtract 1 region because the two parallel lines don't intersect.

So $$ZZ_n = L_{3n} - 5n = \frac{9n^2+3n}{2}-5n+1 = \frac{9n^2+3n}{2} - \frac{10n}{2} +1 = \frac{9n^2-7n}{2} + 1$$

$\endgroup$
1
$\begingroup$

I figured a different approach. We all know by now,

  • Finding 1: Each new zig-zag will intersect each old zig-zags at $9$ points.
  • Finding 2: When two zig-zags intersect, they create $8$ finite regions around intersections (see colored regions from the picture of bryanj's answer).

Let's assume each zig-zag is so thin that it can be drawn as a line (two parallel lines are too close to each other) and the segment connecting two parallels is quite long. Now to draw the $n$ zig-zags on a plane, first we will draw $n$ lines on that plane intersecting each other. Then we will replace $n$ lines with $n$ 'thin' zig-zags I was talking about.

For example, if $n = 3$, we draw 'simple lines' first, and we get 7 regions (See the picture below). It has $L_3 = 7$ regions and $\binom{3}{2} = 3$ intersections.

enter image description here

Now replacing 'simple lines' with zig-zags, we get, this picture.

enter image description here

So, $L_3 = 7$ regions are still there. For each of $\binom{3}{2} = 3$ intersections, we get $8$ regions (from finding 2). Total $L_3 + 8\times\binom{3}{2}$ regions.

Finally, for $n$ zig-zags, $ZZ_n = L_n + 8\times\binom{n}{2}$

$\endgroup$
  • $\begingroup$ how does 3c2 come? $\endgroup$ – Brij Raj Kishore May 17 '18 at 19:07
  • 1
    $\begingroup$ It takes 2 lines (not parallel) to form 1 intersection. Given 3 lines, you can form 3c2 groups each having 2 lines. Hence, 3c2 intersections. $\endgroup$ – shonku May 17 '18 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.