A cheat for the standard multiplication algorithm

Of course, I mean the one that looks like this (pick whatever format you prefer): 

The one on the left is the one that I learned in school. It was one of my great dislikes. I always made errors when I performed it. This post describes a work-around, a “cheat”, if you like, that drastically cut down on my errors. It's a method that I generally hid from my teachers and colleagues so they wouldn't know how weak I was in arithmetic. I have not seen it used elsewhere, but I found it so helpful that I would not be surprised to learn that others have discovered it. 

I have a curious mental glitch. For some reason my brain will occasionally swap digits. For example, when I see 432 on the page, it stays as 432 as long as I look at it, but if I were to avert my gaze in order to record the number elsewhere, I might write 342 and remain totally unaware that I had made an error.

I still make mistakes like this. I'm sure now that this memory quirk is the source of some of my difficulties with arithmetic. However, as a kid, it never crossed my mind that that I might have a twist in my neural circuits. I just accepted that I was not very good in arithmetic.

Here is how my memory quirk could affect me if I were to multiply 68 by 4 following the method that we were taught in elementary school: 

4 times 8 is 32. Write down the 2 and carry the 3. Keep the carry number in memory. Then 4 times 6 is 24, and 24 plus the carry number is 26 so the answer is 262. 

Although my addition skills are no great shakes, in this case I was not adding incorrectly—when I got 26 the addition was perfectly correct: 24 plus 2 is 26. What happened was that in my head I was swapping the memorized "carry number" (the 3) with the number I had just written down (the 2). 

When we were first learning the multiplication algorithm, instead of having to keep the carry number in our heads, we were permitted to write tiny numbers in the appropriate place above the multiplicand like so:

Writing down the carry numbers was not a cure. Even for single digit multipliers, it only helped a little bit. It did not help at all when the multiplier had more than one digit. The jumble of small carry numbers written above the multiplicand actually exacerbated the situation. 

By the time I started high school (grade eight) I had concocted a “cheat”. Instead of separating out the carry numbers either in my mind or on the worksheet, I wrote down the full product of the individual digits. The cheat was not perfect, but it substantially reduced my errors. Using the cheat, here is how to multiply 345 by 6.

The alignment is important. First the product of 6 and 5  is 30, so write 30 diagonally with the 3 in the ten’s column and the 0 in the units column but in the line below. Next, the product of of 6 and 4 is 24, so write 24 diagonally with 2 in the hundred’s column and the 4 in the ten’s column in the line below. This places the 4 directly below the 3, and both 4 and 3 are in the ten's column. Continue in this way, writing the product of 6 and 3 diagonally with the 1 in the thousand’s column and the 8 in the hundred’s column below the 2. Finally, add the columns vertically to get the answer. 

This can be adapted to multi-digit multipliers as shown below, but it starts to get messy.

To avoid the messiness, I usually multiply 345 separately by 4 and 6 on scrap paper as shown below on the right, and then transfer the answers to the proper position in the standard algorithm as shown on the left.  (I still do this when I have to multiply multi-digit numbers without a calculator.)

                                          

Why call this a “cheat”? Well, when I was a youngster, doing anything that was outside the rules was considered cheating, and, if nothing else, arithmetic was taught as a set of rules. So in that context, it was cheating.

* * *

You may notice that my cheat has a very strong resemblance to the lattice method of multiplication. Of course, back in my day they did not teach the lattice method, and I didn’t actually know about it until I taught a “math for elementary teachers” course. In such courses I avoided teaching the lattice method because I thought that writing things slantwise in one direction and adding things slantwise in the opposite direction followed by wrapping the answer around two sides of a square would screw up a student's understanding of place value. To be honest, I do not know if the lattice method really does lead to place value confusion. I also confess that I never taught students my cheat method, so, although I believe that the cheat's strong emphasis on the proper location of the digits with regard to place values would be beneficial, I really don't know if  that is the case. 

* * *

Regarding my memory quirk, I don't think it's dyslexia. If it is, then it’s extremely mild. It’s nowhere near as profound as what Toomai describes in his post about the dyslexic mathematician. What little I know about dyslexia is that it also causes troubles with algebra, and I never had difficulty with algebra. Surprisingly, my wonky memory regarding numbers doesn’t apply to letters.

Proofs and problem solving, part 3 of 3

First of all there is considerable impatience with the material. Surprisingly, this is often noticeable in the better students. But better students tend to demand instant understanding. Mathematics has always been easy for them. Understanding and intuition have come cheaply. Now as they move into the higher reaches of mathematics, the material is getting difficult. They lack experience. They lack strategies. They don’t know how to fiddle around. 

