A small math success - but huge for us

[lewelma]

For the past 2 months we have spent an hour per day working together through the Art and Craft of Problem Solving. Thank you so much Kathy in Richmond!!! What a wonderful, wonderful (and difficult) book!

 

So here is the success....yesterday, we were working on an IMO problem and actually knew how to start it! We could not do it, mind you, but we could:

 

1) understand the question and what it was looking for

2) know how to investigate it and what kind of conjecture we were trying to find

3) have an intuitive sense of the tactics to use, and we were right!

4) be able to apply our number theory knowledge

5) And when we gave up after and hour and looked at the proof.....we could understand the proof!! :hurray:

 

This was a HUGE success for us, and I have been feeling so good all day even though we did not actually solve the problem!

 

Here is the problem for those who are interested:

 

(IMO 1985) Consider a set of 1,985 positive integers, not necessarily distinct, and none with prime factors bigger than 23. Prove that there must exist four integers in this set whose product is equal to the fourth power of an integer.

 

My ds told me that he wished he lived in the year, 4, because then all the problems would be easier! He has noticed that the problems often use the year of the exam in the problem! :001_smile:

 

Ruth in NZ

[Kathy in Richmond]

:hurray: :hurray: Yay Ruth & son!

 

Isn't it the best feeling to make progress on that kind of tough problem? and a bit addictive, too?! Sounds like your ds will be more than ready for the summer testing at this rate!

 

& how cool that you're taking this on this challenge together! There might be two mathematicians in your family before long... :D

[Arcadia]

My ds told me that he wished he lived in the year, 4, because then all the problems would be easier! He has noticed that the problems often use the year of the exam in the problem! :001_smile:

 

 

:hurray: If he lived in the year 4, he might be the one writing the theorems instead of the one proving them

[quark]

Awesome news Ruth! :party: <<< This is your tiny little fan club from this corner of the US being inspired by you guys and cheering you on!

[kiwik]

Yay indeed.

[Tress]

So cool!

[Wildiris]

I love Kathy in Richmond's recommendations. Is this the book you're talking about? The Art and Craft of Problem Solving.

 

How old is your child? I assume your using this with your 7th grader.

[lewelma]

I love Kathy in Richmond's recommendations. Is this the book you're talking about? The Art and Craft of Problem Solving.

 

How old is your child? I assume your using this with your 7th grader.

 

 

yes, that is the book. My son is 12. We are currently able to understand only 30% of it. It is a University math majors textbook. The author states that you should read each chapter until you don't understand, then move to the next chapter. When you finish the first pass of the book, you start again. This approach allows you to work at your personal level in each topic, and allows your ability in all topics and problem solving to be increased concurrently.

 

There is NO way that my son could work with this book independently. We work on each problem together and then read through the proofs together. If the problem is easier, we each separately investigate it and write up a formal proof and then compare. My goal is to find ideas in each problem that will be generalizable to other problems. We keep a list, and I quiz him every day about the different generalizable skills we have learned. For example, what kinds of problems are would likely be helped by the extreme principal? or what kind of problems suggest a proof by induction? How can you recognize parity in geometry problems? These types of questions are not directly answered in the text -- they are more of a way for us to really internalize what we are reading and categorize all the ideas. Plus, it helps us review esoteric ideas by recalling specific problems that reflect them. We've decided that if there are 20 different tactics that are possible, and we can recognize that 4 are good candidates for a certain problem, we can try those four. If one works, great, if none work, then at least we have gotten our hands dirty and have a much better understanding of the problem and can go from there.

 

To help in proof writing, I drill him on specific phrases like "This specific case is generalizable because the only special feature of 11 that we used is that it is odd." (yes, I am memorizing all this too, so that just popped out of my brain). This drill has really helped him not only with the language of math, but also helped him realize different approaches he could use to prove a conjecture. For example, the above case showed us that you can use an example as your proof in many cases of parity. This is very important to know, because most proofs do not allow this. Our overall goal is to get as many tools in our tool box as we can, and then remember what tools we have in there!

 

All this is really working. I cannot believe how far we have come in 2 months.

 

I told someone last week that I could only go through this process once because what I am giving my son is not a knowledgeable tutor, but rather a skilled learner who is at his exact level in math. If I ever go through this material again with a student, I would be much much more knowledgeable and I would loose the confusion that has been so critical in helping him battle through this material. What I am finding is that because I don't know the answers and I cannot teach him how to do it, I am instead teaching him how to learn problem solving -- what questions to ask, what answer to hunt for, how to compare problems, how to really interact with this material. No tutor who knows the material well could do this as well as I can, because once you have the knowledge, it would be virtually impossible to relive the confusion.

 

But then I realized that because my memory is so shaky, I could probably do it one more time. :001_smile:

 

Ruth in NZ

[Tress]

But then I realized that because my memory is so shaky, I could probably do it one more time. :001_smile:

 

 

:D, you are funny and VERY inspirational!

[mathwonk]

this problem is really frustrating me. I tried an easier version, that there must exist two numbers whose product is a square. i got that one i think. the idea was that the exponents of all the primes in the product should be even. So the two numbers multiplied together to yield a square should have the same parity for every prime power. Since each exponent is either odd or even, and there are only 9 primes ≤ 23, there are 2^9 = 512 different choices of these parities. Hence if we have more than 512 numbers, there must be at leat two such that every exponent has the same parity. Then their product has all exponents even and hence is a square.

 

But I don't know the solution yet for a fourth power.

[Pen]

Wow! I was once upon a time on a math team, and cannot now even figure out what the problem means...

 

I don't think I understand the set of the positive integers which are "not necessarily distinct"--I thought in a set if something was not distinct then it was not counted as an element of the set. ??? If the integers can be the same number, then I think I can find sets for which this would not be true and thus could not be proved.

 

How many factors up to 23 can there be? Is 23 x 23 x 23 x 23 ... x 23 ... a possible member of this set? Or is the highest possible integer in the set 23 x 19? Or is the highest integer in the set 23 x 19 x 17 x 13 ... x 2 ?

[lewelma]

Mathwonk, you have hit a point in the proof where the book purposely skips a step to make you think.

 

At this point they repeatedly use the pigeonhole principle to conclude that 1472 integers in the set can be arranged into 736 pairs such that each pair contains 2 numbers with identical 9-tuples of exponent parity. (They have 2 more paragraphs in the proof which I can write out if you want). However, they don't tell us HOW they repeatedly use the pigeonhole principle. So if you can figure it out and explain it to us, we would be most appreciative.

 

Ruth in NZ

[lewelma]

Wow! I was once upon a time on a math team, and cannot now even figure out what the problem means...

 

Yes, this is why we were so excited.

 

I love my internet friends. No one else understands why we are so pleased to only understand the question and not even solve it. And no one is willing to listen to me explain it!

[mathwonk]

ok. lets try it.

[lewelma]

I don't think I understand the set of the positive integers which are "not necessarily distinct"--I thought in a set if something was not distinct then it was not counted as an element of the set. ??? If the integers can be the same number, then I think I can find sets for which this would not be true and thus could not be proved.

 

How many factors up to 23 can there be? Is 23 x 23 x 23 x 23 ... x 23 ... a possible member of this set? Or is the highest possible integer in the set 23 x 19? Or is the highest integer in the set 23 x 19 x 17 x 13 ... x 2 ?

 

 

Yes, it can be ANY number, as in really really huge -- 23^10000 would count. BUT the number must be factorable into only the 9 primes - 2, 3, 5, 7, 11, 13, 17, 19, 23

 

Not necessarily distinct, means they could be the same number if you want. But that did not really help us.

 

The tactic that we used was parity of the exponents, because they must factor into something to the fourth. So you have 4 numbers and each has an exponent for each prime (even if the exponent is 0), and when you add all 4 exponents they must be a multiple of 4. My ds figured all this out, but then I got the next step. You must use the pigeon hole principle to demonstrate how you have too few holes for all the pigeons. With only 512 possible parity combinations and 1985 numbers, there must be too few combinations. Hopefully Mathwonk can fill in the holes in the proof, because we can't quite see it.

[avilma]

The proof proceeds in 2 steps.

First one proves that there are more than 512 pairs of integers whose product is a perfect square.

Second one proves that there is at least a pair of those perfect squares whose product is the fourth power of an

integer.

 

For both steps the important observation is that each of the 1985 numbers (and any other number

which is a product of 2 or more of those numbers) is the product of powers of the 9 prime numbers that are smaller

or equal to 23. Note that some of the exponents of these powers could be 0. For example 46 is a number that can be in our set

since it can be represented as 2 x 23 = 2¹ x 3⁰ x 5⁰ x 7⁰ x 11⁰ x 13⁰ x 17⁰ x 19⁰ x 23¹

The product of 2 such numbers will be a perfect square if the matching exponents for each of the 9 bases have the same

parity, i.e. if the exponents are both odd or both even.

Each exponent can be either odd or even which is a binary choice so the number of different combinations of parities

for all 9 exponents can be at most 2⁹ = 512. So if I take 513 numbers from the set of 1985 I know that at least 2 of

them have same parity exponents so their product is a perfect square. Take out this pair of numbers. I am left with 511 numbers

in my "working" set and 1985 - 513 = 1472 in the "reserve" set. Move 2 numbers form the "reserve" set to the "working" set

so there are again 513 numbers in the working set. Again there is a pair in the working set whose product is a perfect square.

Take out that pair so I have now got 2 pairs of numbers whose product is a perfect square. Keep moving 2 numbers from

the "reserve" set to the "working" set and taking out a pair of numbers whose product is a perfect square from the "working"

