If you're worried about being dishonest, it's easy enough to say, "Oh, yes, I've seen this problem before. The solution I came up with was ..."
When interviewing for my current job, they gave me a quiz that included what amounted to the classic fizz-buzz problem, but using different words and with some slight differences. So I just said, "Oh, this is a lot like fizz-buzz", and proceeded to give a solution.
If you were warned that this question would come up in the interview (maybe the recruiter tells you or a friend interviewed there recently) and you looked up an answer on the Internet and memorized it, and then you trot this answer out as if you just figured it out, okay, that could be cheating. But if you frankly say, "oh yeah, I read a solution to this problem not long ago", and can explain why and how the solution works, even if you didn't think of it yourself, you're demonstrating a level of understanding. I've occasionally interviewed people who were able to give a solution to a problem but it quickly became clear they had no idea where this solution came from or how it worked. Obviously they just copied it from somewhere.
As someone else on here said, if an interviewer is going to use commonly-known problems -- fizz-buzz or square roots or whatever -- it would be absurd for them to then accuse someone of cheating because he's heard of the problem before. (I've never been asked about the Towers of Hanoi on an interview, and I don't remember the details of the problem so besides a vague, "yeah, I'm pretty sure the solution was repetitive or recursive or something", I'd have to figure it out again anyway. But whatever.)