Solution
Strides of Any Length
Show the problem again
A staircase has 10 steps. You start at the bottom (step 0) and must finish exactly on step 10. Each stride carries you up any positive whole number of steps (1, 2, 3, ..., or all 10 at once). Climbs are different if their sequences of strides differ. How many different climbs are there? Give an integer.
Worked solution
**Answer: 512.** A climb is completely determined by the set of intermediate steps you stand on. Each of steps 1 through 9 is either a landing point or not, independently, and every such choice gives a valid climb. Hence there are 2^9 = 512 climbs. Equivalently, this counts the compositions (ordered sums) of 10, and there are 2^(n−1) compositions of n: think of n ones in a row with n − 1 gaps, each gap either a "plus" or a "comma".
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.