— Davis and Hersh in "The Mathematical Experience", 1980

Davis and Hersh are talking about students from the late 1970’s, but the passage describes quite accurately the resistance displayed by some of my university students even in this century. 

I particularly like the comment about fiddling around, because that’s what you have to do to create a proof or solve an unfamiliar problem. Throughout my teaching career, whatever the curriculum of the day was, my students seemed to have had very little practice fiddling around. They seemed to have the notion that a solution or proof always follows a pre-ordained script.

I was able to remedy this somewhat by exposing them to mathematical puzzles—ones that were simple, yet which could not be solved by following a memorized procedure. The students pretty well had no choice except to fiddle around. And because the puzzles seemed simple, they were quite willing to try.

I ended the previous post with the following puzzle. It’s simple, but the complete solution is not obvious. It’s one that I frequently used in a university course, and I think it would work for junior high / high school students. Although it is well known, I doubt that many students are familiar with it. 

You are presented with eight coins, numbered from 1 to 8, but otherwise identical in appearance. One of them is fake and weighs slightly more than the others. The real coins are all exactly the same weight.  

You have at your disposal a two-pan balance, and no other weights except the coins themselves. The problem is to find the counterfeit coin using as few weighings as possible. 

Now if you choose two of the coins and by good fortune one of them was the counterfeit, then weighing one against the other would reveal it. However, this really does not count as being a solution. You need something that works all the time and does not depend upon luck.

Here is a possible solution, one that is based on the binary search idea described in my previous post. This is how I did it at first, and so did most of my students. 

Divide the eight coins into two groups of four. Weigh one group of four against the other to find out which group contains the fake. Divide that group in half, and weigh two against two to identify which pair contains the fake. For the third and final weighing, compare the coins in that pair to identify the counterfeit.

A binary search is very efficient in many cases, as it is for this puzzle. But it is a script to be followed, and following a script does not always lead to an optimal solution. We have yet to convince ourselves that three weighings is the best that we can do, that it is impossible find the counterfeit in less than three weighings. There doesn’t seem to be an obvious way to prove this, so here’s where the fiddling around has to occur. And we will see how fiddling around reveals a better solution. 

A tactic that is sometimes useful is to approach a problem from the reverse direction. Instead of trying to find the minimum number of weighings for eight coins, let us ask what is the maximum number of coins we can handle if we are only allowed one weighing. If we have a collection of coins and one is fake and slightly heavier, how many coins can be in the collection?  Can we find the counterfeit with one weighing if we have two coins? three coins? four coins? etc. 

If we have two coins and one of them is fake, putting a coin in each pan will immediately identify the counterfeit. If we have four coins and one is fake, putting two in each pan will allow us to identify which pair contains the fake, but unfortunately it does not reveal which member of the pair is the fake. We would need another weighing. 

So one weighing with four coins (or more) seems out of the question. What if we have three coins? Putting two in one pan and one in the other won’t help. The coins are close in weight, so the pan with two coins would tilt down regardless. So, it is unreasonable to ask about an odd number of coins—we need an even number so that we could put the same number in each pan.  

One of the difficulties that I have when fiddling around is that I am prone to making unwarranted assumptions, and I just made one here. Who says that we have to put all of the coins in the pans? With three coins, why not see what happens if we put one coin in each pan and leave the third coin aside? And that does it! If the balance tilts, we will know immediately what coin is counterfeit. If the balance stays level, then the two coins in the pans must be the same weight and so the coin that we left aside must be the counterfeit. With three coins we can find the counterfeit with one weighing. 

This fiddling around with three coins throws a new light on the entire puzzle. Maybe we don't have to divide the eight coins into two groups of four. What if we divide the eight coins  into three groups, put a group in each pan, and leave the third group aside? 

What if we put three coins in each pan and leave two aside? If the pans don’t balance, this will tell us which group of three contains the fake. If the pans balance, this will tell us that the group of two that we left aside contains the fake. Either way, we will know which group contains the counterfeit, and since the groups contain only two or three coins, with one more weighing we can find the counterfeit. 

So this logical fiddling around leads to a better solution. With eight coins, we can find the counterfeit in two weighings, and the fiddling around has revealed that the counterfeit cannot be found with less than two weighings. 

* * *

In its original form, the counterfeit coin puzzle did not use numbered coins. The reason I specified that they be numbered is that there is another solution, and it’s easiest to explain if you number the coins. This alternate solution came about because I was still fiddling around and changed the question a bit. What if we could not use the information obtained from the first weighing to determine what to do for the second weighing?  In fact, a solution with two weighings is also possible in this case.

Let us imagine that the coins are arranged in an array as follows:. 

The rows and columns will tell us what coins we should weigh. In both weighings we will weigh three against three and leave two aside. 

Using the rows: weigh 1, 2, and 3 against 4, 5, and 6, and leave 7 and 8 aside. That will tell us which row of the array contains the fake. Call it the hot row. 

Using the columns: weigh 1, 4, and 7 against 2, 5, and 8, leaving 3 and 6 aside. That will tell us which column is the hot column. 

The counterfeit coin is located at the intersection of the hot row and the hot column, just like finding a point in the Cartesian plane given its x and y coordinates. And we don't have to know the outcome of the first weighing before doing the second weighing. 

* * *

You can search the internet and find this and many other counterfeit coin puzzles. You will no doubt encounter the problem discussed here. Some posts ask why use eight coins when the same solution works for nine. I think that using nine coins gives too strong a hint that the coins should be split into three groups of three, so I prefer the eight coin version.

* * *

It would be wonderful if there was an algorithm that always tells us how to fiddle around. 

Unfortunately, there is as yet no such algorithm. The closest I have seen to this is the collection of strategies described by George Polya in his books about problem solving. What one should do when fiddling around depends upon what the problem is. The best way to learn is to practice on lots of problems.

Proofs and problem solving, part 2

This is the second of three posts about the connection between problem solving and proofs. 

A couple of questions tempted me to write these posts:  What is a proof? And why is it difficult to learn how to prove things? 

Michael Pershan asked 37 math teachers why they think kids find proof so hard in geometry. One of their suggestions was that kids have not yet developed logical thinking or deductive reasoning. I am not entirely comfortable with that sentiment, and, like Michael Pershan, I think that that kids already have some logical reasoning abilities. I don’t think that you can sharpen their abilities by making them study and-or / if -then statements or by drawing truth tables. And figuring out how to prove something is not completely a deductive process. 

As to what a proof actually is, most definitions are as vague as you can get, and boil down to some variation of saying that “a proof is just a convincing argument”. Keith Devlin has written several evolving posts about it, and most recently (here) put it this way:

Proofs are stories that convince suitably qualified others that a certain statement is true.

I like Devlin’s discussion of what a proof is, but I worry about the “suitably qualified others” part of the definition. Not because I think it is inaccurate, but because I think that a student who is first learning how to prove things will likely take it to mean “It’s not a proof unless my teacher says it is.”

Some of us may equate “proof” with a notion that I would call “formal proof”, the idea that a proof must follow a specific template or format—which puts yet another hurdle in front of a student trying to learn how to prove things. 

I think you will have great difficulty proving something if you are continually fretting about obtaining some sort of external approval. Before even thinking about convincing someone else, you should at least be satisfied in your own mind that what you are doing is valid. Some sort of “self feedback” if such an oxymoron makes sense. 

Before teaching someone how to prove things, and especially before making students practice templated proofs, it may be beneficial to put them in a position where this self feedback occurs naturally. One way to do this is to provide interesting problems, ones that are within reach but which do not have an immediately obvious solution.  

In the previous post, I included the following puzzle, and I will use it as an example to show how problem solving and proof sometimes go hand in hand.

There are three boxes that contain red and white balls. One box contains 10 red balls, one contains 10 white balls, and the third contains 5 red and 5 white balls. The boxes have been labelled “red”, “white”, and “mixed”, but each label is on a wrong box.  

All of the boxes have lids so you cannot see what is in them, but you are allowed to reach inside the boxes without peeking and take one or more balls out and look at them. Taking out as few balls as possible, figure out what the correct labels should be. 

When I first saw this puzzle, my initial reaction was to start asking “What if” questions:

What if I take a ball from the box that is mislabelled “red”?  Either the box contains only white balls or else it contains a mixture. If I take one ball and it’s red, then I know the box has a mixture. But if it’s a white ball, then I’m in trouble—I could have selected a white ball if the box contains a mixture. So selecting one ball is not enough. If I take even five balls from the box they could all be white, and I still won’t know whether it contains the white balls or a mixture.

What if I also take some balls from the box mislabelled “white”. If I get red balls from the  from the “white” box, I’m in the same pickle.

This is not too promising. Maybe I should take some balls from all three boxes?

What I described above is based partially on my memory of my own experience and also on what I imagine might happen to others. However, even if you had these thoughts, you no doubt moved on. Your next step might have been:  

What if I take a ball from the box mislabelled “mixed”?  That box contains either all red balls or all white balls, so one ball is enough to tell me what its label should be.

