A revelation regarding problem solving especially for tough contests.

[StatOnTheSide]

I have recently had a revelation and I have very few people to share it with. It would mean a lot to me if the experienced problem solvers in this forum can pitch in and add to/correct the following paragraph. I am thinking that in case there is more to it, then I would love to hear about it and learn. Kindly do provide your input in case you think there is more to it than what is given below.

What makes a contest problem tough is the so called "crux move" as Paul Zeitz calls it or the "insight" that Prof. Schoenfeld refers to in his book 'Mathematical Problem Solving'. A problem to find or to prove requires certain logical statements which when connected will form the solution. Exercise problems seldom have a crux move. All the logical statements are straightforward and that's what makes them easy. On the other hand, a tough contest problem will involve one or two logical statements which are hard to observe. So the idea is to 'play around' with the given data and try to fish out a conjecture which can potentially make the solution straightforward. This approach is seldom taught in high school or heck, even in engineering. This approach seems to be unique only to higher level problem solving in math or higher level education in pure math. Since I am an engineer, I never came across this approach in the context of solving math problems before I looked into problem solving in contests. I have taken this approach in engineering during the time when I was doing research in circuit design but it never occurred to me that the approach is same for solving tough math contest problems!

In 1976, thee was a problem in the IMO which asked something to the effect of "break 1976 into smaller positive integers so that their product is maximum". As there are a lot of ways to do it (1976=1+1...+1=1000+976=...), it might be initially daunting to figure out a way. Simply finding the maximum product for lower numbers (like the maximum for 9 instead for 1976) will reveal a possibility that all the numbers are either 2, 3, or 4 and that the number of 2s cannot be more than 2 (for example in the case of 10, breaking it to 3+3+4 gives the maximum product). Since 1976=3.658+2, the maximum then turns out to be 2*(3^658) if the conjecture is true. Now you have to try to prove the conjecture and if it turns out true, you solved the problem.

A problem's solution, when presented, looks deductive. But the solution in the making is totally inductive. You have to play around with the given data to find out a possible pattern so that conjectures can be made. Those conjectures will then be used to solve the problem. If not, you move on to a different strategy to figure out more patterns to solve the problem. The tricky part of the whole process is to first understand the problem correctly and then, to figure out that crux move/insight/critical conjecture which can possibly help solve the problem.

I would truly appreciate it if the members of this forum can pitch in and add to it or correct the above. It is a revelation to me but I am quite sure that it is a very routine thing for a very experienced problem solvers/mathematicians of this forum.

 

[mfb]

I don't have anything to add to the general statement (I agree), but I think the example you picked has an easy way to find the solution. Consider the simple case of a product of two numbers - you quickly see that splitting 2a=a+a and 2a+1=(a+1)+a is the best, and from this it follows that no two numbers in an ideal decomposition can differ by more than 2. If all the numbers are (approximately) the same, you get something like a*a*... (b times), or a^b. It can be shown that a=e=2.718... maximizes this in the real numbers, and if you restrict the decomposition to integers you get many 3 and a few 4 or 2 - with your posted limit, as 2*2*2 is worse than 3*3.

 

[StatOnTheSide]

I don't have anything to add to the general statement (I agree), but I think ...

Thanks very much mfb. It is good to know that you agree with the general appraoch to solve tough contest problems. Please do feel free to add more to it in case you think it is missing something.

 

[tfree76]

I think this is an excellent observation. Journal articles usually don't describe the process of discover and as you observed math education doesn't cover this either.
In earlier times, math research papers sometimes contained more information about the path to discovery. One example would be a paper by Euler, "Discovery of a most extraordinary law of numbers, relating to the sum of their divisors"
The paper is available at: http://eulerarchive.maa.org/docs/translations/E175en.pdf

 

[StatOnTheSide]

I think this is an excellent observation. Journal articles usually don't describe the process of discover and as you observed math education doesn't cover this either.

Thanks very much tfree76. I wonder as to why such a simple thing is not included in standard math syllabus. It might stem from the fact that this approach may be a little bit deeper than what kids can handle. It may not be something that kids 'have to know'; however, it is nevertheless a very simple thing that teachers should be able to teach their more gifted kids so that they can crack problems from tough contests.

