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

 Odd steps (Posted on 2013-05-08)
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.)
 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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: