Back in my undergrad days, when I was taking a number theory class, I noticed that all squares that weren't multiples of three were always one more than a multiple of three, never one less.
16 = 15 + 1
25 = 24 + 1
100 = 99 + 1
After I thought about it for a while I realized that this had to be the case and there was a simple algebraic proof that showed it (there's a also a simple geometric proof -- think about cutting the square into two smaller squares and two rectangles -- but that can wait for another day).
I'd assign this with the following hint:
think about (x + 1)(x + 1) and (x - 1)(x - 1)
Here's the proof. All natural numbers can be written as:
II. 3k + 1
III. 3k - 1
We're talking about squares that aren't multiples of three so we can skip the first case and look at II and III.
(3k + 1)(3k + 1) = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1
(3k - 1)(3k - 1) = 9k^2 - 6k + 1 = 3(3k^2 - 2k) + 1
I like this problem for a few reasons.
First, it's simple. The question is easy to state and the proof is at the right level for a beginner.
Second, it gives the student a chance to do something interesting with polynomials.
Third, it demonstrates an important problem solving technique -- breaking the problem down to cases.
Fourth, it introduces number theory and it gets the students thinking about numbers in a different way.