阿凡提解金链

国王赏赐阿凡提一条有7个环的金链，但是提出了一个条件：只允许阿凡提切开7个环中的一环，然后每天取走一环，不能多也不能少。如果阿凡提有办法做到，就可以得到金链，如果做不到，它不但得不到金链，还要受处罚。阿凡提是怎么解开这条金链的？

切开第三环，得到1个单环（第三环），1个2连环，1个四连环

第一天拿走单环

第二天用单环换2连环

第三天在拿走单环

第四天用单环+2连环换走四连环

第五天拿走单环

第六天用单环换走2连环

第七天拿走单环

按这个方法，仔细想想吧，每天多拿了一个环，7天拿完了

下面是正确方法，有些图表看不见，我发给你 阿凡提的办法是：把金链的第3环断开，这条金链便分成如图的3节，它们分别是一个单环，一个二连环，一个四连环： 阿凡提第一天取走单环；第二天放回单环而换走那个二连环；第三天再取走单环；第四天把前三天取走的3个环放回而换走四连环；第五天再一次取走单环；第六天又用单环换走二连环；最后第七天取走剩下的那个单环。 阿凡提为什么知道这样做，他的窍门在哪里呢？ 让我们对此题进行分析，先进行横向扫描。如下图所示，如果不计对称性，一根7个环的金链切开一环，不外乎切开第一环，或第二环，或第三环，或第四环四种情况： 如果切开第一环，则将整条金链分成一个单环和一个6连环，阿凡提第二天就无法取走一环了。 如果切开第二环，则将整条金链分成2个单环和一个5连环，阿凡提头两天可分别取走一环，到第三天就无法取走一环了。 如果切开第四环，则将整条金链分成了一个单环和两个3连环，阿凡提在第二天就不能取走一环了。 根据以上分析，唯一可能达到目的的办法就只有切开第三环。经过检验，切开第三环确可以达到目的。这是一种穷举证法，通过横向扫描，发现了解题方法。这种解法不需要太多的预备知识。 现在，我们再利用二进制数的知识，从侧向切入，来解释阿凡提的办法。 因为从1到7的所有正整数都可以用一个不超过三位的二进数来表示，三个数位上的值分别为1，2，4，每个数位上的数字不外乎0与1两种情况。因此，如果我们能把金链分成1环、2环和4环的3节，那么对每一天来说，当我们把当天的天数写成二进数后，数位上的数字是1的，就取走相应的一节，数位上的数字是0时，就不取相应的一节。例如5写成二进数是101，4位上的数字是1，就取走4连环；2位上的数字是0，就不取2连环；个位上的数字是1，即取走单环。这样，对每一天都有方法取得，从而可达到所要求的目的。每天的取法如下表所示： 切开第三环，恰好可以把整条金链分成1环、2环和4环的三节。 通过以上的横向扫描和侧面切入，我们给出了问题的两种解法，但是两个方法都没有触及问题的要害。例如，我们只要将原来的问题稍加推广。 如果允许切开两环，要保证每天可以恰好取走一环，金链最长可以是多少环呢？允许切开三环呢？一般地，允许切开n环又如何呢？ 对于推广后的问题，上述两种解法都无能为力。因为金链的环数不知道，当然不宜使用穷举证法；同样，由于取环的天数不知道，用二进制也无法确定。为了解决推广后的问题，让我们仍旧回到原来的问题，寻求更一般的规律： 其实，道理也很简单。阿凡提只能切开一环，除这一个单环，最多能把这条金链再分成两节。第一天阿凡提只能拿走那个断开了的单环。第二天怎么办呢？不外乎两种可能。 一种是第二天还有一个单环，这样一来，两节中有一节是单环，另一节就只能是一个5连环，第三天，便再也没有办法取走一环了。所以，如果出现这种情况是不行的。 另一种是第二天有一个2连环，阿凡提可拿第一天取走的单环换取这个2连环。两节中有一节是2连环，另一节就只能是4连环了。为了使两节一个是2连环，一个是4连环，唯一的可能就只有在第三环切开。 现在来讨论允许切开n个环的情形。“依约前山似故山”，我们可以把上面关于原问题的分析类比地推广。 把一条金链切开n个环后，除了切开处的n个环是单环外，剩下的最多分成了n+1节。 很明显，第一天，第二天，……一直到第n天，都可以用n个单环来对付。到了第n+1天情况就不同了。可能有两种情况： 一种是其余的各节中最短的一节都多于n+1环，则第n+1天无法再取走一环，这样就达不到要求的目的。 另一种是其余各节中最短的一节不多于n+1环，那末第n+ 1天只要从前面取走的n个单环中退回若干个(即比这最短的一节少一个)再把这一节取走即可。为了使金链最长，这一节可以有n+1个环。 接下去的n天，即从第n+2到第2n+1天，又可用n个单环对付，到第2n+2天，可使其余各节中第二个最短的节有2n+2= 2(n+1)环，则第2n+2天，可将原取走的2n+1个环退回，换取这有2(n+1)环的一节。接下去的2n+1天，即从第2(n+1)+1天到2(n+1)+2n+1天，都可以用退回的2n+1