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.