All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Odd steps (Posted on 2013-05-08) Difficulty: 3 of 5
Find the number of different ways to climb a staircase with n stairs using steps of odd sizes only.
Disregard the physical limitations of step's size.

Case 1: The order of the steps is relevant.
Case 2: The order of the steps is irrelevant.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution Comment 1 of 1

DECLARE SUB takeStepA (wh!)
DECLARE SUB takeStep (wh!)
CLEAR , , 25000
DIM SHARED h(100), ways, n, tot
CLS
FOR n = 1 TO 30
  ways = 0: tot = 0
  takeStep 1
  PRINT n, ways
NEXT n
STOP
PRINT
FOR n = 1 TO 30
  ways = 0: tot = 0
  takeStepA 1
  PRINT n, ways
NEXT n

SUB takeStep (wh)
  FOR stSize = 1 TO n - tot STEP 2
    tot = tot + stSize
    h(wh) = stSize

    IF tot = n THEN
       ways = ways + 1
    ELSE
       takeStep wh + 1
    END IF

    tot = tot - stSize
  NEXT
END SUB

SUB takeStepA (wh)
  IF wh = 1 THEN st = 1:  ELSE st = h(wh - 1)
  FOR stSize = st TO n - tot STEP 2
    tot = tot + stSize
    h(wh) = stSize

    IF tot = n THEN
       ways = ways + 1
    ELSE
       takeStepA wh + 1
    END IF

    tot = tot - stSize
  NEXT

END SUB

In Case 1, the resulting numbers are the Fibonacci numbers:

steps          ways
 1             1
 2             1
 3             2
 4             3
 5             5
 6             8
 7             13
 8             21
 9             34
 10            55
 11            89
 12            144
 13            233
 14            377
 15            610
 16            987
 17            1597
 18            2584
 19            4181
 20            6765
 21            10946
 22            17711
 23            28657
 24            46368
 25            75025
 26            121393
 27            196418
 28            317811
 29            514229
 30            832040


 
In Case 2, the numbers are less familiar:


 
 1             1
 2             1
 3             2
 4             2
 5             3
 6             4
 7             5
 8             6
 9             8
 10            10
 11            12
 12            15
 13            18
 14            22
 15            27
 16            32
 17            38
 18            46
 19            54
 20            64
 21            76
 22            89
 23            104
 24            122
 25            142
 26            165
 27            192
 28            222
 29            256
 30            296
 

Sloane's OEIS finds A000009 as fitting these numbers.


  Posted by Charlie on 2013-05-08 17:40:00
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information