GENERAL DISCUSSION

Working on these problems under observation was an extremely challenging situation for all of these students. During class they were used to working together, first as an entire class getting oriented to the problems, sharing ideas about the meaning of the hypotheses and clarifying the task in the problem, and then in a small group exchanging ideas about how to solve the problem, formulating a plan and trying to execute the plan. Students did work independently on problems which they submitted as individuals but in those instances they were neither being observed nor were they subject to a time constraint. Thus, this was a very different environment for problem solving than they were accustomed to.

 

DISCUSSION OF PROBLEM I:

This problem was choosen because it potentially can involve several different techniques and heuristics. Since it is required to show that two of the numbers must be equal this suggests that it might be amenable to an attack using the pigeonhole principle. With this in mind one can then formuate some subgoals and also attempt to work backwards. One subgoal is to show that at most 99 diffferent numbers are used to fill in the 100 cells of the table. This would be a penultimate step and lead directly, through an applcation of the pigeonhole principle to the desired result. In turn, if one could show that the range of values - the difference of the largest and smallest - is at most 98 then it would follow that there are at most 99 different values and, as stated, we would be done. This suggests investigating how much any two entries can differ by and now the hypothesis, that two neighbors (squares with a common edge) differ by at most 5 comes into play. Label the squares (k,l) where k and l can take any of the values 1, 2, . . . , 10. The distance between two squares (a,b) and (c,d) is then the total number of horizontal and vertical moves one has to make to move from one to the other. In turn this is

| a - c | + | b - d |.

Since adjacent squares differ by at most 5, each horizontal and vertical move results in a difference of at most 5 and therefore the entries in (a,b) and (c,d) differ by at most

5( | a - c | + | b - d | ).

Since both | a - c | and | b - d | are at most 9 this means that the difference between any two squares is at most 5 x 18 = 90. Since this applies to any two squares, in particular, it applies to the squares with the smallest and largest entries and consequently the range is at most 90. This last step, making use of the existence of a smallest and largest value, is an application of the extremal priniciple. Thus, this solution to the problem makes use of both the pigeonhole and extremal priniciples, involves formulating subgoals, working backwards, as well as ideas from geometry (distance, in this case what is known as" taxicab distance") and graph theory.

STUDENT PERFORMANCE ON PROBLEM I

Nearly every student began the same way - they drew a table in order to have a visual reference and in order to better understand the task. Some students then, without much talking or thinking about the problem would begin to fill in numbers, typically startiing in a corner with 1 and putting numbers around it which were within the required range. It was not clear whether these students were trying to actually fill in the table with entirely different integers, contrary to what is asked, or trying to get some insight into why it is not possible.While it did appear tha some of these students were approaching it indirectlya nd trying to do a proof by contradiction, in several instances the students would put the same entry into two different squares all the while continuing to fill in the table and this suggests that there were moments when working on the problem when they lost sight of what was beiing asked.

Altogether, these students,usually did not get very far and when stuck they would draw another table, usually smaller (changing the 10 x 10 to 2 x 2 or 3 x 3 and even 4 x 4) and try to formulate the same problem for a more manageable table. In doing so they were appealing to a well grounded heuristic - try a simpler problem. This particular heuristic is has limited value since one is constrained by the values that can replace 5 since once the table is 3 x 3 or larger there are squares with four neighbors and if one is trying to get insight by this approach then it not served by making the problem completely trivial. Therefore, it makes sense to use 4 instead of 5 but nothing smaller. On the other hand, by using a smaller table there are fewer cells and that might make it more difficult to get two to have the same value. None of the students who approached the problem this way make substantial progress.

Five students made some progress towards a solution. These students did lots of talking during the process, testing their ideas verbally on themselves. Like the others they all drew tables in order to have a visual reference. Like their peers they tried to fill in cells but by their discussion this was clearly inteneded to try to get insight into why eventually two numbers must be the same. Quite early in these students analysis they honed in on the pigeonhole principle as a possible method of solution since this was the most common method used during the course to show two things were equal.

