In the book «Concrete Mathematics: A Foundation for Computer Science» by Donald Ervin Knuth, Oren Patashnik and Ronald Lewis Graham (Copyright ⓒ 1994, 1989 by Addison-Wesley Publishing Company, Inc.) there is a following problem (ch.1, No.13, page 19):

What's the maximum number of regions definable by n zig-zag lines, each of which consists of two parallel infinite half-lines joined by a straight segment?

The main idea of the solution is to consider very narrow zig-zags (almost straight lines) and then to use the result from the main text of the book, which gives the formula of regions definable by n straight lines.

My question is: does this «configuration» of zig-zags give us the real maximum of regions and why?

Original solution: 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$.

enter image description here

In this example (given in the book) with 2 zig-zag lines we have $ZZ_{2}=12$.

  • $\begingroup$ The book is called Concrete Mathematics, and is by Ronald Graham, Donald Knuth and Oren Patashnik. $\endgroup$ – Lord Shark the Unknown Sep 2 '17 at 17:38
  • $\begingroup$ Thank you. I suppose, «Concrete Math» doesn't sound misleading, since most of the mathematicians should know what I mean, but anyway, I corrected the name. $\endgroup$ – Simeon Y. Sep 2 '17 at 17:42
  • $\begingroup$ Surely all its authors deserve credit? $\endgroup$ – Lord Shark the Unknown Sep 2 '17 at 17:42
  • $\begingroup$ Thank you! I have this image, but my current rating is too low to insert it. By the way: do you have any ideas about the question? $\endgroup$ – Simeon Y. Sep 2 '17 at 19:30
  • $\begingroup$ I wasn't aware of your answer because you forgot to prefix it by arrobas followed by my pseudo. Besides: no, I have no idea. But what makes you think that it is not the maximum number ? Do you have a counterexample ? $\endgroup$ – Jean Marie Sep 2 '17 at 21:42

Your Answer

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

Browse other questions tagged or ask your own question.