write up 5

Write-up 5
Assignment 12 Problem 7

Introduction

I have approached this problem (as I did in write-up 1) with the objective of attempting to simulate what I expect students in a classroom may do. I have done this to try and answer (at least for myself) the question of how feasible it is to teach through open-ended problems and implications that such an approach may have for the problems you choose.

In reading this the reader may find a very elegant solution to the problem by noticing some ommisions or oversights on the part of the author. I make no apology for this -- rather than presenting a beautiful solution I have chosen to reflect on the struggle so that the reader who does not "see" a solution straight away will explore with me some approaches.

Step 1 - Arbitrary choices of starting numbers.

After setting up the spreadsheet to perform the algorithm described in the task I entered a range of numbers in the starting positions and tried, in vain, to find some combination of starting numbers that will yield a large number of rows. At this stage I could not detect any pattern and decided to approach the problem in a more sytematic manner.

Step 2 - Seeking a simpler problem.

Invoking Polya I decided to seek a simpler problem first from which I might extract some guidance in our problem.

(i) Consider a single collumn - this is clearly a silly case.

(ii) Consider the problem with only two collumns - again this is a silly case as the rows will all go to zero after at most two rows.

(iii) Consider the problem with three collumns - this proved interesting:

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.

Step 3 - Building the collumns from the bottom.

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.

Step 4 - Return to guesses.

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.

Step 5 - Let the computer do the work.

Having laboured over this approach I decided to have the computer do some of the initial work for me.

Attempt 1.

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.

Attempt 2

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.

Conclusion

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?

Return to Aarnouts' EMT668 page