最少要种多少棵菜

试想有一块NxN的菜地, 为了获得大丰收又能够使投入最小, 希望最初开始种的菜种尽量少而让菜种自由发挥最终充满整个菜地. 一块空地的前后左右四块地上如果有两块或以上已经有了菜种, 那么这块空地也会发芽. 按照如此的生长趋势, 试问如何安放最初的菜种使得最终整块NxN菜地都能够长满菜呢? 开始时最少用几棵菜种呢?

可以发现, 如果在菜地的对角线上放满N棵菜, 就可以使整块菜地最终长满菜. 当然方法不止这一种, 如上图的放法也能够达到目的. 那么N棵菜是否是最少的棵数呢? 结论是肯定的.

如上图, 如果k(=5)阶菜地需要k棵菜才能填满, 那么k+1阶菜地上红色区域至少要有一棵菜才能使此区域最终长满菜, 否则即使k阶子菜地填满, 按照生长规则这一区域也不能长出一棵菜. 因此k+1阶菜地至少需要k+1棵菜. 并且容易说明3阶菜地至少要3棵菜才能长满菜地, 所以归纳假设成立. 嗯, 这只能说是一种解释, 作为证明十分牵强漏洞很大. 不过暂时没有想到很好的巧妙的方法.

来源: cut the knot