Haven't you ever wondered as to why math olympiad problems or putnam problems appear so tough? For example, there is one problem in 1983 putnam: Let f(n) = n + [√n]. Define the sequence ai by a0 = m, an+1 = f(an). Prove that it contains at least one square.

When you read my solution, I based it on a the statement "if n=k^2+l where 0<l<k+1, then f(f(n)) = (k+1)^2+(l-1)" and so if you keep on operating it with the function 'f', the number 'l' will eventually go to zero. For me, this statement is one of those things that mathematicians seem to do very often namely 'pulling a rabbit out of a hat' or the way G. Polya calls it "Deus Ex Machina" in his book 'Mathematics and Plausible Reasoning Vol. II'. How on Earth did I get this conjecture?

Well the answer now is very simple. Contest math base their problems on some specific mathematical fact. The trick is that it won't be obvious at all when you read a problem. It needs "Discovery". You take the inductive approach and play around with the given data to "Figure out a pattern". Now this pattern will eventually lead you to the conjecture and the solution to the problem. This is the general theme. Whether you can figure out the pattern or not is definitely a matter of talent and practice. But if you are not aware of this general procedure, no amount of talent or practice will help you solve such problems. In this problem, I calculated the first few terms of the sequence and I then found the pattern where every second term approaches the nearest perfect square by one more than the second previous term in case l<k+1. Proving that conjecture was easy and it is a common sense thing to say that it is a positive number which decreases and hence will become zero at some point.

When I was a kid, I tended to look at such problems and then just kept on trying to figure out an algebraic expression for when this number would become a perfect square while not having any ideas as to how I would be able to do it. This is called the wild goose chase by Prof. Alan Schoenfeld the great! Now I realize the general approach to contest problems and I don't even bother to do algebra unless there are indications in the problem statement itself which requires some algebraic modifications.

Proofs are a chain of logical statements. How do you make a math problem hard? Just make one or two of the logical statements in the proof to be a very obscure fact and let the student fight it and figure out that obscure thing. Then the exercise is it to just practice and get better at making conjectures and then once you get very good at arriving at the obscure logical statemtents, the rest will be straightforward. Paul Zeitz, in his book 'Art and Craft of Problems Solving', has even devoted a whole chapter on simply making conjectures which is a strong indication of how imporant it is to be able to observe a pattern and make conjectures.

In earlier times, math research papers sometimes contained more information about the path to discovery. One example would be a paper by Euler, "Discovery of a most extraordinary law of numbers, relating to the sum of their divisors"
The paper is available at: http://eulerarchive.maa.org/docs/translations/E175en.pdf

I have taken a print out. Thanks very much for pointing to this article! I think there is another famous article written by Descartes called "Rules for the Direction of Mind". I am thinking that he will have more information about mathematical discovery.

 

[mfb]

When you read my solution, I based it on a the statement "if n=k^2+l where 0<l<k+1, then f(f(n)) = (k+1)^2+(l-1)"

I think that part needs some modification. Consider 8, f(8)=10, f(10)=13.
8=2^2+4, and 13=f(f(n))=3^3+4.
It is possible to fix that, however - l is decreasing if (and only if) l<k, and as l can only stay constant or decrease and k increases this has to happen.

Thanks for the nice problem :).

 

[StatOnTheSide]

I think that part needs some modification...It is possible to fix that, however - l is decreasing if (and only if) l<k

Thanks for the correction mfb. Does that not follow from the line where I state that
0<l<k+1? Feel free to correct me.

I just typed it quickly and it does not have the rigor that a complete proof must have. You have to consider what happens if l>k+1 or when l=k+1. If you have l=k+1, the next step results in a perfect square. If you begin with l>k+1 but l<2k+1, then the next step will result in f(n)=(k+1)^2+q where now, q<(k+1)+1. Here q=l-(k+1).

It is amazing though that once you observe the pattern, it makes the solution very simple and somewhat trivial!

 

[mfb]

You have to consider what happens if l>k+1 or when l=k+1.

Exactly.

It is amazing though that once you observe the pattern, it makes the solution very simple and somewhat trivial!

Once you see that the increment (a -> a+sqrt(a)) follows (roughly half) the distance between square roots, you found the trick.

 

[jedishrfu]

