# Showing the Necessity of Proving the Impossibilities

"It's impossible because I tried but couldn't do it!" I need situations which shows that this kind of reasoning above is not working!

I do have an example, but look for more: It's so hard to cover a $6\times 10$ rectangle by pentominos (I hope no student would manage to do it), but actually possible in hundreds of ways!

• This seems very broad. Couldn't the emphasized text be said of many [existence] problems that students are unable to resolve? One example that comes to mind: Finding a counting number for which $n^2 - n + 41$ is composite. Students will try examples beginning at $n=1$ (or even $n=0$) and continue until it becomes tedious, at which point they declare it impossible i.e. claim the output is always prime. Dec 5, 2016 at 5:54

Here is a nice one which I am surprised wasn't posted yet:

$\text{Prove }n^{17}+9 \text{ and } (n+1)^{17}+9 \text{ are not relatively prime for all n }$ by giving a counter example.

The first counterexample is $n=8424432925592889329288197322308900672459420460792433$.

That ought to keep your students trying for a while :)

• +1 for being evil.
– DRF
Dec 6, 2016 at 9:41
• Is there an elementary argument that this is the first counterexample? I am not seeing it. Or was it just found by brute force? Mar 7, 2018 at 20:08

I will reuse something I already answered another question with. I think the problem you describe will likely come up in a circumstances when we, as teachers, state and prove something is impossible (usually, an equation has no solution). It is often difficult to have students understand how such a proof is relevant, and the best way I can think of is to design a problem which is very close to the one at hand, with no obvious solution, but yet with some solution. I am not sure a general list is so useful, so I'll just pick one example.

Imagine you discussed the irrationality of $\sqrt{2}$. In other words, you discussed the impossibility to solve $p^2=2q^2$ in integers. If some students feel it obvious that there could not be a solution, then propose them the equation (also to be solved in integers) $p^2=12 q^3$. It is not obvious to find a solution when one is not familiar with the decomposition into primes, but of course $(p,q)=(18,3)$ does the job.

An old professor of mine made this point by repeated reference to aviation skeptics / skepticism. Up to a certain point in history, engineers were able to point to any number of failed attempts at machines that produced sustained flight, and no successful attempts.

A student who fails to produce example that satisfies some set of conditions and then decides that no such thing can satisfy these conditions is like an engineer who has built or observed many crashing airplanes, and decided that a flying machine cannot be built.

The question reminds of the story told about Gauss and his discovery of the constructibiliy of the 17-gon. As a young person, Gauss made the discovery and approached his professor. The professor (Kastner) dismissed Gauss because after all, the subject of straightedge and compass construction was settled since the time of the ancient Greeks. If more could be known, then over the centuries, smart people would have made the discoveries. So the construction must be impossible. What could a teenager possibly contribute?