Enigmatic Code

Programming Enigma Puzzles

Enigma 1110: Dots and lines

From New Scientist #2266, 25th November 2000

Matthew and Ben are playing a game. The board is a 1-kilometre square divided into 1-centimetre squares. The centre of each small square is marked by a red dot.

Matthew begins the game by choosing a number. Ben then selects that number of red dots. Finally Matthew chooses two of Ben’s selected dots and draws a straight line from one to the other. Matthew wins if his line passes through a red dot other than those at its ends; otherwise Ben wins.

What is the smallest number that Matthew can choose to be certain of winning?

In the magazine this puzzle was incorrectly labelled Enigma 1104.

[enigma1110]

Advertisements

6 responses to “Enigma 1110: Dots and lines

  1. Jim Randell 19 June 2017 at 8:04 am

    In the following I use the term “point” (or “lattice point”) to refer to the red dots.

    We are trying to find the smallest number of points k such that given any set of k points, we can always find a pair of points such that the line segment between these two points passes through an intermediate point.

    We can easily choose up to 4 points, such that the line segment formed by any pair does not pass through an intermediate point. We just need to choose the points from the vertices of the unit square: (0, 0), (0, 1), (1, 0), (1, 1). But there are other solutions with four points, e.g. (0, 0), (2, 3), (5, 7), (7, 10).

    If we consider the parities of the co-ordinates of the points, using their residues modulo 2, we get one of the following values for each point: (0, 0), (0, 1), (1, 0), (1, 1). (These are the vertices of the unit square again).

    And if we try to add a further point to the set, the parities of its co-ordinates will have one of these 4 values. So in any set of 5 (or more) points there will be at least two points that have the same parity pairing.

    Consider two different points with the same parity pairing. The parity is (p, q) and the points are (2a + p, 2b + q) and (2c + p, 2d + q). Where p, q are 0 or 1 and a, b, c, d are integers. Then the mid-point of the line segment between these two points is:

    ((2a + p + 2c + p) / 2, (2b + q + 2d + q) / 2) = (a + c + p, b + d + q)

    Which is a lattice point.

    So in any set of 5 points there will always be two points such that the line segment joining those points passes through an intermediate point.

    Solution: The smallest number Matthew can choose and be certain of winning is 5.

    In general the number of intermediate points on the line segment between the points (a, b) and (c, d) is given by:

    gcd(|a – c|, |b – d|) – 1

    (See: Enigma 1308).

    So, there will be no intermediate points if:

    gcd(|a – c|, |b – d|) = 1

    The following Python program exhaustively looks for k-sets of dots on the grid with no pair that form a line segment that passes through an intermediate point.

    from enigma import irange, gcd, arg, printf
    
    # there are 100000 centimetres in a kilometre
    k = arg(5, 0, int)
    N = arg(100000, 1, int)
    printf("[N={N}, k={k}]")
    
    # max index
    M = (N ** 2) - 1
    
    # choose <k> points (from index <i> onwards) that form a set with <ps>
    def solve(k, ps=[], i=0):
      if k == 0:
        return ps
      else:
        # choose the next point
        for j in irange(i, M):
          (y, x) = divmod(j, N)
          if all(gcd(abs(x - a), abs(y - b)) == 1 for (a, b) in ps):
            return solve(k - 1, ps + [(x, y)], j + 1)
        return None
    
    # start with (0, 0)
    ps = solve(k - 1, [(0, 0)], 1)
    printf("[N={N}] {k} => {ps}")
    

    With the default settings (k=5, and a 100,000 × 100,000 grid) the program takes 1h50m to confirm that it is not possible to find a suitable set.

    But the parameters can be specified on the command line, and 5-sets on a 1,000 × 1,000 grid can be checked in under a second.

  2. Hugh Casement 19 June 2017 at 9:16 am

    Is it as simple as that?  If I choose points (0, 0) and (3, 18) they have different parities, but the line segment joining them passes through (1, 6) and (2, 12).

    Incidentally, red dots in squares is an unnecessary complication.  They play the game on a square grid; they can reserve the red pen for marking the grid intersections to be joined.
    And I think they’re soon going to tire of their game!

    • Jim Randell 19 June 2017 at 10:09 am

      @Hugh: The argument is that if a pair of points have the same parity pairing then the line between them passes through an intermediate point. The reverse does not hold (as you point out). Although if the line between two points is split into n segments by intermediate points, then the two original points will have the same pair of residues modulo n.

      The two points you give have different pairs of residues modulo 2 (so there is no intermediate point halfway between them), but the distances between their respective x and y co-ordinates have a GCD of 3, so the line joining them is split into three segments and there are two intermediate points at distances 1/3 and 2/3 between them. The points have the same pair of residues modulo 3.

      You can follow the same argument I give above to show that in any set of 3×3 + 1 = 10 points there will always be a pair of points that are joined by a line segment that is split into thirds by intermediate points. (We can chose the 9 points given by (0, 1, 2) × (0, 1, 2) to find a set of 9 points that don’t have this property).

      But we already know from considering residues modulo 2 that we can find a pair where the line segment is split in half by intermediate points in a smaller set of points.

      The reasoning implies you won’t be able to find three other points to go with (0, 0) and (3, 18) to make a set that does not contain a pair with a line segment that is split in half by an intermediate point.

  3. Hugh Casement 19 June 2017 at 10:31 am

    I’m going to have to reread that a couple of time before it sinks in!

    Is there a rule that Ben can follow to choose four points (or three, or just two) such that there can be no intermediate grid points?  Will he have to take their coordinates modulo every prime number in the book, to cover all parities besides the normal twofold parity?

    • Jim Randell 19 June 2017 at 12:59 pm

      Choosing two points is easy. You just need to make sure the differences in the x and y co-ordinates are co-prime. Armed with a list of co-prime pairs we can choose the first point arbitrarily, and then the second point would have its co-ordinates shifted by the co-prime pair.

      There’s a couple of mechanisms for generating co-prime pairs given in Enigma 1182, which Ben could use to generate co-prime pairs less than 100,000. (These are available as the functions farey() and coprime_pairs() in the enigma.py library).

      For sets of 4 points, Ben can use the corners of any unit square (there are quite a lot of those), or he could use a “skew square” with corners at (0, 1), (1, k+2), (k+2, k+1), (k+1, 0). The distances between the co-ordinates of adjacent corners are always 1 and k+1 (which are necessarily co-prime), and the distances between the co-ordinates of the diagonals are k and k+2. So as long as k and k+2 co-prime that would work. Armed with a list of twin primes [ OEIS A077800 ], Ben could make quite a lot of 4-sets.

  4. Hugh Casement 19 June 2017 at 2:22 pm

    Thanks, Jim.  I do value your insights and analyses.

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: