PUMaC 2015 · 组合（B 组） · 第 3 题

PUMaC 2015 — Combinatorics (Division B) — Problem 3

[ 4 ] Princeton’s Math Club recently bought a stock for $2 and sold it for$ 9 thirteen days later. Given that the stock either increases or decreases by $1 every day and never reached$ 0, in how many possible ways could the stock have changed during those thirteen days?

解析

[ 4 ] Princeton’s Math Club recently bought a stock for $2 and sold it for$ 9 thirteen days later. Given that the stock either increases or decreases by $1 every day and never reached$ 0, in how many possible ways could the stock have changed during those thirteen days? Solution: We see that for this to happen, out of the 13 days, the stock price must increase 10 of those days and decrease the other 3 days. The number of arrangements of such days is the same as the number of ways to start at the origin and move to the lattice point (3 , 10) by only ( ) 13 moving one unit to the right or up each step. There are = 286 such ways to do this. 3 However, we counted the case where the stock decreases to less than or equal to $0, which is ( ) 11 not allowed to happen. If the stock goes down the the first two days, there are = 11 1 ways to distribute the last down day. Else, the only way the stock reaches $0 is if the stock values fluctuates as { 2 , 1 , 2 , 1 , 0 } or { 2 , 3 , 2 , 1 , 0 } , in which case for both, there is only one way to distribute the rest of the days. Thus there are 13 cases to subtract. Subtracting those cases, the total number of ways the stock could have changed is 273 . Author: Roy Zhao