几个简单的数学题

由于N久没有看过数学和写代码了，逻辑思维能力和代码功底已经一塌糊涂了，所以打算每周发点时间在这上面。下面是在看书的过程中看到的几个比较有意思的题目

1.420>422问题
我们有一块如下图所示的边长为20×12的长方形

然后，把这个矩形沿着左上-右下对角线切开，变成两个三角形，把左边的三角形网上移动2cm，变成如下的图片

然后把露出来的两个三角形切掉，并且拼起来，形成如下两个图形

然后我们算面积可得(20+2)19 + 22 = 422,但是原图形的面积是2021=420，怎么突然多出来了呢？原因在哪呢？你知道哪里描述出问题了吗？

问题在于左移2个单位的时候，所得的直角三角形的另外一边只可能比2小，可以由原来的矩形得到一个边的比例额。

2.有一个44的格子，其中有些格子有数字，有一个格子是空的，问有没有可能只通过规定使得从左边的图形变到右边的图形，规定如下：和空格相邻的可以和空格交换位置。

首先我们可以知道这个是不可能的，但是需要证明为什么不可能[就是要寻找一些不变量，然后比较不同状态下这些不变量的情况]，首先我们引入一些辅助概念和变量。

Ⅰ我们定义把空格和左边或者右边的数字交换叫做一次横向移动，把空格和上面或下面的数字交换叫做一次纵向移动

Ⅱ我们把所有的15个数按从上到下，从左到右排成一排，然后得到一个序列S

Ⅲ如果我们横向移动一次的话，S的顺序是不会变的，但是如果我们纵向移动一次的话，就会改变3个数对的顺序，比如上面的左图中如果我们进行一次纵向移动的话，那么就会改变[12,13],[12,15],[12,14]这3个数对的顺序。

Ⅳ我们定义序列S的逆序对数为P，那么我们可以得到如果进行一次横向移动的话P是不会变的（S都没变，P当然没变了），但是进行一次纵向移动的话，P会由奇数变成偶数，反之亦反。

那么我们就可以推出能从左图能到的状态的P的奇偶性和该状态空格所在行的奇偶性相反，因为：首先初始状态的时候，P为1,而空格在第4行，满足条件，然后进行横向移动的话，那么P不变，而且空格的奇偶性也不变，所以满足。如果进行纵向移动的话，那么P的奇偶性会发生改变，同时空格所在行的奇偶性也会发生改变（从奇数到偶数或者相反）。

所以不能从左边的图变到右边的图，因为右边的图中P的奇偶性和空格所在的行的奇偶性相同。

3.一共有N个盒子堆成一列，现在需要把这N个分成N堆，每一堆刚好一个盒子，每次把一堆有a+b个盒子的堆分成两个分别有a个盒子和b个盒子的堆，可以得ab分，现在给定你一个N，问你最多能得到多少分呢？比如下面这个张可以得到45分

元方你怎么看呢？

其实这是个常量，首先不知道的话，你先算几个，然后就会发现了，然后F[n]=(n-1)n/2，这个可以证明的。这里我们用归纳法证明：
1.对于n=1时, f[1] = 01/2 = 0成立
2.假设对于所有的n>0f[n] = (n-1)n/2成立，那么f[n+1]=(n+1)n/2。我们假设n+1分成a和b两堆，那么a+b=n+1.f[a] = a(a-1)/2, f[b] = b(b-1)/2, f[n+1] = f[a]+f[b]+ab = a(a-1)/2 + b(b-1)/2 + ab = (a+b)*(a+b-1)/2满足条件
3.得证

下面是写good proofs的一些tips
一：知道你要用什么方法，并写出来
二：不要跳跃式的推理
三：对每一步都阐述理由
四：不要用过多的符号来表述尼的推理过程
五：尽可能简化你的推理过程
六：引入适当的中间变量
七：对长证明进行结构化
八：不要用“显然成立”等过于简单的词语