### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,114)
- misc (2)
- project euler (2)
- puzzle (29)
- site news (43)
- tantalizer (29)
- teaser (3)

### Site Stats

- 166,224 hits

Programming Enigma Puzzles

16 March 2015

Posted by on **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

Nis 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×nchessboard, 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 smallestnfor which it is possible?

See also **Enigma 1225**.

[enigma1248]

Advertisements

%d bloggers like this:

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

Solution:(1) The largest total possible for the specified grid is 144.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.This works OK up to

N=8 (and doesn’t find any solutions), but asNincreases the CPU time used is proportional toN, so it becomes unwieldy quite quickly.^{N}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 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 columnXthen we can consider then×ngrid formed by ignoring columnXand rowX. In thisn×ngrid, 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×ngrid 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 rowXcorresponds to one of the columns in the (n+1)×(n+1) grid that isn’t columnX, say columnY, and columnYin then×ngrid corresponds to a row, say rowZ.What we need to show now is that column

Xin the (n+1)×(n+1) grid is the same as columnZ[*]. It then follows that columnXcorresponds to one of the rows in the (n+1)×(n+1) grid (the same row that columnZcorresponds 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.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×ngrid, where every row is the same as some column.If all the rows are distinct then there are

ndifferent 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

iand rowj.Now consider any row

r, there is a corresponding columnc, and we know rowiis the same as rowj.So in column

c, elementiand elementjare the same. But columncis the same as rowr, so elementiand elementjin rowrare the same. This means that for every rowr, the elementiand elementjare the same. So columnsiandjare the same.So we have shown that if rows

iandjare the same, then columnsiandjare 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

kdistinct patterns in the rows, then, given the correspondence of the columns to the rows there are at mostkdistinct patterns in the columns. But each pattern in the rows must be represented in the columns so there are at leastkdistinct patterns in the columns. Hence there are exactlykdistinct 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.