一只青蛙在坐标平面的原点。从点 $\left( x\text{,}y \right)$ 出发，青蛙可以跳到 $\left( x+1\text{,}y \right)\text{,}\left( x+2\text{,}y \right)\text{,}\left( x\text{,}y+1 \right)\text{,}\left( x\text{,}y+2 \right)$ 四点中的任一点。求起点为 $\left( \text{0,0} \right)$ 终点为 $\left( \text{4,4} \right)$ 的不同的跳跃序列数
【难度】
【出处】
2018年第36届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
556
【解析】
我们令 $s\text{=}x+y$，则青蛙每跳一次 $s$ 值增加 $1$ 或 $2$ 。因为 $\left(4+4 \right)-\left( 0+0 \right)\text{=}8$，所以青蛙最少跳 $\frac{8}{2}\text{=}4$ 步，最多跳 $\frac{8}{1}\text{=}8$ 步。设四种跳法各跳了 $a\text{,}b\text{,}c\text{,}d$ 步。则 $a+2b\text{=}4\text{,}c+2d\text{=}4$
1．$a+b+c+d\text{=}4\Rightarrow b+d\text{=}4\text{,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。易知 $b\text{=}d\text{=}2\text{,}a\text{=}c\text{=}0$ 。所以共有跳法 $C_{4}^{2}\text{=}6$ 种。
2．$a+b+c+d\text{=5}\Rightarrow b+d\text{=3,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。 $\left\{ \begin{matrix}
a\text{=}2 \\
b\text{=}1 \\
c\text{=}0 \\
d\text{=}2 \\
\end{matrix} \right.$ 或 $\left\{ \begin{matrix}a\text{=0} \\
b\text{=2} \\
c\text{=2} \\
d\text{=1} \\
\end{matrix}\right.$，所以共有跳法 $2\cdot C_{5}^{2}\cdot C_{3}^{1}=60$ 种。
3．$a+b+c+d\text{=6}\Rightarrow b+d\text{=2,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。 $\left\{ \begin{matrix}
a\text{=4} \\
b\text{=0} \\
c\text{=}0 \\
d\text{=}2 \\
\end{matrix} \right.\text{,}\left\{ \begin{matrix}a\text{=}2 \\
b\text{=}1 \\
c\text{=2} \\
d\text{=1} \\
\end{matrix} \right.\text{,}\left\{ \begin{matrix}a\text{=0} \\
b\text{=2} \\
c\text{=4} \\
d\text{=0} \\
\end{matrix}\right.$，所以共有跳法 $C_{6}^{4}+C_{6}^{2}\cdot C_{4}^{1}\cdot C_{3}^{2}+C_{6}^{4}=15+180+15\text{=21}0$ 种。
4．$a+b+c+d\text{=7}\Rightarrow b+d\text{=1,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。 $\left\{ \begin{matrix}
a\text{=}2 \\
b\text{=}1 \\
c\text{=4} \\
d\text{=0} \\
\end{matrix} \right.\text{,}\left\{ \begin{matrix}a\text{=4} \\
b\text{=0} \\
c\text{=2} \\
d\text{=1} \\
\end{matrix}\right.$，共有跳法 $2\cdot C_{7}^{4}\cdot C_{3}^{3}=2\cdot 35\cdot 3\text{=21}0$ 种。
5．$a+b+c+d\text{=8}\Rightarrow b+d\text{=0,}a\text{=}c\text{=}4$ 。共有跳法 $C_{8}^{4}=70$ 种。
一共有 $6+60+210+210+70\text{=}556$ 种
1．$a+b+c+d\text{=}4\Rightarrow b+d\text{=}4\text{,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。易知 $b\text{=}d\text{=}2\text{,}a\text{=}c\text{=}0$ 。所以共有跳法 $C_{4}^{2}\text{=}6$ 种。
2．$a+b+c+d\text{=5}\Rightarrow b+d\text{=3,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。 $\left\{ \begin{matrix}
a\text{=}2 \\
b\text{=}1 \\
c\text{=}0 \\
d\text{=}2 \\
\end{matrix} \right.$ 或 $\left\{ \begin{matrix}a\text{=0} \\
b\text{=2} \\
c\text{=2} \\
d\text{=1} \\
\end{matrix}\right.$，所以共有跳法 $2\cdot C_{5}^{2}\cdot C_{3}^{1}=60$ 种。
3．$a+b+c+d\text{=6}\Rightarrow b+d\text{=2,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。 $\left\{ \begin{matrix}
a\text{=4} \\
b\text{=0} \\
c\text{=}0 \\
d\text{=}2 \\
\end{matrix} \right.\text{,}\left\{ \begin{matrix}a\text{=}2 \\
b\text{=}1 \\
c\text{=2} \\
d\text{=1} \\
\end{matrix} \right.\text{,}\left\{ \begin{matrix}a\text{=0} \\
b\text{=2} \\
c\text{=4} \\
d\text{=0} \\
\end{matrix}\right.$，所以共有跳法 $C_{6}^{4}+C_{6}^{2}\cdot C_{4}^{1}\cdot C_{3}^{2}+C_{6}^{4}=15+180+15\text{=21}0$ 种。
4．$a+b+c+d\text{=7}\Rightarrow b+d\text{=1,}a\text{=}4-2b\text{,}c\text{=}4-2d$ 。 $\left\{ \begin{matrix}
a\text{=}2 \\
b\text{=}1 \\
c\text{=4} \\
d\text{=0} \\
\end{matrix} \right.\text{,}\left\{ \begin{matrix}a\text{=4} \\
b\text{=0} \\
c\text{=2} \\
d\text{=1} \\
\end{matrix}\right.$，共有跳法 $2\cdot C_{7}^{4}\cdot C_{3}^{3}=2\cdot 35\cdot 3\text{=21}0$ 种。
5．$a+b+c+d\text{=8}\Rightarrow b+d\text{=0,}a\text{=}c\text{=}4$ 。共有跳法 $C_{8}^{4}=70$ 种。
一共有 $6+60+210+210+70\text{=}556$ 种
答案
解析
备注
