A revelation regarding problem solving especially for tough contests.by StatOnTheSide Tags: contests, revelation, solving, tough 

#1
Apr713, 03:48 PM

P: 92

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. 



#2
Apr713, 05:45 PM

Mentor
P: 10,809

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.




#3
Apr713, 05:56 PM

P: 92





#4
Apr813, 01:42 PM

P: 1

A revelation regarding problem solving especially for tough contests.
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/tra...ons/E175en.pdf 



#5
Apr813, 02:38 PM

P: 92

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+(l1)" 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. 



#6
Apr813, 04:11 PM

Mentor
P: 10,809

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 :). 



#7
Apr813, 04:30 PM

P: 92

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! 



#8
Apr913, 07:21 AM

Mentor
P: 10,809





#9
Apr913, 07:54 AM

P: 2,477

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. 



#10
Apr913, 11:42 AM

P: 92

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. 



#11
Apr913, 12:12 PM

P: 2,477

There was a classic story about this: A princess was being forced to marry a prince. The prince said lets 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. 



#12
Apr913, 12:22 PM

P: 92

Nice one!




#13
Apr1013, 05:38 PM

Sci Advisor
P: 1,168

Hope this is not too faroff: 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. 



#14
Apr1013, 06:10 PM

P: 92

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. 



#15
Apr1013, 06:35 PM

Sci Advisor
P: 1,168

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 wellargue that classical mathematics was a somewhatchaotic 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 nicelypackaged, 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. 



#16
Apr1013, 07:00 PM

P: 92

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



#17
Apr1013, 08:49 PM

P: 2,477

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 whats 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/ 


Register to reply 
Related Discussions  
The new James Bond, a revelation.  General Discussion  19  
Tough tough question: Calculating magnetic Flux in water  Classical Physics  0  
The book of Revelation and the White Horse  General Discussion  16  
Computer Revelation: share forums  Computing & Technology  0  
Celestial Revelation  General Discussion  4 