The "Ercules and the Hydra" problem, as found in "L. Kirby and J. Paris. Accessible independence results for peano arithmetic. London Mathematical Society, 4:285 293, 1982.".
It is easily solved with
Using transfinite induction, but it is possible to show that Hercules will always kill the hydra (with a finite number of blows) regardless of the strategy chosen to chop off hydra's heads. Moreover, this fact is not provable within Peano Arithmetic.