At this point you would probably feel that you are on track to a solution. You are also starting to work out why the solution works even though you haven’t yet got a complete solution. 

After realizing that you only need to look at one ball to determine what is in the "mixed" box, you have to imagine what your next step would be. There are several courses of action. My own instinct was to ask myself if I needed to look at ball from another box. Here’s how I remember thinking about it:

What if I now draw a ball from the box mislabelled “red”? I’ve just been through that.  That box contains either all white balls or a mixture of red and white balls. 

Wait a minute. By this time I will know the colour of the ball that I drew from the box mislabelled “mixed”. Suppose it was white. Then this is the only box that contains all white balls, so the box mislabelled “red” can’t contain only white balls. I already know that it can’t contain only red balls, so it would have to contain a mixture of red and white balls. 

And then this leaves only one possibility for the last box, the one mislabelled “white”—it must contain only red balls.

At this point you have a solution: you can figure out the correct labels if you take just one ball from the box labelled "mixed".  At the same time you have a proof that your solution works even though the proof and the solution are a bit disorganized and not quite complete. 

I do not know if all students can hold all this reasoning in their minds while they are solving the puzzle. It would be beneficial to use physical models to play with—actual boxes and balls with labels that could be switched around. Many years ago I saw a grade 5 student demonstrate a solution and explain her reasoning using such props. Her proof convinced me. 

Next post’s puzzle 

The puzzle that is the subject of the next post is interesting to me because of some prior knowledge that I had, and before stating it I want to set you up with the same background. 

When I was in grade seven or eight, we used to play a "guess a number" game. I goes like this (this is not the puzzle for the next post, but just a set up):

I am thinking of a number between 1 and 100. You can ask me questions that have a “yes or no” answer. Try to guess it in as few questions as possible. (Of course by a “number” we mean a whole number, not a fraction.)

We had a variety of approaches and questions.  One of our strategies was to first determine whether it was even or odd, thereby cutting the possibilities in half. Let us suppose the number was 21. The questions might go like this:

Q1: Is the number divisible by 2? Ans: No.  

Q2: Is the number divisible by 3? Ans: Yes.  

Q3: Is the number divisible by 9? Ans: No.

And we could continue in this way trying to find the divisors of the number:

Q4: is the number divisible by 5? Ans: No.

