一个游戏

??????不知道屏幕前的你是否也玩过这样的一个游戏，在游戏里，你可以将两个低等级的单元可以合成为一个次高等级的单元，而两个次高等级的单元可以合成为一个高等级的单元，而这样的合成游戏中，往往也会具有网格的限制，每一个单元都会占据一个网格，而总的网格是有限的，并且在网格中添加单元时，只能添加最低的等级的单元。那总的网格数与我们单元的最高等级之间是否有一定的数学关系呢？想必是有的，先来带大家看一下我最近玩过的一款游戏，是一款合成恐龙的游戏。
在这里插入图片描述

这张图片就表现出了网格的概念，每一个单元占据一个网格，而一共有 $15$ 个网格，并且每两个同等级的单元可以合成为一个高等级的单元。

问题分析与解决

分析

??????遇到了逢二进一的问题，我们首先就会想到二进制的问题。的确，我们在探究一个有 $15$ 个网格可以放置的最大的单元等级是多少的问题时，我们可以采取这样的思路，将我们的操作分成了两个操作：添加操作与融合操作。添加操作即每次往这些网格中放置一个最低等级的单元（这也是问题的一个限制），融合操作为将满足融合条件（同一等级的单元数量大于等于 $2$ ）的单元进行融合。并且，为了最大化我们的网格空间，我们将融合操作的优先级放到添加操作的前面。我们前面提到，这样的一个问题是一个二进制逢二进一的问题，即完全可以将这个问题看作一个二进制计数的问题。

抽象

??????按照我们上述的规定，融合操作优先级大于放置操作优先级，那这个问题已经转化为了一个二进制计数的问题。我们先把网格数量减少到 $3$ 。我们先添加一个最低单元，二进制数代表为 $（ 1 ）$ 。此时没有满足融合条件，我们继续添加。现在有两个最低等级的单元，但还没有融合，我们找不到一个合适的二进制数对其进行表示，我们规定一个二进制数 $（ 02 ? ）$ ，这里的 $^{'} ?^{'}$ 代表的是逢二已满，但没有进位的中间态。此时，占据的网格数量是2，然后进行融合操作，融合为一个高等级的单元，对应的二进制数代表为 $（ 10 ）$ ，占据一个网格。
??????如果想融合成一个等级为三的单元，我们需要几个一级单元呢？很明显是 $4$ 个，那 $4$ 个等级为一的单元是如何被放置在这些网格上的呢？很明显在之前 $（ 10 ）$ 的基础上，又增添了两个，随后变成了 $（ 12 ? ）$ ，再次融合变成 $（ 2 ? 0 ）$ ，再次融合变成 $（ 100 ）$ 。
??????即融合成一个三级的单元，需要至少三个网格，我们这里的网格数定义为二进制数上的每一位代表的数量之和，即所需要的最少的网格数等于在整个添加、融合过程中二进制数上每一位之和的最大值（包括中间态），在二进制合成游戏下，我们想融合一个等级为 $N$ 的单元，至少需要 $N$ 个网格。

拓展

??????倘若存在三进制的单元游戏，或者多进制的单元合成游戏（ $M$ 进制），那生成一个等级为 $N$ 的单元至少需要多少个网格呢。倘若生成等级为 $N$ 的单元，可知其对应的 $M$ 进制数的第 $N$ 位应该为零，从第一位到第 $（ N ? 1 ）$ 位，都不为 $0$ 。并且首位为 $M$ ，其余位为 $(M ? 1)$ ，即所占据的网格数量为： $(M + (N ? 2) (M ? 1)) = (M N ? M ? N + 2)$ ，将 $M = 2$ 代入可得在二进制下，这个关系为 $N$ 。