There's no argument in the fact that problem solving is a vital part of our intellectual functions and something that helps keep the mind sharp. Even something as simple as a logic puzzle, such as Sudoku, can help influence our mental well being.
One of my favorite activities to keep my problem solving sharp is participating in competitions at TopCoder, a company dedicated towards providing online competitions in algorithms, component design, and so on. I personally participate in the algorithms competitions. I highly recommend for everyone who can program in Java/C/C++/C# to participate from time to time, even if you feel like you have no chance. If anything, it will keep your mind and your programming skills sharp. The scoring system is based on time, so you learn to gear your mind towards immediately being able to categorize problems and then developing a solution.
Currently, the TopCoder Collegiate Challenge is underway, and I have surpassed my expectations this year. Last year I only made it past the qualification rounds, but this year I have matched that and even made it past two more online rounds. If I am able to make it pass two more online rounds then I would have the opportunity to go to Orland and compete against 47 of the world's finest. I don't expect to make it this far from a realistic point-of-view, not a pessimistic one. Nevertheless, I will definitely try my best to make it even further.
Don't think it's just your physical self that needs to be kept "in shape"!