AUTHOR:Jinfa Cai; John C. Moyer; Connie Laughlin
TITLE:Algorithms for Solving Nonroutine Mathematical Problems
SOURCE:Yearbook (National Council of Teachers of Mathemat 1998 218-29 '98

The magazine publisher is the copyright holder of this article and it is reproduced with permission. Further reproduction of this article in violation of the copyright is prohibited.
MATHEMATICAL algorithms are powerful tools that contribute to effective problem solving and are rules that guarantee a solution when correctly applied. However, there is a great deal of empirical evidence that although some students appear to know an algorithm, they cannot correctly apply the algorithm to solve a problem. Understanding an algorithm conceptually implies knowing the procedures specified by the algorithm and knowing when and how the procedures should be applied. The question is, How can teachers create learning environments so that students can understand where and when to use the algorithms? About a half-century ago, Piaget had already indicated that "to understand is to discover, or reconstruct by rediscovery, and such conditions must be complied with if in the future individuals are to be formed who are capable of production and creativity and not simply repetition" (Piaget 1973, p. 20). Today, the idea that students should be allowed to invent their own algorithms is still valued (National Council of Teachers of Mathematics NCTM 1989, 1991). "Mathematics is learned when learners engage in their own invention and impose their own sense of investigation and structure" (NCTM 1991, p. 144). Thus, in order to know when and how to apply algorithms correctly in problem solving, students should be provided opportunities to develop and invent their own algorithms.
In this paper, we share with readers examples in which students were given situations and guided to invent their own procedures and algorithms. Students actively participated in processes of knowledge construction and made sense of mathematical procedures and algorithms. They became active participants in creating knowledge rather than passive receivers of rules and procedures. The lesson plans were designed to allow the students to invent their own algorithms in solving nonroutine problems. The two examples presented here involve middle school students' inventing algorithms through inductive reasoning and generalization. The concepts and skills involved in these two examples are very important for the development of their algebraic thinking.

ALGORITHMS FOR FINDING THE SUM OF AN ARITHMETIC SERIES
As students move into the middle grades, the development of algebraic reasoning becomes more and more important. Students should be given many problems that allow them to study patterns and look for ways to generalize results. Eventually, these generalizations are expressed in closed algebraic forms using variables. One such problem that was posed to a group of sixth-grade students is the Staircase problem, shown in figure 26.1. The students were asked to find their answers in as many different ways as they could. Findings from cross-national studies show that teachers in Japan and China experienced success with this teaching strategy.
The students worked on this problem in pairs. After twenty minutes, each pair had at least one way to determine the number of blocks needed to build a staircase of nine steps. Then each pair was asked to present its solutions. The initial strategies were dependent on the specific cases and unsophisicated. Most students focused on drawing all nine stair steps and then counting. Some students said that in order to find the total number of blocks needed to build a staircase of nine steps, they just found the sum of 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9. If the numbers are added in their original order, the result will be the total number of blocks. Many groups recognized that to find the total number of blocks needed in a staircase, they could just add the number of blocks in the new step to the previous total number of blocks. Of course, this method requires them to know the previous sum, so the students did not have an efficient way to get past this obstacle. Two invented algorithms were presented by two pairs and elaborated through classroom discussions: a pairing algorithm and a geometric algorithm. These two algorithms were developed simultaneously in the classroom, but they are presented separately in this paper.

THE PAIRING ALGORITHM
Frank and Maria looked for ways to add the numbers other than in the original order and soon discovered the idea of pairing numbers to obtain common sums:

1+2+3+4+5+6+7+8+9 = (1+9)+(2+8)+(3+7)+(4+6)+5
= 10+10+10+10+5
= 10◊4+5
= 45

The symmetry of this approach appealed to many pairs, but they did not accept it as a superior solution strategy until the problem was extended to a greater number of stairs.
After all the pairs had presented their solutions, the teacher asked the students, "What if we need to build a staircase of fifty steps, how many blocks do we need?" After a pause, the teacher continued, "We have already discussed several ways to figure out the number of blocks needed to build a staircase of nine steps. What if we used these ways to find out the number of blocks we need to build a staircase of fifty steps?" The earlier algorithms of just counting by ones or adding in order were discarded by many students as too inefficient. Instead, this pairing algorithm became very popular. Jane in particular was very proud to share her solution to this problem with the class. Her work is shown in figure 26.2.
After Jane's presentation, many students were puzzled because Jane's answer was different from their answer. Some other students were puzzled because many of Jane's pairs were not equal to 51. Jane had paired 25 with 27, 24 with 28, and so forth, but the sum of each of these pairs is 52, not 51 as Jane had said. Cognitive conflict leads to many constructive discussions in class. The teacher asked the students to investigate what had happened in Jane's solution. Bill raised his hand and pointed out that when Jane had done the pairing, she had skipped 6. Bill then offered his correct pairing algorithm: "There are 25 pairs of 51. 51 ◊ 25 = 1275. So the correct answer should be 1275." Some students also agreed with Bill that 1275 should be the correct answer.
When Bill correctly paired the numbers, he did not have an unpaired middle number. That seemed to puzzle Jane. She asked, "Where is the middle one, which is not paired with anybody?" Most of the students and the teacher in the class seemed to have difficulty understanding what Jane meant. The teacher asked, "What do you mean, 'the middle number,' Jane?" Jane replied, "Well, if you look at nine steps, you paired the numbers, but the middle number 5 is not paired with anybody." Then the teacher understood what Jane meant. Since with nine steps there is a middle number, 5, that is not paired, Jane appeared to believe that there should also be an unpaired middle number with 50 steps. So the teacher focused the class discussion on the resolution of Jane's question.
* What is the common sum?
* How many pairs do you have? How do you know?
* Is any number unpaired? How do you know?
* What happens when pairing with even numbers of steps and odd numbers of steps?
The discussion ended at the point when the students realized that if they have an even number of steps, they will not have an unpaired middle number and if they have an odd number of steps, they will have an unpaired middle number.

THE GEOMETRIC ALGORITHM
On the first day of exploring this problem, Bob and Tasha suggested drawing a complete 9-by-9 square and then "slicing it in half" to find the number of blocks in the nine-step staircase (see example 1 in fig. 26.3). These two students knew they were on to something but could not fully explain it to the class at the time. When this picture was shared with the whole class, many interesting questions were raised by the other students, for instance, "Was the square really divided in half? Half of 81 is not 45, is it?"
Later, the teacher helped the students in the class see that the square was not actually divided in half by encouraging them to draw a diagonal line on Bob and Tasha's figure. All the students agreed that the diagonal line divided the 9-by-9 square in half but that it cut off some of the staircase. A close examination of the figure shows that the nine-step staircase is more than half of a 9-by-9 square, since there are nine half-squares above the diagonal. The 9-by-9 square has 81 blocks, and half is 40.5. If we add the 9 half-blocks to 40.5, we will get 45, the number of blocks in a nine-step staircase. This classroom discussion helped the students clarify ideas about shape, geometry vocabulary, and division.
Patti also presented her group's solution to the class. Her solution was similar to Bob and Tasha's, but she fit two nine-step staircases together, which formed a rectangle rather than a square. Example 2 in figure 26.3 shows her group's solution. This solution was the catalyst for many students to begin to generalize the problem. If the staircase had ten steps, the rectangle was 10 ◊ 11. Patti explained, "Then you divide the product of 10 ◊ 11 in half because you only want one staircase, not two." If the staircase had fifty steps, the rectangle formed by two staircases was 50 ◊ 51. Several groups used this idea as one solution to a fifty-step staircase. It was interesting to watch them arrive at answers to various sizes of staircases. They used the pairing algorithm and the drawing strategy together with counting ideas to arrive at their answers, and they also began to express a generalization for the problem of adding consecutive integers.
After three days of working on this problem, many groups were able to begin to generalize in words about how to obtain the number of steps in any staircase. The teacher decided to go one step further and encouraged the students to use variables to show the number of blocks in any staircase. A few students wrote the generalization in symbols. When they shared this formula with the rest of the class, the other students listened but could not readily apply it to new staircases. For the most part, the majority of the students fell back on their earlier algorithms for help. They either (1) needed to list a few, if not all, of the numbers in pairs to obtain the sum or (2) needed to draw a rectangle composed of two sets of staircases. Their reliance on their earlier algorithms suggests that their algorithmic thinking about the sum of consecutive numbers or the area of a rectangle is a facilitating step on the road to understanding the formula for the sum of consecutive integers. As these students encounter this same number situation in new problems, they will have at least one or two fairly efficient strategies to obtain the sum. Eventually, most may use the formula, but these intermediate strategies are the key to making sense of the ideas about symbolism.

ALGORITHMS IN THE CROSSING-THE-RIVER PROBLEM
A certain aspect of algorithms can be described by numeric patterns that, in turn, can be modeled with algebraic symbols. In this sense, algebraic reasoning is at the heart of algorithmic processes. The second example shows how algorithms invented by students for solving a problem can also stimulate algebraic thinking. Given an appropriate problem, students can be induced to conceive a strategy for solving the problem, invent an algorithm for applying the strategy, and model the algorithm with algebraic symbols. Teachers who observe their students engaging in problem solving of this type have a golden opportunity to assess their students' level of algebraic thinking.
The problem that we have used with middle school students is Crossing the River, shown in figure 26.4. The students worked in groups of three. Almost all the students found this problem to be enjoyable and interesting. They soon became enthusiastically immersed in the solution process. At first the students did not have a thorough understanding of the problem. In order to understand it, the groups needed to act out various scenarios with manipulative materials. Through trial and error, the students soon understood the crux of the problem and began to invent and formulate a strategy for solving it. At the heart of their strategy was an awareness that when an adult crosses to the far side of the river, there must always be a child waiting there to bring the boat back.

FROM STRATEGY TO PROCEDURE
A realization of the basic strategy alone, however, was not sufficient to solve the problem. The students had to convert this basic strategy into a procedure for getting all eight adults and two children across the river in the minimum number of trips. In time, this procedure led to the invention of a generalized algorithm for solving all problems of this type. It was interesting to observe the students as they grappled to "proceduralize" their strategy (i.e., to develop an algorithm). Many, even after they had conceptualized a correct procedure, had difficulty implementing it without error. For some, colored counters were too abstract. They had to resort to the use of more-realistic materials: a model that looked like a boat, large pieces for adults, and small pieces for children.
After a while, all the groups came up with an answer. Most of the answers were correct: thirty-three trips. Wrong answers were not due to faulty strategies. Rather, wrong answers were due to incorrect counting or incorrect compensation for an error in implementation. Through discussions with the students about their procedures, the teacher realized that many groups were not yet explicitly aware of the repetitive sequence of steps they had used to solve the problem. This meant that even though the students were able to "proceduralize" their strategy for solving the problem, the procedure itself was not yet sufficiently understood at a conscious level. The teacher's goal was for the students to transform their procedure into a generalized concrete algorithm. To do so, the students needed to conceptualize the steps individually as well as in sequence with other steps.

FROM PROCEDURE TO ALGORITHM
To induce the students to make a conscious effort to invent a generalized algorithm, the teacher then asked the students to record their solutions to three different variations of the problem: to find the number of one-way trips it takes for (1) six adults and two children, (2) fifteen adults and two children, and (3) three adults and two children to cross the river. Note that the teacher changed only the number of adults, not the number of children. With the number of children maintained at two, the solution for each situation varies only in length. The teacher told the students to devise their own way of recording their solution and to record it while the pieces were actually manipulated. He told them that one student should describe how a second student is manipulating the pieces while a third student records the information. This requirement not only ensured that all three students were involved in the process, but it also provided tactile, auditory, and written feedback on the repetitive nature of the procedure.
Through this process, the students were led to invent a generalized algorithm that they could use to solve any problem of this type. At the heart of the algorithms invented by the students was a "chunk" of four moves that was repeated for each adult transported to the far side. The groups became aware of the repetition of chunks in different ways. Akeem, Jorge, and Tyra's group became very enamored with the rhythm of the words that Tyra kept repeating for Akeem to write down: "Two kids, one kid, one adult, one kid; two kids, one kid, one adult, one kid; two kids, one kid, one adult, one kid;" and so on. Sam, Rosa, and Tara noticed the chunks by examining the diagrams they had made. So did Ning, DeAnn, and Thomas. The last two groups represented the elements of the pattern in similar ways, but the elements appeared in the chunks in a different order. Examples 1 and 2 in figure 26.5 show the difference between their algorithms.
Sam, Rosa, and Tara noticed chunks that started at the top of their diagram. In their algorithm, a chunk is composed of the first four crossings: two children cross to the far side, one child crosses back to the near side, one adult crosses to the far side, one child crosses back to the near side. One chunk must be performed for each adult who crosses the river. These chunks are repeated until only two children are left on the near side. Finally, one extra trip is required to complete the solution.
Ning, DeAnn, and Thomas noticed chunks that occurred at the bottom of their diagram. In their algorithm, the last four crossings constitute a chunk that had been repeated throughout their solution: one child crosses back to the near side, one adult crosses to the far side, one child crosses back to the near side, two children cross to the far side. Ning, DeAnn, and Thomas's algorithm requires a single trip at the beginning before the repetitive chunking begins: two children must cross to the far side, then one chunk is performed for each adult who crosses the river.
Joe, Enrique, and Cybill decided to draw arrows of different colors to represent different combinations of people crossing theriver. In their algorithm, a red arrow represents two children crossing, a green arrow represents a single child, and a blue arrow represents a single adult. This group identified the chunks through the repetition of the colors: red, green, blue, green; red, green, blue, green; red, green, blue, green; red, green, blue, green; and so on.
Terry, Glenn, and Roberta conceptualized the chunks as cyclic. They drew an insightful diagram (see fig. 26.5, example 3), in which the chunks are repeated cyclically until only two children remain on the near side. Then the final trip to get the two children across is simply the first leg of the next cycle.
By the time the students finished solving these problems, they were able to implement their strategy in a repetitive procedure with few errors. In addition, by forcing the students to attend to the details of the strategy, the teacher guided them in inventing a generalized algorithm that they could apply almost flawlessly to any Crossing the River situation with two children.

FROM ALGORITHM TO SYMBOLIC REPRESENTATION
The teacher's final goal in this process was to induce the students to model the algorithm algebraically. To do so, the teacher asked the students, "Can you describe, in words, how to figure out the answer for this problem if the group of people to cross the river includes 2 children and any number of adults? How does your rule work out for 100 adults?" The teacher used such a large number of adults to encourage the students to think of a way to solve the problem other than by manipulating or drawing each trip. Finally, the teacher challenged the students, "Can you generalize the rule for 2 children and any number of adults, say, x?"
Tyra quickly started chanting, "Two kids, one kid, one adult, one kid; two kids, one kid, one adult, one kid; two kids, one kid, one adult, one kid..." while Akeem counted the number of crossings and Jorge counted the number of adults. Pretty soon, however, they got confused. Then Akeem said, "Each adult needs 4 trips, so that's 400 trips. We don't need to count them. It's four times the adults." He forgot about the extra trip at the end, and so did Tyra and Jorge. To help them remember, the teacher suggested they compare their solution with Joe, Enrique, and Cybill's solution.
Joe, Enrique, and Cybill had not forgotten about the extra trip. They looked at their colored diagrams and were able to write, "Four trips for every adult, plus the last trip for the 2 kids. 4 ◊ 100 + 1. 4x + 1." Ning, DeAnn, and Thomas also were quickly able to solve the problem, writing "1 + 4 ◊ 100. The first trip to get the two kids across and then 4 trips for every adult. 1 + 4x."
Sam, Rosa, and Tara, though, took a different approach. They concentrated on the directions of the arrows in their diagram (fig. 26.5, example 1) and separated them into two types: those going over and those coming back. They explained, "Each adult needs 2 trips over and 2 trips back, and we can't forget the last trip for two kids. So, you take the number of adults and multiply by 2. That is, 100 ◊ 2 = 200. You add 1 for the last trip = 201. Then you add 200 + 201 = 401." The general form of the solution the students provided was 2a + 2a + 1 (here a stands for the number of adults).
One student, Josť, had a very different approach to this problem. He used the results of prior problems and some proportional reasoning to arrive at his answer. His group had already determined that with two children, three adults require thirteen trips, fifteen adults require sixty-one trips, and six adults require twenty-five trips. So he reasoned that the first twenty-four adults (3 + 15 + 6) to cross would require ninety-six trips (13 + 61 + 25 - 3), since the total of the trips from prior problems was ninety-nine but the three extra trips must be subtracted because the three groups are separate. Next he multiplied the 24 adults and the 96 trips each by 4 to determine first that 96 (i.e., 24 ◊ 4) adults would require 384 (i.e., 96 ◊ 4) trips. He then separately figured out that he needed 17 more trips to get the remaining 4 adults and 2 kids across. So his final answer was 401. He tried to write a rule for x adults and 2 children but got frustrated and gave up. The teacher mentally noted that although Josť's solution was quite creative, she would watch him in his discussions with other students to see if he could adopt an approach more conducive to symbolic representation.
The examples given here show the importance of having students invent their own algorithms. It is clear that each group of students had its own unique way of conceptualizing the Crossing the River problem. Because the teacher encouraged the students to invent their own algorithms, they were given an avenue to express their individual conceptualizations of the problem. Being able to conceptualize the problem indicated that the students really understood the generalizations they eventually discovered. More important, the teacher avoided the pitfall of imposing a conceptualization of the problem and a generalization that the students did not understand. The discussions of the students' solutions to the problem naturally lead them to make sense of using variables to represent patterns.

CONCLUSION
As Steen (1986, p. 6) indicates, "the mathematics curriculum must not give the impression that mathematical and quantitative ideas are the product of authority or wizardry." Students have "authority" over the algorithms through their own inventing and their constructive processes in solving nonroutine problems. When students invent algorithms, they will not only know the algorithms but will also know when and how to apply the algorithms correctly to novel situations. Students should be encouraged and allowed such invention and knowledge-construction processes in the classroom. Moreover, mathematics instruction at the middle school level is essential to preparing students for their study of algebra in high school. The development of their algorithmic thinking is an important component of the preparation.
Added material
Fig. 26.1
Fig. 26.2. Jane's pairing algorithm for the Staircase problem
Fig. 26.3. Two students' geometric algorithms for the Staircase problem
Example 1: Bob and Tasha's algorithm group
Example 2: An algorithm from Patti's group
Fig. 26.5. Algorithms for the Crossing the River problem
Example 1: Sam, Rosa, and Tara's conceptualization of the chunks in their algorithm
Example 2: Ning, DeAnn, and Thomas's conceptualization of the chunks in their algorithm
Example 3: A cyclic algorithm from Terry, Glenn, and Roberta's group

REFERENCES
Kamii, Constance. Young Children Continue to Reinvent Arithmetic (Third Grade): Implications of Piaget's Theory. New York: Teachers College Press, 1994.
National Council of Teachers of Mathematics. Curriculum and Evaluation Standards for School Mathematics. Reston, Va.: National Council of Teachers of Mathematics, 1989.
National Council of Teachers of Mathematics. Professional Standards for Teaching Mathematics. Reston, Va.: National Council of Teachers of Mathematics, 1991.
Piaget, Jean. To Understand Is to Invent: The Future of Education. Translated by George-Anne Roberts. New York: Grossman Publishers, 1973.
Steen, Lynn. "A Time of Transition: Mathematics for the Middle Grades." In A Change in Emphasis, edited by Richard Lodholz, pp. 1-9. Parkway, Mo.: Parkway School District, 1986.

FIG. 26.4

CROSSING-THE-RIVER PROBLEM
Eight adults and two children need to cross a river. A small boat is available that can hold one adult or one or two children. Everyone can row the boat.
What is the minimum number of trips needed for all the adults and children to cross the river?
Show or explain how you got your answer.

WBN: