Ask YC: Math problems
13 comments
Now and then I work through problems on projecteuler.net without anything more than a basic calculator. I've gotten 17 of them so far (1, 2, 5, 6, 8, 9, 15, 17, 18, 19, 24, 52, 63, 76, 164, 190, 191).
Also, there are a bunch of contest problems on John Scholes's website: http://www.kalva.demon.co.uk/ . It seems to be down at the moment, but I'm sure it'll be back soon. Of the contests I'm familiar with:
AIME is for fairly advanced high school students (say, on average, one person per high school might take it, and most won't get any of them right)
USAMO is a step up from AIME -- the top ~150 high school students in the US take it each year
IMO is a step up from USAMO -- basically, don't even bother
Putnam is an exam for US university students -- it's generally considered difficult, since the median score is usually 0, even among those willing to take it in the first place, but A1 and B1 are usually pretty easy on every test; I would say it's between AIME and USAMO
Also, there are a bunch of contest problems on John Scholes's website: http://www.kalva.demon.co.uk/ . It seems to be down at the moment, but I'm sure it'll be back soon. Of the contests I'm familiar with:
AIME is for fairly advanced high school students (say, on average, one person per high school might take it, and most won't get any of them right)
USAMO is a step up from AIME -- the top ~150 high school students in the US take it each year
IMO is a step up from USAMO -- basically, don't even bother
Putnam is an exam for US university students -- it's generally considered difficult, since the median score is usually 0, even among those willing to take it in the first place, but A1 and B1 are usually pretty easy on every test; I would say it's between AIME and USAMO
USAMO and IMO problems are about the same difficulty. Try some of the easier ones first - they are in order of difficulty, so the first ones are generally easier. In general geometry is more likely to require specialized knowledge; go for the problems that sound "programmy". Putnam problems are about the same average level of difficulty but there is more of a gradient from A1-A6 and B1-B6.
I strongly disagree. USAMO problems range in difficulty quite a bit. I can solve some but certainly not all. Not so for IMO. And nowadays I generally solve all of the Putnam problems in the time allotted.
By the way, the early years of the IMO were very easy, by today's standards (only a few countries were involved at that point). They would probably be approachable to people comfortable with the AIME problems.
By the way, the early years of the IMO were very easy, by today's standards (only a few countries were involved at that point). They would probably be approachable to people comfortable with the AIME problems.
Add WYSE to the list - some really intriguing problems there.
You could print out a couple Project Euler problems. Most of them can be solved with pencil and paper, but most people make programs to help them out. They're quite fun.
http://www.projecteuler.net
http://www.projecteuler.net
If you are looking for a physical book, try Problem Solving Strategies (http://www.amazon.com/Problem-Solving-Strategies-Problem-Boo...) or Problem Solving Through Problems (http://www.amazon.com/Problem-Solving-Through-Problems-Larso...).
I suggest something light and something out of the ordinary to counterbalance. You'll never know for what type you are in the mood. Here are two that I love:
How to Solve It -- by G. Polya
How to Solve It -- by G. Polya
http://www.amazon.com/How-Solve-Aspect-Mathematical-Method/dp/0691023565
http://www.amazon.com/Alice-Puzzle-Land-Raymond-Smullyan/dp/0140070567Yes -- anything by Smullyan is a pleasure to read. I think much of it is out of print, but should still be findable. "Lady or the Tiger" and "Satan, Cantor, and Infinity" were both good reads. "Alice," as well.
Yeah the link I supplied actually had a few people selling used copies. I got a first edition of it a while back and I still love to pull it out and go through the problems to freshen up my brain. :)
One thing I do when I'm bored is to prove the equations I've been taught in my math classes but have never seen derived (like many people, I often skip past the proofs in the textbook when I'm in a rush to finish my homework). Deriving these is enlightening and gives me a nice feeling of "oh, that's why." Also, understanding the derivation of the fundamental math theorems can actually come in handy, in contrast to some contest questions, which can be contrived and arcane in comparison.
http://www.artofproblemsolving.com/Forum/resources.php is a good source of problems. I'd just stick with USAMOs (click on the "USA" link), they're varied and of pretty high quality.
If you truely want a really great, small, book, purchase Peter J. Eccle's An Introduction to Mathematical Reasoning.
http://books.google.com/books?id=ImCSX_gm40oC&dq=an+intr...
http://books.google.com/books?id=ImCSX_gm40oC&dq=an+intr...
One of my favorite books is To Mock a Mockingbird, by Raymond Smullyan (http://www.amazon.com/Mock-Mockingbird-Raymond-M-Smullyan/dp...). It presents itself as a puzzle book that teaches combinatory logic along the way. Not only is it lots of fun to work through the puzzles, but at the end, you have a pretty solid understanding of the lambda calculus.
Anything by Martin Gardner.
Titu Andreescu has some good problem books. You might like 102 Combinatorial
Problems, http://www.amazon.com/102-Combinatorial-Problems-Titu-Andree...,
if you like Concrete Mathematics, and it's fairly small to carry.
Thanks to everyone who's made suggestions. I've ordered some books and and I'm checking out the other sources. Should give me enough to work on for a while :p
But you didn't tell us what you decided on! Those of us who did well have to be able to brag! ;)
This is a nice book: http://www.amazon.com/dp/0486647250
Just work on the Collatz Conjecture. It's trivial to understand and it'll keep you busy :P
I can't tell if this is a joke or not, but if it's serious it's not a good idea. Working on one impossible problem is a good way to get frustrated as hell.
Bah.
I love working on impossible (or rather, impossibly difficult) math problems... especially on airplanes when I get sick of reading. The point isn't to solve them but simply to understand why they are hard. When you get a glimpse into the complexity that is these problems, you begin to see why mathematicians go insane.
Collatz is great for this because anyone can understand it and anyone who understands rigor can try to prove it.
I love working on impossible (or rather, impossibly difficult) math problems... especially on airplanes when I get sick of reading. The point isn't to solve them but simply to understand why they are hard. When you get a glimpse into the complexity that is these problems, you begin to see why mathematicians go insane.
Collatz is great for this because anyone can understand it and anyone who understands rigor can try to prove it.
Collatz is completely unapproachable. Sure, anybody can understand what it's saying and run the algorithm on a couple of numbers. Very few people will be able to do anything else with it. (I think that saying that you can "understand why Collatz is hard" is disingenuous. Maybe you're admiring the fact that something so simple can be so intractable, but unless you're a phenomenal mathematician you're not understanding it more fully.)
Now, YMMV, of course. It's just been my experience—and the experience of my mathematically-inclined friends—that banging your head against a problem that is way out of your league is more frustrating, less rewarding, and less useful than working on something within your abilities. If your goal is a distraction, go with what works, but if your goal is to improve your problem solving abilities, don't act like a spectator—do something you can actually do.
Now, YMMV, of course. It's just been my experience—and the experience of my mathematically-inclined friends—that banging your head against a problem that is way out of your league is more frustrating, less rewarding, and less useful than working on something within your abilities. If your goal is a distraction, go with what works, but if your goal is to improve your problem solving abilities, don't act like a spectator—do something you can actually do.
Well, I disagree that it's completely unapproachable. And I take a slight bit of offense that you think my comments are disingenuous. You don't sit down to "solve" an open problem. You sit down to learn things about it. And your claim that you can't learn anything useful or discover it's intractability is just flat wrong.
Collatz has two parts, one that there are no cycles, and two that there are no divergent trajectories.
For example, you can trivially prove that there are no cycles of length 2, or even 3, or 4. It's not hard, at all. It's not unapproachable. It's easy. For a slightly more difficult problem, you can try to generalize your method of proof to show there are no cycles less than some number N, given some criteria. I'll leave that as an exercise to the reader.
I've developed my own proof about the smallest possible cycle. It was actually pretty good. Once I decided it was legit, after alot of work and refinement. I read a bunch of papers on the issue from actual mathematicians. Mine wasn't as good as theirs, but still not bad.
Or, you can categorize numbers by how often, after undergoing the 3x+1 step, they divide by 2. For example, the number 3 only gets divided by 2 once (3->10->5). You can very quickly find the patterns to show all the numbers that divide by 2 once, twice, and so on.
You can go farther with this pattern idea, as well... by finding the sequences of numbers that, for example, divide once on the first iteration of the Collatz function and then divide twice.
Using this idea, you can prove, for example, that there are no divergent sequences that only divide by 2 once at each step.
I have a few dozen pages in a notebook with a whole bunch of interesting but likely useless facts about Collatz. So please don't tell me it's "unapproachable" and nothing can be done except stare at it dumbfounded.
Collatz has two parts, one that there are no cycles, and two that there are no divergent trajectories.
For example, you can trivially prove that there are no cycles of length 2, or even 3, or 4. It's not hard, at all. It's not unapproachable. It's easy. For a slightly more difficult problem, you can try to generalize your method of proof to show there are no cycles less than some number N, given some criteria. I'll leave that as an exercise to the reader.
I've developed my own proof about the smallest possible cycle. It was actually pretty good. Once I decided it was legit, after alot of work and refinement. I read a bunch of papers on the issue from actual mathematicians. Mine wasn't as good as theirs, but still not bad.
Or, you can categorize numbers by how often, after undergoing the 3x+1 step, they divide by 2. For example, the number 3 only gets divided by 2 once (3->10->5). You can very quickly find the patterns to show all the numbers that divide by 2 once, twice, and so on.
You can go farther with this pattern idea, as well... by finding the sequences of numbers that, for example, divide once on the first iteration of the Collatz function and then divide twice.
Using this idea, you can prove, for example, that there are no divergent sequences that only divide by 2 once at each step.
I have a few dozen pages in a notebook with a whole bunch of interesting but likely useless facts about Collatz. So please don't tell me it's "unapproachable" and nothing can be done except stare at it dumbfounded.
Understanding why it is intractable is probably a good learning experience by itself.
The path is the goal, or how is that saying translated to english?
While thinking about an impossible problem, you can discover lots of other things. Also, who says that it is impossible?
While thinking about an impossible problem, you can discover lots of other things. Also, who says that it is impossible?
> The path is the goal, or how is that saying translated to english?
Probably most often heard as...
The journey is the destination
Probably most often heard as...
The journey is the destination
I'm going traveling in se asia for 3 months fairly soon. I'm planning on doing a lot of lazing about and reading. I'd quite like to work on some math problems while I'm there. I've been enjoying working through Concrete Mathematics but it's too heavy to take with (I'm traveling light). Does anyone have an suggestions of a source of good interesting problems and exercises? Either somewhere I can download them or in a book that's small enough to carry with me would be good.