Enigmatic Code

Programming Enigma Puzzles

Enigma 216: Point to point

From New Scientist #1362, 16th June 1983 [link]

As a challenging geometry puzzle, I asked my son to mark a prescribed number of points on a piece of paper, no three of them being in a straight line, and then to join each of the points to each of the others by straight lines. I knew by my choice of the number of points that he would not be able to do this without at least two of these lines crossing.

But I asked him to do it with some of his lines drawn in red, and the rest drawn in blue, and in such a way that it would be impossible to find a red triangle or a blue triangle in the whole configuration. This he managed.

How many points had I asked him to draw?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma216]

5 responses to “Enigma 216: Point to point

  1. Jim Randell 22 August 2014 at 3:27 pm

    Any three non-collinear points can be joined with non-crossing lines, which form the edges of a triangle. A fourth point can be added to give a lattice in the shape of a triangle with an additional interior point, so it is possible to have 4 points that are joined with non-crossing lines. But it is not possible to add a fifth point without requiring that the lines joining them must cross. So there must be at least 5 points.

    This Python program considers increasing sets of points, starting from 5, to find a colouring of some of the edges such that no triangles formed from the points have all sides the same colour. There is a solution for 5 points, and it finds the first solution in 32ms.

    from itertools import combinations, count
    from enigma import irange, subsets, first, printf
    
    def solve(n):
    
      # identify the points
      points = set(irange(1, n))
    
      # identify the lines
      edges = set(combinations(points, 2))
    
      # and identify the triangles
      triangles = set(((a, b), (a, c), (b, c)) for (a, b, c) in combinations(points, 3))
    
      # consider subsets of the edges (to paint one colour)
      for s in map(set, subsets(edges, min_size=1, max_size=len(edges) // 2)):
        # and look for triangles with all edges painted the same colour
        if any(c in (0, 3) for c in (len(s.intersection(t)) for t in triangles)): continue
        # if there are none, return this subset
        yield s
    
    for n in count(5):
      s = first(solve(n))
      if s:
        printf("{n}: {s[0]}")
        break
    

    Solution: He was asked to draw 5 points.

    There are several colourings of the edges that work, but they basically boil down to the following two arrangements:

    Enigma 216 - Solution 1

    Enigma 216 - Solution 2

    • Jim Randell 24 August 2014 at 8:40 pm

      Here’s a recursive version of my program that runs under Python 3.

      from itertools import combinations, count
      from enigma import irange, first, printf
      
      # partition <edges> into sets <A> and <B>
      # such that no set in <triangles> is a subset of <A> or <B>
      def solve(A, B, edges, triangles):
        # see if any triangle has all edges the same colour
        if any(A.issuperset(t) or B.issuperset(t) for t in triangles): return
        # are we done?
        if not edges:
          yield (A, B)
        else:
          # choose an edge
          es = set(edges)
          e = es.pop()
          # try to colour it
          yield from solve(A.union([e]), B, es, triangles)
          yield from solve(A, B.union([e]), es, triangles)
      
      # start with 5 points
      for n in count(5):
      
        # identify the points
        points = set(irange(1, n))
      
        # identify the lines
        edges = set(combinations(points, 2))
      
        # identify the triangles
        triangles = set(((a, b), (a, c), (b, c)) for (a, b, c) in combinations(points, 3))
      
        # choose an edge
        e = edges.pop()
        # solve for the remaining edges
        s = first(solve(set([e]), set(), edges, triangles))
      
        if s:
          printf("{n}: {s[0]}")
          break
      
  2. Jim Olson 23 August 2014 at 10:45 pm

    I guess I misread the enigma. I got the same answer but looking at your illustrations in both cases there are red triangles present and in the first illustration there is a blue and red triangle. I interpreted the enigma to mean you could not find red or blue triangles in the configuration.

    • Jim Randell 24 August 2014 at 8:39 pm

      I agree that the wording on this problem could be clearer. My program only looks for solutions using triangles with vertices at the selected points (the black blobs in the diagram). But if you want to look for solutions where the vertices of triangles may be formed by the intersections of the lines, then obviously there are more triangles to consider, but each line between selected points can only be of one colour, so any solution to the second problem must also be a solution to the first.

      By considering the following equivalence of graphs, the solution I found also gives a solution to this second problem:

      Enigma 216 - Solutions

      There is a single additional crossing point X (the intersection of AC and BD). This adds 4 new triangles: XAB, XAD, XBC, XCD to be considered.

      Either way both puzzles can be solved by selecting 5 points.

  3. arthurvause 29 August 2014 at 11:04 am

    Ramsey’s Theorem provides a proof that 6 or more points must contain a triangle of one colour.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: