Advertisement
Guest User

problem

a guest
Oct 1st, 2016
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.60 KB | None | 0 0
  1. Suppose you are given a number n, which represents the height of a flight of steps, and then given the following rules:
  2. 1) You must take at least 2 steps to traverse the stairs;
  3. 2) Each successive step must be less than the previous step
  4. and then told to find the number of possible ways you could traverse this flight of stairs. E.g. when n = 4, you can only take 3 steps then 1 step, so Tn = 1. When n = 5 you can either take 4 steps then 1 step or 3 steps then 2 steps, so Tn = 2.
  5. I initially thought that the height of the first step could only be from (nmin) to (n - 1) where nmin is a the smallest integer k whose triangular integer that is greater than n. (E.g. if given n = 5, then nmin would be 3 because the triangular number of 2 is 3 which is less than 5). As as seen from the previous example, the lowest height of the first step is 3.
  6. I then wrongly deduced that the relation was described as Tn = Σ Ti, where i is from 1 to n - nmin,with a base case of 3 and 4, as T3 and T4 = 1. My reasoning is that if the first step is i steps, then (n - i) steps remain, so my answer should be a sum of all the remaining possibilities for each i.
  7. The problem with my definition is that it ignores the possibility of the second step being higher than the first step, violating rule 2. For example, if I take n = 13, the first steps height will range from [5, 12], so by my definition the sum should be from i = [1, 7]. However, during the summing, when i = 5, again the remaining number of steps to be taken is 7, but T7 also counts the possibility 6 steps then 1 step, which would cause the answer to be one more than it should be.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement