Rather unlike the case of the four collumn problem it would
appear as though all cases reduce to a series of recurring rows
that is we never get a row of all zeros. Certainly different cases
take a different number of rows before they begin recurring but
they all seem to do so.
This raises some interesting questions for further investigation:
-- Is the assumption that the recurring patterns always arises
correct?
-- What is the largest number of rows before the pattern begins
recurring?
-- Will we get recurring patterns again if we extend the problem
to five collumns?
-- Is there any way of predicting what numbers we can expect in
the recurring sequence?
Based on a few examples and some preliminary exploration of these
questions I was tempted (for a short time only!) to explore the
matter algebraically for four collumns.
Let the entry in collumn 1 be 0, in collumn 2 be a, in collumn
3 be b and in collumn 4 be d with the condition that a > b
> c (the zero, at this stage, is simply for ease of working).
It is then possible to work out a number of rows in terms of a,
b and c!
Clearly this becomes quite messy quite quickly and I decided to try another tack.
Having been let down by Polya I decided to try another approach
that of wishful thinking. We can start with the last row and try
to build up the table from the bottom.
From observing a number of examples in Step 1 we know that the
last row of non-zero numbers will all be identical. I first tried
to see in how many different ways a pattern can end:
Using this as a basis I then tried to build a table by starting
with the last few rows. The process goes as follows:
* Place any entry in the first collums in the row above the top
row with digits.
* This determines at most two possibilities for the entry in the
second collumn.
* For each possible entry in the second collumn there are at most
two possible entries in the third collumn.
* The entry in the first collumn also determines at most two possible
entries in the last collumn.
* After listing all these possibilities look for agreement between
the possibilities in the third and fourth collumns. If you have
been successful fill in the next row.
The reader is encouraged to try a few rows in this manner you will find that the pretty picture provided is missleading in that you will find the process to be rather tedious.
Having enjoyed no significant progress by the methods described
I decided to return to Step 1 and enter some arbitrary numbers
and then to try and improve on these. In the process I observed
some interesting ideas and developed an algorithm for the method.
The algorithm is described below:
* Place a 0 in collumn 1,
* Place any number in the next three collumns either in ascending
or desceding order, let the numbers be in a rough ratio of say
1 : 2 or 3 : 6,
* Now manipulate the numbers as follows to try and get more rows
in the pattern:
-- start with any entry in the first row (not the zero) and increase it watching what happens to the last row of non-zero entries.
EITHER the values in the last row will increase in which case continue increasing the value of the entry you are working with,
OR the values in the last row will decrease in which case decrease the value of the entry you are working with,
OR you will get more rows in your pattern in which case you should rejoice and continue doing what you are doing,
OR you will loose rows in which case UNDO the damage.-- continue with the entry you started with until you have as many rows as possible and as large an entry in the last row as possible.
-- continue in this manner visiting (and revisiting) all the entries in the first row until you cannot increase the value of the last row's entries or generate more rows!
Using this algorithm I was able to generate the following table:
At this stage I am still unable to notice (despite following
many hunches) a relationship between numbers in the first row
that will generate a large number of rows.
The reader is invited to try this algorithm and suggest improvements.
Having laboured over this approach I decided to have the computer
do some of the initial work for me.
I wrote a short Macro for Excell that works as follows:
(i) place a zero in the first collumn.
(ii) rather than placing a number in collumns 2, 3 or 4 enter
the following formula:
= round(rand()*1000,0)
this formula will place a number between 0 and 999 in the cell.
(iii) enter the formulas for the rest of the table as per the
instructions in the task.
The Macro, once activated, will cause new numbers to be entered
in the first row and will then work out the entries in the other
rows. I set it to stop once it had generated a set of numbers
that yielded non-zero entries in the tenth row.
In less than ten minutes the computer generated some 25 sets of
starting numbers that will yield ten or more rows. Using the alogrithm
described above I was able to "improve" the computer's
list as shown below:
This table is provided as much to illustrate that some of my
initial hunches (eg regarding ratio) seem to have errors in them
as it is provided so that the interested reader may use these
number to generate their own rows and seek the relationship between
the initial numbers that leads to a large number of rows of entries
- a relationship that still evades me!
For the interested reader you can click
here and access the Excel spreadsheet that generates the rows
as decribed.
If the computer is capable of doing a random generation then
surely it can also test ALL the cases from starting condition
(0, 0, 0, 0) to (999, 999, 999, 999)!
This is quite possible though a little time consuming. Intrigued
by the idea I have writen yet another Macro and have set it to
work - that is I have asked it to test all these cases and stop
only once it has found one that yields 19 rows (18 being our best
so far)! On a single computer I estimate that some 4000 hours
are needed to test all the cases with my (seemingly eternal) loop.
Fortunately I am working in a computer room with a number of computers
and I have shared the task between 10 (400 hours each - many many
days!) - clearly I am not expecting an answer before my colleagues
kick me off the other machines, BUT ever hopeful I may get one
case in time......... (watch this space).
After a number of days with ten computer running simultaneously
the computers have found one combination of starting numbers (0,
964, 440, 155) that will yield 19 rows.
An enjoyable exercise - this investigation has NOT yielded
any answers (YET!) and has indeed raised many more questions for
exploration - I would rank it a good problem and a valuable investigation.
There are some critics of this kind of learning who would argue
that little has been achieved and that we should have done more
"mathematics" to solve the problem, or that we should
not have set a problem that would not yield a solution. How do
you feel?
Two final thoughts for the reader:
-- How would you have set about the problem?
-- What has been learnt by the approach used?