One student made only slight progress. This student focused on the interior squares (not on an edge of the table) all of which had four neighbors. This student also had the wherewithal to think about the smallest value on the board (taking it to be 1, which is permissable since nothing is changed in the problem if the same numbers is added or subtracted from every entry but this did not appear to be what the student was thinking, rather he/she simply assumed that the least number was 1. Also, the student made the assumption that this number was in an interior position, perhaps because this is the most challenging situation to putting down distinct entries in each cell: there are only 5 numbers within the smallest number, whereas a number in the middle of the range might have 10 numbers within 5 of it. This student also came upon the idea that the pigeonhole principle might be used but never was able to define the "pigeon" or the 'pigeonholes".

Another student, after attempting to fill in the cells and doing some investigation of the obstacle to putting distinct entries in the 100 squares came the conclusion that either the result is true or else diagonally adjacent elements (sharing a vertex but not an edge) differ by at most 9. At this point the student began to think about the use of the pigeonhole principle but could not figure out what were the pigeonholes. At this point the student attempted to gain insight by simplifying the problem by making it smaller and fell into the same trap as the aforementioned students.

Another student came upon the idea of using the pigeonhole principle and also came to the conclusion that two squares in the same row (column) had entries which differed by at most 45 but was not able to get any closer to a solution than this.

One student got close to a solution but did not realize how close. At the very outset this student concluded that the difference of any two in a row was at most plus or minus 45 and likewise for a column and then also concluded that the greatest difference possible would be from one corner to an opposite corner and be at most plus or minus 90. This student also thought about moving horizontally and vertically from one cell to another. The student then wanted to show that there were less than 100 numbers used in all so that he/she could apply the pigeonhole principle but was tripped up because the difference could be -90 or +90.

In one instance a student got the essentials of a solution quite quickly after articulating the likelihood of an attack by the pigeonhole principle. From here, this student began to think about the spread of the integers, first concluding that it could be as much as 496 since there were 100 integers, hypothesiziing them to be distinct multiples of 5. Quickly however this student began to think about how much two could differ if they were in the same row or the same column, concluding in both cases, that a maximum difference of 45 was possible. From there the student concluded that the maximum difference of any two would be at most 90 and then said the result follows from this (which is true but requires a bit more rigor). This was the very best performance.

DISCUSSION OF PROBLEM II

This problem was also choosen for the heurisitcs that might be demonstrated in approaching a solution as well as the use of content from elementary number theory and an application of the extremal method and the efficacy of doing an investigation. My first thought was that students would look for solutions by systematically plugging in numbers for a,b,c,d and after not to many tries either find no solution or the trivial solution a = b = c = d = 0. I expected that once they articulated the idea that there is no (non-trivial) solution they would do a little more searching and then try to prove that there are no (non-trivial) solutions. In the course of investigating one is led to the fact that the right hand side is divisible by 3 and so the left hand side must be divisible by 3 leading to the auxilary question: when is the sum of two square integers divisible by 3. This is a good subgoal and can be investigated by itself. At this point, one can make use of ideas from elementary number theory and either introduce the use of congruence or else deal with the problem more concretely and investigate the question for the various cases of the remainder of a and b when divided by 3. This should lead to the conclusion that 3 divides both a and b. If one then writes a = 3e', b = 3f one then gets the equation

9(e^2 + f^2) = 3(c^2 + d^2)

and then dividing by 3 gives the equation

3(e^2 + f^2) = c^2 + d^2

which is essentially the same equation as the first only with different letters representing the variables. By the same logic one can then conclude that 3 divides c and d and make the substitutions, the division by 3, etc. This would then go on for ever, which is impossible and thus we can conclude by what early number theorists called the method of infinite descent that there is no non-trivial solution. Alternatively, once one makes the conjecture that there is no non-trivial solution one can approach the problem by contradiction: Assume that there is a solution and use the extremal principle - take one satisfying some minimal condition, i.e. | abcd | is as small as possible. Then as above one would get a new solution, (c,d,e,f), with

| cdef | < | abcd |. Yet another alternative is to assume a solution in which a,b,c,d have no common factor since any common factor can be divided out to get a solution (and so is a property of a minimal solution) but then we get a contradiction since we show that each is divisible by 3.

STUDENT PERFORMANCE ON PROBLEM II

Not every student who participated in the problem portion of the interview got to work on this problem because of the time factor. Of the remaining eight students six made some progress on the problem and perhaps three came very close. As hypothesized, nearly all the students began by trying some numbers and quickly lost patience with this when no easy solutions, apart from the trivial solution presented itself. It was also common for the students to rephrase the problem and also to articulate simpler problems, for example, finding solutions to a^2 + b^2 a multiple of 3 in integers. One student did this but never voiced the possibility that there were no non-trivial solutions, rather to the contrary, throughout the effort this student continued to think that some obvious non-trivial solution was being overlooked and was equally convinced that if one solution could be found then there would be some method, similar to the one used for a problem in class to find infinitely many solutions. It appeared that because of the way the problem was phrased - "find all solutions in integers . . . " - this student believed from the very beginning that there must be solutions to the equation and was never moved from that belief despite the accumulating evidence.

One student did not approach the problem by trying numbers but tried to manipulate the expression, subtracting a term from one side and then taking a square root, in the hope of somehow parameterizing one of the variables in terms of the others. Absolutely no progress was made nor did this student vocalize the correct conjecture - that non non-trivial solutions exist.

Three students approached the problem nearly identically: They began with an investigation and did not find obvious solutions. At that point they went back to the equation and focused on the simpler but related question of when a sum of squares is divisible by 3. After more computations these students all conjectured that both a and b must be multiples of 3 but neither gave a completely rigorous proof nor got any further than this.

Three studenst made substantial progress on the problem. As in the other cases, these students did some investigating and also fixed on the simpler problem of finding solutions to

a^2 + b^2 a multiple of 3.

Everyone of these students expressed this in the language of congruences drawing on a knowledge of elementary number theory. By considering the different possible congruences for a and b all three students concluded that both a and b are divisible by 3. This was as far as one student could take the problem though it was conjectured that the only solution is the trivial one. The other two students thought to substitute expressions of a and b as multiples of 3 into the equation and then to observe that after dividing by 3 essentially the same equation as the original equation arises except now with c and d in the role of a and b. Both students concluded from this that also c and d are divisible by 3. One of these students then thought about the consequence of dividing a solution by 3 to get another solution which would also be divisible by 3. This was disturbing to the student for an unarticulated reason. This is definitely a near solution and probably with more time to reflect this student would have completed it with a rigorous proof. The other student similarly concluded that 3 divides c and d and conjectured that the (0,0,0,0) is the only solution but did not think to divide a solution by 3 to get another solution. This student also ran out of time but was confident that with more time the problem could be finished from this information.