Q5: Is the number divisible by 7? Ans: Yes. (so it's odd and a multiple of 21)

Q6: Is the number 21? Yes.

This strategy works well for some numbers, but the process can be rather lengthy for others. (Try it for a prime number like 59.) 

Eventually, we learned another strategy: keep halving the interval that contains the number.

Q1: Is it bigger than or equal to 50?  Ans: Yes. (so it's from 50 to 100)  

Q2: Is it bigger than or equal to 75? Ans: No. (so it's from 50 to 75) 

Q3: Is it bigger than or equal to 62? Ans: No. (so it's from 50 to 61) 

Q4: Is it bigger than or equal to 56? Ans: No. (So it's from 50 to 55) 

Q5: Is it bigger than or equal to 53? Ans: No. (So it’s, 50, 51 or 52) 

Q6: Is it bigger than or equal to 51? Ans: Yes. 

Q7: Is it 52? No. 

Q8: Is it 51? Yes.

The process being used is called a binary search, and any computing science student will be familiar with it. You can always find a number between 1 and 4 in three guesses, between 1 and 8 in four guesses, between 1 and 16 in five guesses, and so on. 

This sets you up for the following problem which is the subject of the next post. I’ve known this puzzle for years. I’m not sure where it originated, but I think it was with Martin Gardner.

You are presented with eight coins, numbered from 1 to 8, but otherwise identical in appearance. One of them is fake and weighs slightly more than the others. The real coins are all exactly the same weight. 

You have at your disposal a two-pan balance, and no other weights except the coins themselves. The problem is to find the counterfeit coin using as few weighings as possible.

Now if you choose two of the coins and by good fortune one of them was the counterfeit, then weighing one against the other would reveal it. However, this really does not count as being a solution. You need something that works all the time and does not depend upon luck.

Come back in a week or so and see if you got the same solution (and surprise) that I did. 

Proofs and problem solving, part 1

The human visual system alters and reshapes our perception of reality. Highlights appear where there are none, shadows are created that do not exist, and identical colours somehow end up looking dramatically different. We are so accustomed to this that it passes without notice. 

The effects can be very strong. I remember being astonished in the mid 1970’s when I first learned about the highlight and shading effects in the Cornsweet illusion and Mach band effect. There are also amazing difficulties in accurately perceiving colours. See for example the examples here (scroll down a screen or so to the "blue and green spirals"). I urge you to visit these illusions before reading the rest of this page. 

There was a time, well before the invention of photography, when artists strived to portray things in a realistic fashion. The perceptual distortions of light and colour mentioned above must have been a challenge: if an artist were to paint what he “saw”, he would include those false visual effects, and a person viewing the painting would be looking at something that differed significantly in light, shade, and colour from the actual scene. As a result, the viewer's perception would likely differ quite a bit from the painter's perception. Sort of like the increased blurriness that you get when you save a jpeg copy of a jpeg, or the degradation that occurs when you make a Xerox copy of a Xerox copy. Passing an already filtered version back through the same filter may have a detrimental effect.

Yet, despite these obstacles, some artists were able to achieve remarkable realism. It makes me think that they were fully aware of the artifacts that their vision introduced, and that they found ways to expunge the distorted light, shade, and colour from their paintings. Exactly how they did this is not clear.

One solution is offered in the film Tim’s Vermeer. It recounts Tim Jenison’s attempt to describe how, in the 17th century, Johannes Vermeer could have used relatively simple optical devices to help him create the light and colour in the painting The Music Lesson. Although not explicitly stated as such, the film is all about how Vermeer could have circumvented the problems inherent in his own visual system and thereby realistically duplicate in his painting the physical highlights, shadings, and colours that were present in the scenes that he observed.  

Viewing the film through my filter as a mathematician, I think of it as somewhat of a sustained metaphor about the process of problem solving and its relationship to proof. In a university lecture, the presentation of a solution frequently follows a path like this: Here’s a problem, here’s my solution, and here’s proof that my solution works. But this is what happens after the solution is obtained. What most likely happened before the solution was completed is that the solving and the proving were thoroughly interweaved.

In the film we see Tim Jenison’s solution to the problem of  accurately reproducing physical light, shade, and colour, along with his proof that his solution works. His proof that Vermeer could have used optical devices is to use those devices himself to recreate Vermeer's Music Lesson.  As the film proceeds, Jenison sticks to his basic premise, but continually adjusts and adapts the process, much like what happens when one is solving a mathematical problem. 

By the time I have solved a problem, my first thoughts about how to solve it have been mostly forgotten. It may be a personal peculiarity, but I find it very difficult to recapture my state of mind as it was when I first considered the problem. When I present my solution, I can polish and burnish it, and can point to logical insights that, once you notice them, inexorably lead to a solution. However, I usually garner these insights as I work my way through the solution; they are not the initial thoughts that led me to the solution.  In other words, the manner in which I present my solution is not always a true reflection of how I solved it. 

This is not a happy state of affairs when teaching. If you show your ultimate solution to a class—no matter how polished and clear it is—if your students do not experience some of  the missteps, stumbles, and side avenues that you took along the way, are you really doing anything different than reading from a textbook? 

George Polya has written books about problem solving, and he gives suggestions on how to get past the initial stages [see the wikipedia article about How to Solve It]. I am not going to dwell too much on that part of problem solving. But what I do want to examine is what happens after you are pretty sure that you are going in the correct direction, how you can continue in that direction, and how during that process you are actually developing an argument that your solution is valid. In other words, I will try to show how proof and problem solving are intimately intertwined just as they are in the the Tim’s Vermeer film.

This will be the content of my next two posts. and I will use two well known simple puzzles to try and illustrate the process. 

Here is the first puzzle:

There are three boxes that contain red and white balls. One box contains 10 red balls, one contains 10 white balls, and the third contains 5 red and 5 white balls. The boxes have been labelled “red”, “white”, and “mixed”, but each label is on a wrong box.   

All of the boxes have lids so you cannot see what is in them, but you are allowed to reach inside the boxes without peeking and take one or more balls out and look at them. Taking out as few balls as possible, figure out what the correct labels should be.

So go ahead and solve it, and convince yourself that you have a solution. Come back in a few days and see if you followed a path similar to mine. 

If you are interested in the Tim's Vermeer film, there is more information about it here and here.  The film is controversial, especially among art historians who view it as an attack upon the artistic integrity of Vermeer. Moreover, in The Music Lesson, Vermeer did not depict everything accurately, but deliberately added and removed light and shade to enhance the painting (see here). This, however, does not disprove that Vermeer used physical devices to help him understand light, shade and colour. And, unlike some of the art historians, I do not view the film as belittling artists: to me it demonstrates the intelligence and ingenuity of visual artists like Vermeer.