Prove that either
a) this problem is solvable
or
b) this problem is unsolvable
Well, my first thoughts on this is that it is impossible to prove that the problem is unsolvable. If you could prove it unsolvable, then you would have a solution to the problem (i.e. a proof for 'prove that ... b) this problem is unsolvable'), thereby making it solvable - paradox.
So, as a result of the above the problem must be either solvable, or a proof can never be generated at all for either argument. However, if no proof can be generated at all, then the problem is unsolvable - BUT, if this were the case then we have proved that the problem is unsolvable, which results in a paradox again.
So, the only non-paradox solution left to us is that the problem is solvable.
Ack! Does that even make sense? I've lost track now...
(I'm marking this as Some Thoughts as I've no idea if this even works as an answer...)