Contest problems are designed to see how deeply you understand the problem space. You might call it insight or intuition as to what is the best approach. The simplest problem I remember was when a prof told us when doing surface integrals in x and y that sometimes its better to integrate over y before x and then on a quiz he gave such a problem. If you remembered what he said then you could solve it quickly if not then you might waste some precious seconds until it hit you.

In some sense, the common strategy of most students for problem solving is depth first that is you choose a direction go as far as you can and then backout a step and try another path. Hard problems may require you to back out all the way and choose another direction but what often happens is frustration sets in. However, in doing this you gain insight into what works and what doesn't for this problem and others like it.

On tough competition tests like the MAA tests, the best students have gone over the ground before, have studied prior tests, have the skills to do quick mental math and can see the pitfalls in most of the problems.

A chess strategy may be something to teach students where you consider all choices at the start, mentally score them and then trying the choices with the highest score first. So in the calculus example above, you'd consider:
- integrate over x (look at a few steps)
- integrate over y (look at a few steps)
- try some substitution
- other...

Another problem I had in Classical Mechanics had a similar effect on me. We were asked to show that an object falling from some great distance from the Earth would traverse half the distance in
something like 7/9 of the total time of fall (I don't remember the actual ratio I was traumatized by the problem). The problem difficulty was in trying to relate the Gm/r^2 rate of acceleration to time of fall and we just couldn't connect the two until our prof comes in and says did you ever consider using one of Keplers laws. We of course said no as they relate to orbits and this has no orbit. He then said:

Well what if the orbit was real narrow like up and then down and you only need the down part.

After that insight, the problem falls apart.

As I look at the CM problem, its clear that you need a deep understanding of the problem space. The Kepler law gave us that for this type of problem but the insight comes from trying to solve the problem. So I guess insight is more like exercise you have to keep at solving problems to make it better. Its something that can't be taught better.

 

[StatOnTheSide]

Contest problems are designed to see how deeply you understand the problem space. ...

In some sense, the common strategy of most students for problem solving is depth first that is you choose a direction go as far as you can and then backout a step and try another path. Hard problems may require you to back out all the way and choose another direction but what often happens is frustration sets in. However, in doing this you gain insight into what works and what doesn't for this problem and others like it....

So I guess insight is more like exercise you have to keep at solving problems to make it better. Its something that can't be taught better.

Thanks very much for sharing your experience jedishrfu! You have rightly pointed out that insight can be obtained only through practice but as you also have pointed out previously, it is a necessary mental action to back out all the way and choose another direction. To know when to do it and to act that way forms the so called control behavior. Many students, like the way I was when I was a kid, never do that. Reading a problem, there is one possible approach that comes to mind. Then like a bull, I used to charge. If I failed, I would simply accept defeat and run away or I would keep on charging at the problem and it never occurred to me that I had to take a different approach simply because I thought that there is no other approach possible.

Then I would read the solution when I gave up. And lo. The solution has the crux move where it feels like the guy pulled a rabbit out of a hat!

Like what you have suggested, I have now realized that you have to figure out the insight into a problem. It might be a pattern that will lead you to a conjecture which forms the crux move. It might be as simple as choosing the right variable as you have pointed out in the example you have given. In physics, there might be more strategies like trying a law or principle that might not look relevant at the outset but can be made use of in such a way that it becomes useful in that context. But in order to be able to do all that, it is very necessary for anybody to have control over the thought process. In case one approach does not lead you anywhere, then the student must 'back off and take another approach'. This is the metacognitive quality that many develop and many don't which are all very nicely explained in Prof. Alan Schoenfeld's 'Mathematical Problem Solving'. That comes only with training to most of the kids. For the ones who have already been doing that, it might look trivial; however, for someone who is new to the topic of metacognition in problem solving will definitely find it as a completely new skill.

Once the student is fully aware that he has to back off once the standard approach won't work, then he can pratice more and figure things out. But if he is not aware of this fact, then no amount of practice will help him. Everytime he sees a problem, he will be on a wild gose chase which will take him nowhere no matter how hard he tries.

 

[jedishrfu]

Thanks very much for sharing your experience jedishrfu! You have rightly pointed out that insight can be obtained only through practice but as you also have pointed out previously, it is a necessary mental action to back out all the way and choose another direction. To know when to do it and to act that way forms the so called control behavior. Many students, like the way I was when I was a kid, never do that. Reading a problem, there is one possible approach that comes to mind. Then like a bull, I used to charge. If I failed, I would simply accept defeat and run away or I would keep on charging at the problem and it never occurred to me that I had to take a different approach simply because I thought that there is no other approach possible.

Then I would read the solution when I gave up. And lo. The solution has the crux move where it feels like the guy pulled a rabbit out of a hat!

Like what you have suggested, I have now realized that you have to figure out the insight into a problem. It might be a pattern that will lead you to a conjecture which forms the crux move. It might be as simple as choosing the right variable as you have pointed out in the example you have given. In physics, there might be more strategies like trying a law or principle that might not look relevant at the outset but can be made use of in such a way that it becomes useful in that context. But in order to be able to do all that, it is very necessary for anybody to have control over the thought process. In case one approach does not lead you anywhere, then the student must 'back off and take another approach'. This is the metacognitive quality that many develop and many don't which are all very nicely explained in Prof. Alan Schoenfeld's 'Mathematical Problem Solving'. That comes only with training to most of the kids. For the ones who have already been doing that, it might look trivial; however, for someone who is new to the topic of metacognition in problem solving will definitely find it as a completely new skill.

Once the student is fully aware that he has to back off once the standard approach won't work, then he can pratice more and figure things out. But if he is not aware of this fact, then no amount of practice will help him. Everytime he sees a problem, he will be on a wild gose chase which will take him nowhere no matter how hard he tries.

Basically the student has to learn to think outside of the self-imposed box. Self-imposed because they never thought they could.

There was a classic story about this:

A princess was being forced to marry a prince. The prince said let's be fair about this. Here's a jar with a white stoneand a black stone. If you pull the white stoneyou can go free. However if you pull the black stoneyou must marry me.

The princess saw the stonesbeing dropped into the jar were both black.

What should she do?

She can't win.

She can't call the prince a cheater. He'll just laugh, cancel the contest and get married.

The solution:

Spoiler

Select a stone and accidently drop it on the ground and say: Oh I'm sorry but you can tell which stone I didn't pick by retrieving the one left in the jar.

 

[StatOnTheSide]

Nice one!

 

[Bacle2]

Hope this is not too far-off: I am by no means an expert programmer, but it struck me to know that people who wrote software were/are expected to document the programs they write. I thought: why not require something similar for mathematical proofs , when published? That way it would be easier to see how the proof was done , and its internal structure.

Another issue is that, when doing problems from a book, it is clear from the context what you need to use to solve the problems/exercises; you use the main results given in the chapter. This is good maybe for an intro level, but maybe should be abandoned as soon as one can.

 

[StatOnTheSide]

Hope this is not too far-off:

Not at all. This is an excellent point!

I am by no means an expert programmer, but it struck me to know that people who wrote software were/are expected to document the programs they write. I thought: why not require something similar for mathematical proofs , when published? That way it would be easier to see how the proof was done , and its internal structure.

This is a very good point. You must read G. Polya's "Mathematics and Plausible Reasoning" Vols 1 and 2. Math in the making is never published these days. In the old times, they used to publish their line of thinking. I think Euclid's "Elements" does that. So when Mathematicians tell you "go and read Euclid", they mean that you must read his work and understand his line of thought. This is exactly what is lacking in the books which give you the tough International Math Olympiad Contest problems and their final one or two line solution. What about the way in which it was arrived at? How did you arrive at the crux move? Why do you do this "pulling the rabbit out of a hat thing again and again and again"?? God knows how much I have been frustrated by this. I am extremely thankful to Him that I have now been able to see as to how it is all done. How did I figure it out? My main source of eye opening was through Professor Schoenfeld's book "Mathematical Problem Solving". He shows a graph where he reports the progress or lack of progress of a novice as time passes. It completely resembled my behavior. Then he shows a graph of that of an expert. I then understood as to why I was not naking progress. Simple thing. If a particular approach does not work, convince yourself that it does not work and drop the dang thing. Move on to a different approach. Observe. Simplify. Look at various simpler situations. Look at a similar problem. Try to see a pattern and try to guess or make a conjecture by observing some pattern. That will form the crux move and you will solve the problem.

q(x) is a polynomial with real coefficients. It is such that for all x,
q(x)-q'(x)-q''(x)+q'''(x)≥0. Prove that q(x)≥0 for all x. Here, q'(x) is the derivative of q(x) wrt x.

So what do you do? Simplify. Take q(x)-q'(x)≥0. How does this behave? Behave according to what? The only thing that is varying here is x. OK so how does it vary according to x? OOOOOOh
Now I see. If q(x)≤0, then so will q'(x) and hence, if q(x) becomes negative from a positive value, it will never cross x-axis again. Rest must be easy. This was a regional olympiad problem somewhere.

Math education has to change. On one hand, kids find it hard to digest what is already taught. At the other end of the spectrum, kids who can solve ALL the textbook problems orally can't solve a single Olympiad problem because inductive reasoning to arrive at deductive reasoning is NEVER taught at the high school level or even at advacned levels unless you are a math major. Inductive reasoning, if made as a new approach to present solutions of math contest problems, will in itself be a very effective way to teach kids to learn the way to solve tough contest problems. Paul Zeitz, in his book "The Art and Craft of Problem Solving" has made the beginning to that approach and I congratulate him for that.

 

[Bacle2]

I think the situation you describe may have to see with the Bourbaki movement, which intended to strip "all the inessentials" from mathematical proofs and arguments. There is definitely some benefit to streamlining arguments, and maybe one can well-argue that classical mathematics was a somewhat-chaotic collection of results that needed organization. But the Bourbaki and modern mathematics movement may have gone too far in that direction, in stripping and eliminating the mess that underlies discovery, and hiding the underlying ideas in the process.

This reminds me of a story told to to me by a man about his grandson. The man was frustrated because the grandson would throw out food without consideration. The grandpa, who had grown in a farm, frustrated, asked the kid: why do throw out food? do you know where food comes from? The kid answered: "yes, from the supermarket" . The kid only knew of the final stage, where he would go to the supermarket, where everything was nicely-packaged, in a nice environment, etc. The kid was not aware of the gigantic underlying logistical machinery needed to turn, say, a cow into beef patties, or the machinery needed to produce, store and distribute cheese. I think something similar happens as a result of all the high tech , which hides all the underlying machinery.

Ultimately, it seems, the education system is still designed, to a large extent, to train people to follow orders in factories. I understand the system was designed with this explicit goal in mind, around the time when the industrial revolution was happenning. This is not so to the same extent in private schools, who train their students to become leaders, managers, etc.

 

[StatOnTheSide]

I think the situation you describe may have to see with the Bourbaki movement, which intended to strip "all the inessentials" from mathematical proofs and arguments. There is definitely some benefit to streamlining arguments, and maybe one can well-argue that classical mathematics was a somewhat-chaotic collection of results that needed organization. But the Bourbaki and modern mathematics movement may have gone too far in that direction, in stripping and eliminating the mess that underlies discovery, and hiding the underlying ideas in the process.

This new to me. I had never known about it. Thanks very much for letting me know about it!

This is not so to the same extent in private schools, who train their students to become leaders, managers, etc.

Wow. Those kids must be very lucky then to have received good education. The school I was in, I actually taught my teacher about how to solve some of the more difficult exercises in the textbook. You can imagine the quality of education I have received. This is not to take away credit from the ones who have achieved it with good training. All I am saying is that a lot of us have missed out on very good opportunities due to lack of good training.

Thanks very much for the information Bacle2. I will now have to read up on the history of presentation of Mathematical material!

 

[jedishrfu]

Hope this is not too far-off: I am by no means an expert programmer, but it struck me to know that people who wrote software were/are expected to document the programs they write. .

This is no longer strictly true. API libraries are minimally documented as least as to how to call a method or function. At one time 1960's maybe IBM hired english majors for programmers. They had the logic and they had the skills to write good documentation. Now everyone hires programmers who think of themselves as hackers who can understand any kind of mess and refashion it into a new kind of mess for the next programmer. (I am one of those refashionable folks...)

Applications are often haphazardly documented within the source and often the comments are wrong. Code evolves but comments don't. Its the eternal battle of I can do it fast, I can do it cheap, and I can do it well, pick any two and what's usually chosen is fast and cheap with the promise to go back and do it well.

There's a website devoted to bad programming practices:

http://thedailywtf.com/