Enigmatic Code

Programming Enigma Puzzles

Enigma 1769: Crossing lines

From New Scientist #2937, 5th October 2013 [link]

I have drawn a number of straight lines across a large sheet of paper, each extending from edge to edge on the paper, so that each line crosses all the other lines. One of the intersections is between three lines, all the others are between just two lines, and none of them are on the edge of the paper. I counted the number of non-overlapping areas formed that did not touch the edge of the paper and found that this was exactly three times the number of non-overlapping areas that did touch the edge of the paper.

How many lines did I draw?

[enigma1769]

Advertisements

3 responses to “Enigma 1769: Crossing lines

  1. Jim Randell 2 October 2013 at 6:34 pm

    If my reasoning is correct (and I think it is), this is fairly straightforward. This Python program runs in 38ms.

    from enigma import printf
    
    # we start with 3 lines that meet at a point,
    # creating 0 internal regions and 6 external regions
    (n, i, e) = (3, 0, 6)
    
    # then add more lines, each one adds n-2 internal
    # regions and 2 external regions
    while True:
      printf("n={n} i={i} e={e}")
      if i == 3 * e: break
      n += 1
      i += (n - 2)
      e += 2
    

    Solution: You drew 15 lines.

    • Jim Randell 30 October 2013 at 6:12 pm

      This diagram shows how the number of regions grows by n when the nth line is added. (n – 2) internal regions (coloured), and 2 external regions. This gives a formulae of I(n) = T(n – 2) – 1, E(n) = 2n.

      Enigma 1769 - Solution

      In the final diagram n = 7, I(n) = E(n) = 14.

      So the solution to the problem is when I(n) = 3E(n):

      (n – 2)(n – 1)/2 – 1 = 6n
      (n² – 3n + 2) – 2 = 12n
      n² = 15n
      n = 15 (n ≠ 0).

  2. arthurvause 2 October 2013 at 11:01 pm

    Using induction, for n lines the total number of areas is n(n+1)/2, the number of areas touching the edge is 2n, so we are looking for n satisfying n(n+1)/2 -2n = 3(2n)

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: