Enigmatic Code

Programming Enigma Puzzles

Enigma 1248: Rows and columns

From New Scientist #2404, 19th July 2003 [link]

First, draw a chessboard. Now number the horizontal rows 1, 2, …, 8, from top to bottom and number the vertical columns 1, 2, …, 8, from left to right. You have to put a whole number in each of the sixty-four squares, subject to two conditions:

1. Rows 1, 2, 3, 4, 5, 6, 7, 8 are equal to columns 3, 6, 4, 4, 1, 6, 8, 6, respectively;

2. If N is the largest number you write on the chessboard then you must also write 1, 2, …, N−1 on the chessboard.

The sum of the sixty-four numbers you write on the chessboard is your total.

1. What is the largest total you can obtain?

If you look at your chessboard with the numbers on it you will find that every column is equal to a row. Now imagine we are considering chessboards of all sizes.

2. Is it possible to find an n×n chessboard, with a number in every square, so that every row equals a column, but there is at least one column which does not equal a row? If so, what is the smallest n for which it is possible?

See also Enigma 1225.

[enigma1248]

Advertisements

2 responses to “Enigma 1248: Rows and columns

  1. Jim Randell 16 March 2015 at 8:13 am

    This Python program solves the first part of the problem in 35ms.

    from collections import Counter
    from enigma import irange, chunk, printf
    
    # in grid <g> merge <s> with <t>
    def merge(g, s, t):
      for (i, x) in enumerate(g):
        if x == s:
          g[i] = t
    
    # create an N x N grid with specified rows and columns equated
    # rcs - list of (r, c) rows and columns (0-indexed)
    def grid(N, rcs):
      # make the grid
      g = [0] * (N * N)
      # label the squares (from 1)
      n = 1
      # equate the rows and columns
      for (r, c) in rcs:
        for i in irange(0, N - 1):
          (ri, ci) = (r * N + i, c + N * i)
          if g[ri] == 0:
            if g[ci] == 0:
              # allocate a new label
              g[ri] = g[ci] = n
              n += 1
            else:
              g[ri] = g[ci]
          else:
            if g[ci] == 0:
              g[ci] = g[ri]
            elif g[ci] != g[ri]:
              # merge the two labels
              merge(g, max(g[ri], g[ci]), min(g[ri], g[ci]))
      return g
    
    # generate the grid (columns need to be 0-indexed)
    g = grid(8, enumerate(c - 1 for c in (3, 6, 4, 4, 1, 6, 8, 6)))
    
    # count the remaining labels
    c = Counter(g)
    
    # output the grid
    for r in chunk(g, 8):
      print(r)
    print(c)
    
    # the maximum sum uses the the numbers 1 to N by occurrence order
    m = sum(i * n for (i, n) in enumerate(sorted(c.values()), start=1))
    printf("max = {m}")
    

    Solution: (1) The largest total possible for the specified grid is 144.

    Enigma 1248 - Solution 1

    For the second part of the problem we can consider using a program like the following:

    It chooses an assignment of rows to columns that assigns a column to each row but doesn’t assign all the columns, and then uses the grid() routine given above to fill out the grid. The rows and columns are extracted from the grid and we look to see if there are any columns that do not also appear as rows.

    from itertools import count, product
    
    for N in count(1):
      printf("[considering N={N}...]")
      # indices for rows and columns
      ns = tuple(irange(0, N - 1))
      # choose a column for each row
      for ps in product(ns, repeat=N):
        # not all columns can be used
        if len(set(ps)) == N: continue
        # create the grid
        g = tuple(grid(N, zip(ns, ps)))
        # determine the rows and columns
        rs = set(chunk(g, N))
        cs = set(g[i::N] for i in ns)
        if cs.difference(rs):
          printf("N={N} ps={ps} rs={rs} cs={cs}")
    

    This works OK up to N=8 (and doesn’t find any solutions), but as N increases the CPU time used is proportional to NN, so it becomes unwieldy quite quickly.

    The published solution is that it is impossible to find such a grid, so we need to find an analytical proof that shows this is the case.

    We need to show that:

    If every row in a square grid corresponds to a column, then every column corresponds to a row.

    If we have a grid where every column corresponds to a row we can transpose it to get an equivalent grid with every row corresponding to a column.

    I think I have the outline of an inductive proof, like this:

    When n=1 the statement is trivially true.

    So suppose it is true for grids of size n×n.

    Consider a grid of size (n+1)×(n+1). If each column corresponds to a row apart from column X then we can consider the n×n grid formed by ignoring column X and row X. In this n×n grid, each column still corresponds to a row, and hence each row corresponds to a column.

    (It is sufficient to consider a single “rogue” column, because if there is more than column that does not correspond to a row, we can simple delete one of these columns and the corresponding row to get an n×n grid where every row corresponds to some column, and hence every column also corresponds to some row).

    Now if we go back to the (n+1)×(n+1) grid then row X corresponds to one of the columns in the (n+1)×(n+1) grid that isn’t column X, say column Y, and column Y in the n×n grid corresponds to a row, say row Z.

    What we need to show now is that column X in the (n+1)×(n+1) grid is the same as column Z [*]. It then follows that column X corresponds to one of the rows in the (n+1)×(n+1) grid (the same row that column Z corresponds to). This is a contradiction of the starting condition, so no such grid of size (n+1)×(n+1) exists.

    Then by induction, we can see that, no such grid of any size exists.

    The bit marked [*] is the tricky bit. In the specific cases I’ve tried it is always true, but showing it in the general case seems to be quite complicated. If you construct the collections of grid squares that correspond to the same symbol (by chasing the relations between rows and columns) it demonstrates the fact, but I’ve not come up with a neat way to show it in the general case. If someone has a way to prove this (or a neater way to do the overall proof), please let me know.

    Solution: (2) It is not possible to find such a grid.

    • Jim Randell 15 April 2015 at 11:48 am

      Thanks to Gerry Myerson for providing an outline proof for the second part of this problem on math.stackexchange.com.

      Here’s my fleshed out proof…

      Consider an n×n grid, where every row is the same as some column.

      If all the rows are distinct then there are n different patterns, each of which maps to a single row and a single column, hence every column corresponds to some row.

      So, consider the case where there are two different rows that correspond to the same pattern. Say row i and row j.

      Now consider any row r, there is a corresponding column c, and we know row i is the same as row j.

      So in column c, element i and element j are the same. But column c is the same as row r, so element i and element j in row r are the same. This means that for every row r, the element i and element j are the same. So columns i and j are the same.

      So we have shown that if rows i and j are the same, then columns i and j are also the same.

      Now if we consider the collections of distinct rows in the grid we get a pattern like – in the solution grid given above – (A, B, A, A, A, B, B, B), and so now we know that the pattern of the columns must correspond to this, so in the example it would be (X, Y, X, X, X, Y, Y, Y). If there are k distinct patterns in the rows, then, given the correspondence of the columns to the rows there are at most k distinct patterns in the columns. But each pattern in the rows must be represented in the columns so there are at least k distinct patterns in the columns. Hence there are exactly k distinct patterns in the columns, and those patterns are the same as the distinct patterns in the rows.

      We have shown that the set of patterns used in the rows is identical to the set of patterns used in the columns. So there cannot be a column that does not correspond to any row.

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: