# 383 pickover/pickover.07.p

Title: Cliff Puzzle 7: 3x3 Recursion
From: cliff@watson.ibm.com

If you respond to this puzzle, if possible please send me your name,
you provide unique information. PLEASE ALSO directly mail me a copy of
your response in addition to any responding you do in the newsgroup. I
will assume it is OK to describe your answer in any article or
publication I may write in the future, with attribution to you, unless
you state otherwise. Thanks, Cliff Pickover

* * *

Consider the 3x3 array below. All nine digits are used exactly once.

```1 9 2
3 8 4
5 7 6
```

Notice that "384" is twice the number in the first row, and that
"576" is three times the number in the first row.

Questions:
1. Are there other ways of arranging the number to produce the same
result using each digit only once and the same rules?
Remember, the second row must be twice the first. The third row
must be 3 times the first row.

2. Start with the number in the last row (e.g "576" or any other
solution you may find) and continue to form another 3x3 matrix using the
same rules with the new starting number. In other words, the number in
the second row must be twice the first. The third row must be three
times the first. (For this problem you may truncate any digits in the
beginning. For example, 1384 would become 384.)

Keep going. How many matrices can you create before it is impossible
to continue. Again, each digit must be used only once
in each matrix.

pickover/pickover.07.s

-------------------------

```> Title: Cliff Puzzle 7: 3x3 Recursion
> Consider the 3x3 array below.  All nine digits are used exactly once.
> 1 9 2
> 3 8 4
> 5 7 6
> Questions:
> 1.  Are there other ways of arranging the numbers to produce the same
> result using each digit only once and the same rules?
```

YES .

``` 2 1 9       2 7 3        3 2 7
4 3 8       5 4 6        6 5 4
6 5 7       8 1 9        9 8 1
```

> same rules with the new starting number. In other words,
> the last number becomes the first, and the number in
> the new second row must be twice the first. The third row must be three
> times the first. (For this problem you may truncate any digits in the
> beginning. For example, 1384 would become 384.)
NONE. There is no solution to the continuation problem.

Bye.

Amit Agarwal
> to continue? Again, each digit must be used only once
> in each matrix.
>
>

-------------------------

By exhaustive search I found that there are only four such arrays.
Here they are:

```  1 9 2        2 1 9        2 7 3        3 2 7
3 8 4        4 3 8        5 4 6        6 5 4
5 7 6        6 5 7        8 1 9        9 8 1
```

Since these are the only four it is clear from inspection that
none of the last numbers ever begin another array with the desired
properties.

Bob Murphy (rmurphy@aludra.usc.edu)

-------------------------

Well, I think I have an answer to both parts. I did what should have been
a complete analysis of all possible column combinations, but it is
certainly possible that I missed a point somewhere. If you don't get any
answers contradicting this one, I'd be happy to send you my analysis.
Anyway - for part 1, I found the following three matrices (in additionn
to the one you gave):

```			2 1 9    2 7 3   3 2 7
4 3 8    5 4 6   6 5 4
6 5 7    8 1 9   9 8 1
```

Note that the first one of these can be generated from yours by moving
the third column to the first position, and the third one can be generated
from the second similarly. In both cases, one column does not receive
or produce any carryovers, so it can be placed at either end.

For part 2, there is obviously no solution, assuming that these are indeed
the only four matrices satisfying the requirements. In my analysis, I
included columns with carryovers in all positions, so if there were any
matrices that would satisfy the relaxed condition of part 2 I should
have found them.

Dan Blum
Institute for the
Learning Sciences
Northwestern U.
blum@ils.nwu.edu
-------------------------

Cliff,

In article <1blrk9INN10s@aludra.usc.edu> (Bob Murphy) writes:

>By exhaustive search I found that there are only 4 starting numbers
>which produce a 3x3 array with the desired property. Here they are:
>

```>   1 9 2        2 1 9        2 7 3        3 2 7
>   3 8 4        4 3 8        5 4 6        6 5 4
>   5 7 6        6 5 7        8 1 9        9 8 1
```

For each of these solutions I happened to notice that the sum of each row
is a constant:

```	sum(row1) = 12
sum(row2) = 15
sum(row3) = 18
```

(necessary but not sufficient condition)

And the sums all differ by the same constant (3). I wonder if this
property may somehow be generalized to matrices of higher degree?

Regards,

-- Greg Schmidt schmidtg@iccgcc.decnet.ab.com

-------------------------

> affiliation, and e-mail address so I can credit you in the future if needed.
> If you like, tell me a little bit about yourself so I can cite you
> appropriately if you provide unique information. PLEASE ALSO directly mail
> me a copy of your response in addition to any responding you do in the
> newsgroup. I will assume it is OK to describe your answer in any article or
> publication I may write in the future, with attribution to you, unless you
> state otherwise.
> Thanks, Cliff Pickover
>
> Consider the 3x3 array below. All nine digits are used exactly once.
>

```> 1 9 2
> 3 8 4
> 5 7 6
```

>
> Notice that "384" is twice the number in the first row, and that
> "576" is three times the number in the first row.
>
> Questions:
> 1. Are there other ways of arranging the numbers to produce the same
> result using each digit only once and the same rules?
> Remember, the second row must be twice the first. The third row
> must be 3 times the first row.
>
> 2. Start with the number in the last row (e.g "576" or any other
> solution you may find) and continue to form another 3x3 matrix using the
> same rules with the new starting number. In other words,
> the last number becomes the first, and the number in
> the new second row must be twice the first. The third row must be three
> times the first. (For this problem you may truncate any digits in the
> beginning. For example, 1384 would become 384.)
>
> Keep going. How many matrices can you create before it is impossible
> to continue? Again, each digit must be used only once
> in each matrix.

Well, this is probably not news to you by now, but I only get four solutions
to the original problem:

```1 9 2      2 1 9      2 7 3      3 2 7
3 8 4      4 3 8      5 4 6      6 5 4
5 7 6      6 5 7      8 1 9      9 8 1
```

If we relax the rules slightly and allow zeroes, and just specify that the nine
numbers only have to be different, then we get two more solutions:

```0 7 8      2 6 7
1 5 6      5 3 4
2 3 4      8 0 1
```

both of which use the digits 0-8, which may be of interest.

The second problem (in either form) has only the above solutions, with only one
matrix in each solution.

If we switch to base 9 (where we must use a zero), there is no solution to the
first, and only one solution to the second (with only one matrix):

```4 8 1
0 7 2
5 6 3
```

In fact, I considered 3 versions of problem 2. In all cases zeroes were
allowed, but the 9 numbers had to be different. For each of them the first 3x3
matrix has to meet the original specifications; where they differ is in how the
succeeding matrices are constructed. In the ensuing discussion, the original
number is called 'n'. So in the example given with the problem, n is 192.

Version A: The second matrix consists of rows with n*2, n*3 and n*4 in them.
(The last three digits of those, anyway.) The next would have n*3,
n*4, and n*5, then n*4, n*5, n*6, etc.

Version B: The second matrix consists of n*3, n*6, n*9. (This is essentially
the second problem as given.)

Version C: The second matrix consists of n*4, n*5, n*6. The next would have
n*7, n*8, n*9 etc.

Results for various bases:

```Base 9:
A, B, C:   4 8 1
0 7 2
5 6 3

Base 10:
A, B, C:   0 7 8    1 9 2    2 1 9    2 6 7    2 7 3    3 2 7
1 5 6    3 8 4    4 3 8    5 3 4    5 4 6    6 5 4
2 3 4    5 7 6    6 5 7    8 0 1    8 1 9    9 8 1

In addition, with version C, we get a second matrix for 219.

2 1 9     8 7 6
4 3 8 ==> 0 9 5
6 5 7     3 1 4

Base 11:   (A, B, etc. represent 10, 11, etc..)
A, B, C: 18 solutions.  From now on, I'll only show the multiple matrix ones.

A:  5 A 1     0 9 2    6 7 4     2 3 8
0 9 2 ==> 6 8 3    2 3 8 ==> 9 0 1
6 8 3     1 7 4    9 0 1     4 7 5

B:  9 3 4     5 A 1
7 6 8 ==> 0 9 2
5 A 1     6 8 3

C:  8 9 1     2 3 4
6 7 2 ==> 0 1 5
4 5 3     8 A 6

(Note that the B solution ends in an A solution matrix!)

Base 12:   19 solutions

A:  7 3 4     2 6 8
2 6 8 ==> 9 A 0
9 A 0     5 1 4

B:  None

C:  3 5 7     1 A 4
6 B 2 ==> 5 3 B
A 4 9     8 9 6
```

Base 13: 71 solutions...and it rapidly increases from here....

The number of solutions rises rapidly, as we might expect, as the more possible
values for digits there are in the base, the more likely the set of 9 will be
distinct. If we look at solutions which only involve the digits 1-9, then the
following is a list of all solutions (for all bases):

```Base 10:  1 9 2    2 1 9    2 7 3    3 2 7
3 8 4    4 3 8    5 4 6    6 5 4
5 7 6    6 5 7    8 1 9    9 8 1

Base 11:  7 8 3    8 4 6    8 9 1
4 5 6    5 9 1    6 7 2
1 2 9    3 2 7    4 5 3
```

(Tested all cases until base 17. After that, no solution can involve a carry.
But there are no solutions without carries. So, no more solutions.)

I hope this is of some interest.

Cheers,
Geoff.

```-------------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm)   |   Programmer by trade --
ftww@cs.su.oz.au                      |       Gameplayer by vocation.
-------------------------------------------------------------------------------
```

-------------------------

> Ref: Your note of Mon, 19 Oct 92 22:24:47 EST
>
> Where are you from?

Whoops, knew I forgot to put something in. I'm currently a student at the
University of Sydney (Australia), doing Computer Science (Honours).

Cheers,
Geoff.

```-------------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm)   |   Programmer by trade --
ftww@cs.su.oz.au                      |       Gameplayer by vocation.
-------------------------------------------------------------------------------
```

-------------------------

By the way, I tried searching for analogous solutions for other sizes and other
bases. So the new problems become:

Consider an n by n matrix containing the 'digits' from 1 to n^2 in a base b,
where b > n^2. The i'th row of the matrix consists of the last n 'digits' of
i*(first row). The versions differ in how succeeding matrices may be
constructed. Let f be the first row.

Version A: The next matrix has rows with 2*f, 3*f, ... , (n+1)*f
The j'th matrix has rows j*f, (j+1)*f, ... , (n+1-j)*f

Version B: The next matrix has rows with n*f, 2*n*f, ... , n*n*f
The j'th matrix has rows (n^(j-1))*f, 2*(n^(j-1))*f, .... , (n^j)*f

Version C: The next matrix has rows with (n+1)*f, (n+2)*f, ... , 2*n*f
The j'th matrix has rows (1+n*(j-1))*f, (2+n*(j-1))*f, ..., j*n*f

Basically these are analogies of the three versions I wrote to you about
before. The results I get are:

```n: 1    base: any above 1

A, B, C:     1

n: 2    base: 5

A, B, C:      3  2             4  1
1  4             3  2

In case B, the second one extends:

4  1 ==> 3  2
3  2     1  4

In case C, the second one also extends:

4  1 ==> 2  3
3  2     1  4

base: 6

A, B, C:      1  4             3  4
3  2             1  2

Note that the only solution to the first problem (no overflow allowed) is
1  4     (in base 6)
3  2

n: 3    base: 10

A, B, C:  1  9  2     2  1  9     2  7  3     3  2  7
3  8  4     4  3  8     5  4  6     6  5  4
5  7  6     6  5  7     8  1  9     9  8  1

base: 11

A, B, C:  7  8  3     8  4  6     8  9  1
4  5  6     5  9  1     6  7  2
1  2  9     3  2  7     4  5  3

Note the base 10 solutions all solve the first problem, while none of the
base 11 solutions do, and there is no second matrix for any of them.

n: 4    base: 18

A, B, C:  1 15 14  4    1 15 16  2    2  1 15 16    2  3 13 16
3 13 10  8    3 13 14  4    4  3 13 14    4  7  9 14
5 11  6 12    5 11 12  6    6  5 11 12    6 11  5 12
7  9  2 16    7  9 10  8    8  7  9 10    8 15  1 10

3 13 14  4    3 13 16  2    4  1 15 14    4  3 13 14
7  9 10  8    7  9 14  4    8  3 13 10    8  7  9 10
11  5  6 12   11  5 12  6   12  5 11  6   12 11  5  6
15  1  2 16   15  1 10  8   16  7  9  2   16 15  1  2

In case C, two of them extend:

1 15 16  2      9  7  8 10      2  1 15 16     10  9  7  8
3 13 14  4 ==> 11  5  6 12      4  3 13 14 ==> 12 11  5  6
5 11 12  6     13  3  4 14      6  5 11 12     14 13  3  4
7  9 10  8     15  1  2 16      8  7  9 10     16 15  1  2
```

Note all of these solutions solve the first problem (no overflow).

Unfortunately, my algorithm is O((n!)^2), so any results for n = 5 are not
going to be forthcoming soon.

Cheers,
Geoff.

```-------------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm)   |   Programmer by trade --
ftww@cs.su.oz.au                      |       Gameplayer by vocation.
-------------------------------------------------------------------------------
```

Continue to: