Hosted by The Math Forum


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!

Problem of the Week 864

The Ten Implications

_____________________________________________
Spring 98 Archive || MacPOW Home || Math Forum POWs || Search MacPOW
_____________________________________________

Suppose P is a property of natural numbers such that

  1. P[0] is true
  2. 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[10].

    P[0] -> P[1] -> P[2] -> P[3] -> P[4] -> P[5] -> P[6] -> P[7] -> P[8] -> P[9] -> P[10]

    And here is how to get to P[25]: (B) is used five times to prove an auxiliary assertion, (C), which is then used five times.

  3. 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[0] -> P[5] -> P[10] -> P[15] -> P[20] -> P[25]

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.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

The Math Forum

2 October 1998