Staircase Step Count
A stadium staircase with 150 steps is numbered from 1 to 150. Jan starts on step 130 and steps down to step number 127, then to step number 124, and continues downward to step 13 stepping only on every third step. Jen starts on step number 3 and steps up to step number 7, then to step number 11, and continues upward to step 139 stepping only on every fourth step. How many steps were stepped on by both Jan and Jen (not necessarily at the same time)?
- 1
- 2
- 3
- +
- 4
- 5
- 6
- -
- 7
- 8
- 9
- $\frac{a}{b}$
- .
- 0
- =
- %
- $a^n$
- $a^{\circ}$
- $a_n$
- $\sqrt{}$
- $\sqrt[n]{}$
- $\pi$
- $\ln{}$
- $\log$
- $\theta$
- $\sin{}$
- $\cos{}$
- $\tan{}$
- $($
- $)$
- $[$
- $]$
- $\cap$
- $\cup$
- $,$
- $\infty$
Solution
Jan steps on step number $ s $ if $ 13\leq s \leq 130 $ and $ s $ leaves a remainder of $ 1 $ when divided by $ 3 $. Jen steps on step number $ s $ if $ 3\leq s \leq 139 $ and $ s $ leaves a remainder of $ 3 $ when divided by $ 4 $. Therefore, we are counting the number of integers between $ 13 $ and $ 130 $ which leave a remainder of $ 1 $ when divided by $ 3 $ and a remainder of $ 3 $ when divided by $ 4 $. Let's check the remainders of Jan's first few steps when divided by 4. \[
13 \rightarrow 1
\] \[
16 \rightarrow 0
\] \[
19 \rightarrow 3
\] \[
22 \rightarrow 2
\] \[
25 \rightarrow 1
\] \[
\vdots
\] We see that the remainders of Jan's steps when divided by 4 cycle through the list $ 1,0,3,2 $. Therefore, only every fourth step that Jan steps on will also be stepped on by Jen, so we are counting the number of elements in $ \{19,31,43,\ldots,127\} $. Writing this list in the form \[\{19+0\cdot12,19+1\cdot12,19+2\cdot12,\ldots,19+9\cdot12\},\] we see that $ \boxed{10} $ steps are stepped on by both Jen and Jan.
Note: This problem is essentially an application of the Chinese Remainder Theorem.
Freeflows