One of the joys of hosting the PoW is the chance to show some really beautiful new ideas to you and to my students. #864 is such an example. Enjoy!
Suppose P is a property of natural numbers such that
- P is true
- Whenever P[n] is true, then P[n+1] is true.
You may use the general law of implication [X and X => Y yield Y] ten times only, but -- the catch -- you are NOT allowed to use induction. What is the largest n for which you can prove P[n]?
Two examples should clarify the rules: Here is a proof of P.P -> P -> P -> P -> P -> P -> P -> P -> P -> P -> P
And here is how to get to P: (B) is used five times to prove an auxiliary assertion, (C), which is then used five times.
- For all n, P[n] ==> P[n+5]:
Proof:P[n] -> P[n+1] -> P[n+2] -> P[n+3] -> P[n+4] -> P[n+5]
Now use (C) five times:P -> P -> P -> P -> P -> P
How high a value can you get? Note that the auxiliary assertions are allowed to be complicated!
If you tell me your top value I will tell you if a higher value is possible.
Source: Michael Sheard, St. Lawrence Univ.
Thanks to Sheard and Dan Velleman and John Guilford for their comments on drafts.
© Copyright 1998 Stan Wagon. Reproduced with permission.