set until there are no more numbers in the reserve set. At the end we would end up with at most 511 numbers in the

"working" set from where we cannot extract anymore pairs and (1985 - 511) / 2 = 737 pairs of numbers whose product

is a perfect square.

 

Now for the second step of the proof we consider the 737 perfect squares. Again those numbers are product of powers

of the 9 prime numbers that are smaller or equal to 23. But the exponents this time are all even. Now these

even exponents can be divisible by 4 or not divisible by 4 (but of course divisible by 2). This is again a binary choice so there can be at

most 2⁹ = 512 such perfect squares whose combination of exponents divisible by 4 or not divisible by 4 are different.

Since we have 737 perfect squares we have at least 2 numbers who have each exponent of the matching bases either

divisible by 4 or not divisible by 4 (but even). Now the sum of 2 exponents divisible by 4 is divisible by 4 and

the sum of 2 even exponents not divisible by 4 is divisible by 4 so the product of those 2 perfect squares has all exponents divisible by 4

which means that that product is the 4th power of some integer. This proves what was asked.

[lewelma]

Thanks! I really appreciate the detail. We will read over it tomorrow.

 

Ruth in NZ

[mathwonk]

sounds good. i am a little dazed at the moment and hence will not certify it, but it sounds good. nice explanation!

[serendipitous journey]

 

(IMO 1985) Consider a set of 1,985 positive integers, not necessarily distinct, and none with prime factors bigger than 23. Prove that there must exist four integers in this set whose product is equal to the fourth power of an integer.

 

 

:svengo:

omgoodness.

 

so, so happy that you could

 

1) understand the question and what it was looking for

2) know how to investigate it and what kind of conjecture we were trying to find

3) have an intuitive sense of the tactics to use, and we were right!

4) be able to apply our number theory knowledge

5) And when we gave up after and hour and looked at the proof.....we could understand the proof!! :hurray:

 

whoo!!!!! hoo!!!! WHOOO-HOOO!!!!

 

 

and I feel very, very reassured that after educating A. I will prob. have sufficient maths to play around with theoretical neuroscience (my retire-from-homeschooling dream). Good grief.

 

did I say:

 

WHOOOOOOOOOO-HOOOOOOO!!! y'all are awesome!

[serendipitous journey]

Ruth, do you proceed using only the solutions (a subset, I gather from the Amazon reviews) available in the book? Do you have an instructor's version?

[lewelma]

Ruth, do you proceed using only the solutions (a subset, I gather from the Amazon reviews) available in the book? Do you have an instructor's version?

 

So far we have only used the book because we are only working through the explanation portion of each chapter and have not yet attempted any of the problems at the end of each section. The explanation portion's proofs are complete. The idea is to cover all the material that we can understand in each section and then move on. When we finish the book, and ds has completed more AoPS we will be ready for the next pass at which time we will be ready for some of the problems. In 8 weeks with 5 hours per week, we have covered 1/2 of the teaching portion of each section in the first 3 chapters. The book has 9 chapters, so even the first pass will take us 6 months. Each day we only do 1 question because we spend 30 minutes trying to figure it out before peaking. And often we just look at the first part of the proof and then spend 15 more minutes on our own. Also, once we read the proof, I make ds repeat it verbally (or in writing) from memory. Given that these proofs can be a page long, this is not as easy as it sounds. But it makes sure that he really understands them!

 

We have the instructor's guide, but even it does not contain all the solutions. The author has not included in the instructor's guide any of the proofs from previous IMO or other contests that are available on line, so we are going to have to do a big hunt. I think he has done this on purpose so that you really have to think about a problem rather than just give up and look at the proof. Either that or there is a copyright problem.

 

This is a book that will keep us going all the way to the IMO if ds gets there. It is REALLY challenging, and will take us at least 4 years to complete I am sure.

 

Ruth in NZ

[lewelma]

:svengo:

omgoodness.

 

WHOOOOOOOOOO-HOOOOOOO!!! y'all are awesome!

 

Thanks! I could not believe that we even knew what to do with the problem. We have come so far in such a short time. The exam starts at the end of July and last 3 weeks, and I am finally beginning to think he will be ready.

 

On a different note, 2 weeks ago I had a flash of brilliance and quickly wrote down my answer. My son, who usually is much better than I am at problem solving, spent an additional 30 minutes slaving away only to come up empty handed. Then he turned to me and asked me to explain what I did. And I had NO IDEA what I did or how I knew to do it. We then look at the complete proof and I was right!?!? It happened again last week - right answer and then the understanding was GONE. And I mean completely GONE. So yesterday, I say "Oh, I got it!" And he said, "quick, tell me right now, or you will forget!" :tongue_smilie:

[Tress]

:D This thread makes me so happy! Surrounded by unschoolers who think that building bird houses and baking cookies teaches you 'more than enough math', this thread makes me positively giddy.