现将一组多米诺骨牌中的每一块均以一对有序的不同的正整数表示，并将这些骨牌以下列顺序排列：从第二块骨牌开始，每一块骨牌的 $x$ 坐标值均等于其前一块骨牌的 $y$ 坐标值．不存在表示为 $\left( i, j \right)$，$\left( j ,i \right)$ 的两块骨牌．设 ${{D}_{40}}$ 为一组坐标值不大于40的多米诺骨牌，求以此种方法排列的骨牌组 ${{D}_{40}}$ 的最大长度．
【难度】
【出处】
1998年第16届美国数学邀请赛（AIME）
【标注】
【答案】
761
【解析】
对于骨牌 $\left( {{i}_{1}} ,{{j}_{1}} \right)$，$\left({{j}_{1}}, {{j}_{2}} \right)$，$\left( {{j}_{2}} ,{{j}_{3}} \right)$，$\left({{j}_{3}} ,{{j}_{4}} \right)$，$\cdots$，构造序列 ${{i}_{1}}{{j}_{1}}{{j}_{2}}{{j}_{3}}{{j}_{4}}\cdots $，同样地，我们由序列 ${{i}_{1}}{{j}_{1}}{{j}_{2}}{{j}_{3}}{{j}_{4}}\cdots$ 可构造骨牌 $\left( {{i}_{1}} ,{{j}_{1}} \right)$，$\left({{j}_{1}} ,{{j}_{2}} \right)$，$\left( {{j}_{2}} ,{{j}_{3}} \right)$，$\left({{j}_{3}} ,{{j}_{4}} \right)$，$\cdots$．
由于 $\left( i ,j\right)$ 与 $\left( j i \right)$ $\left( i\ne j \right)$ 不会同时出现，故 ${{D}_{40}}$ 中的骨牌数不多于 $\text{C}_{40}^{2}$，且当骨牌数为 $\text{C}_{40}^{2}$ 时，每个数恰出现39次．由于 ${{D}_{40}}$ 的排列所对应的序列中除首尾两项外，其余每项均计算两次，故至多只有两个数出现奇数次，从而骨牌数目不多于 $\text{C}_{40}^{2}-\left( \frac{40}{2}-1 \right)=761$．
下面证明 ${{D}_{40}}$ 的最大长度为761．事实上，首先由序列 $1231$ 变成412431，再将412431变为54124315235，其次，对于已构造好的含 $2n+1\left(n\geqslant 2 \right)$ 个不同数且长度为 $C_{2n+1}^{2}+1$ 的序列，且该序列首尾两项均为 $2n+1$，我们在首项 $2n+1$ 前加入 $2n+2$，并将1，2，$\cdots$ $2n$ 两两配成 $n$ 组，在构造好的序列中找出这样的 $n$ 组，且每组的两数的序列中相邻，在每组的两数前插入 $2n+2$，此时便得到一个新序列 $A$，$A$ 的长度为 $\text{C}_{2n+1}^{2}+1+\left( n+1 \right)$．对于 $A$，设插入前，两两配成 $n$ 组的数为 $\left({{i}_{1}}, {{j}_{1}} \right)$，$\left( {{i}_{2}}, {{j}_{2}} \right)$，$\cdots$，$\left({{i}_{n}} ,{{j}_{n}} \right)$，于是将 $A$ 变为
$\left(2n+3 \right)A\left( 2n+3 \right){{i}_{1}}{{j}_{1}}\left( 2n+3\right){{i}_{2}}{{j}_{2}}\left( 2n+3 \right)\cdots \left( 2n+3\right){{i}_{n}}{{j}_{n}}\left( 2n+3 \right)$．
由于 $A$ 的首、末两项分别为 $2n+2$ 及 $2n+1$，又 ${{i}_{1}}$，${{j}_{1}}$，${{i}_{2}}$，${{j}_{2}}$ $\cdots$，${{i}_{n}}$，${{j}_{n}}\in\left\{ 1, 2 ,\cdots ,2n \right\}$，故不会出现 $\left( i,j \right)$，$\left( j,i \right)$ $\left( i\ne j \right)$ 同存在于序列中的情形，此时新序列含 $2n+3$ 个不同数，长为 $\text{C}_{2n+1}^{2}+1+\left( n+1\right)+2n+n+2=\text{C}_{2n+3}^{2}+1$，且首尾两项均为 $2n+3$．
重复上述构造，最终可得含40个不同数，且长度为 $\text{C}_{39}^{2}+1+20=762$ 的序列，其对应一个761个骨牌的 ${{D}_{40}}$ 排列．
综上所述，${{D}_{40}}$ 的最大长度为 $761$．
由于 $\left( i ,j\right)$ 与 $\left( j i \right)$ $\left( i\ne j \right)$ 不会同时出现，故 ${{D}_{40}}$ 中的骨牌数不多于 $\text{C}_{40}^{2}$，且当骨牌数为 $\text{C}_{40}^{2}$ 时，每个数恰出现39次．由于 ${{D}_{40}}$ 的排列所对应的序列中除首尾两项外，其余每项均计算两次，故至多只有两个数出现奇数次，从而骨牌数目不多于 $\text{C}_{40}^{2}-\left( \frac{40}{2}-1 \right)=761$．
下面证明 ${{D}_{40}}$ 的最大长度为761．事实上，首先由序列 $1231$ 变成412431，再将412431变为54124315235，其次，对于已构造好的含 $2n+1\left(n\geqslant 2 \right)$ 个不同数且长度为 $C_{2n+1}^{2}+1$ 的序列，且该序列首尾两项均为 $2n+1$，我们在首项 $2n+1$ 前加入 $2n+2$，并将1，2，$\cdots$ $2n$ 两两配成 $n$ 组，在构造好的序列中找出这样的 $n$ 组，且每组的两数的序列中相邻，在每组的两数前插入 $2n+2$，此时便得到一个新序列 $A$，$A$ 的长度为 $\text{C}_{2n+1}^{2}+1+\left( n+1 \right)$．对于 $A$，设插入前，两两配成 $n$ 组的数为 $\left({{i}_{1}}, {{j}_{1}} \right)$，$\left( {{i}_{2}}, {{j}_{2}} \right)$，$\cdots$，$\left({{i}_{n}} ,{{j}_{n}} \right)$，于是将 $A$ 变为
$\left(2n+3 \right)A\left( 2n+3 \right){{i}_{1}}{{j}_{1}}\left( 2n+3\right){{i}_{2}}{{j}_{2}}\left( 2n+3 \right)\cdots \left( 2n+3\right){{i}_{n}}{{j}_{n}}\left( 2n+3 \right)$．
由于 $A$ 的首、末两项分别为 $2n+2$ 及 $2n+1$，又 ${{i}_{1}}$，${{j}_{1}}$，${{i}_{2}}$，${{j}_{2}}$ $\cdots$，${{i}_{n}}$，${{j}_{n}}\in\left\{ 1, 2 ,\cdots ,2n \right\}$，故不会出现 $\left( i,j \right)$，$\left( j,i \right)$ $\left( i\ne j \right)$ 同存在于序列中的情形，此时新序列含 $2n+3$ 个不同数，长为 $\text{C}_{2n+1}^{2}+1+\left( n+1\right)+2n+n+2=\text{C}_{2n+3}^{2}+1$，且首尾两项均为 $2n+3$．
重复上述构造，最终可得含40个不同数，且长度为 $\text{C}_{39}^{2}+1+20=762$ 的序列，其对应一个761个骨牌的 ${{D}_{40}}$ 排列．
综上所述，${{D}_{40}}$ 的最大长度为 $761$．
答案
解析
备注
