20130922 阿里巴巴 笔试题 最后一题 消数字 - Tristan's blog
题目描述：
在黑板上写下50个数字：1到50.在接下来的49轮操作中，每次做如下动作：选取黑板上的两个数字a和b，擦去，写上|a-b|。请问最后一次动作之后，剩余的数字可能是什么？
答案
1到50之间所有的奇数
分析
题目一拿上来，感觉无从下手，老是想用数论的知识或者DP之类的方法迅速搞定。这种类型的题目（互联网公司常考的数学题、算法题）或者从纯计算机的思维来考虑（DP、分治、贪心、深搜、广搜等），或者从数学角度来考虑（数学归纳法，反证法，数字之间的关系、数字的特征、转变为几何问题等）。此题目我们从最基础的数学归纳法的角度来考虑。
当只有 1,2两个数字时，黑板上只能留下1
当有1,2,3,4时，黑板上可能留下0,2,4
当有1,2,3,4,5,6,时，黑板上可能留下1,3,5
当有1，2,3,4,5,6,7,8时，黑板上可能留下0,2,4,6,8
由以上规律，我们假设：黑板上有1-2*n个数字，当n为奇数时，黑板上可能留下的数字为1到2*n-1之间的所有奇数；当n为偶数时，黑板上留下的是0到2*n之间所有的偶数。
由于25(50/2)属于奇数，我们先只考虑奇数的问题。
当n=1时，显然成立
假设当n=k时（k为奇数），1,2,3…..2*k满足假设（也就是黑板上可能剩下1到k之间所有的奇数）
则当n=k+2时，黑板上可能存在的数字"一定"包括（这里很矛盾，"可能"并且"一定"，"可能"是指黑板上可能留下的数字，这是一个总的集合，而"一定"是指这个总的集合里面一定包含某些数字，当然，这个总的集合也可能包含其它数字，比如偶数）先前的1到2*k-1之间所有的奇数，因为这时总的序列是1,2,3….2k,2k+1,2k+2,2k+3,2k+4，只要我们先把2k+2和2k+1去掉，留下1，然后把2k+3与2k+4去掉留下1，再把两个1去掉，得到0，前面2k个按照上一轮的操作得到1到2*k-1之间所有的奇数即可。想得到2*k+1的话，就让前2k个剩下2k-1，然后用2k+4减去2k+3,得到1,2k+1再减去1得到2k，然后2k减去前2k个剩下的2k-1，得到1，然后用2k+2减去1得到最终的2k+1；同理，可以得到2k+3.
以此，得证部分结论：黑板上有1-2*n个数字，当n为奇数时，黑板上可能留下的数字包含1到2*n-1之间的所有奇数
证明充分必要性
根据题意我们可以得知，最后剩下的数字肯定是0到2n之间的数字，因为绝对值不会出现负数，而非负数之间差的绝对值不会大于做运算的其中任意一个数字。所以，我们可以得知，黑板上最多存在0到2n的数字。那么，如何知道剩下的肯定不是偶数呢？
这里我们根据奇数和偶数之间的运算一堆奇数和偶数做减法，奇数与奇数相减，得到的是偶数，因此奇数的总数目减2；奇数与偶数相减，得到的还是奇数，奇数的总数目不变。也就是说，奇数的总个数的奇偶性不发生变化。因为n是奇数，代表奇数的个数是奇数，因为最后肯定只剩下一个数字，所以剩下的只可能是奇数。
充分必要性得证。
同理，偶数的情况也可以得证
Read full article from 20130922 阿里巴巴 笔试题 最后一题 消数字 - Tristan's blog
题目描述：
在黑板上写下50个数字：1到50.在接下来的49轮操作中，每次做如下动作：选取黑板上的两个数字a和b，擦去，写上|a-b|。请问最后一次动作之后，剩余的数字可能是什么？
答案
1到50之间所有的奇数
分析
题目一拿上来，感觉无从下手，老是想用数论的知识或者DP之类的方法迅速搞定。这种类型的题目（互联网公司常考的数学题、算法题）或者从纯计算机的思维来考虑（DP、分治、贪心、深搜、广搜等），或者从数学角度来考虑（数学归纳法，反证法，数字之间的关系、数字的特征、转变为几何问题等）。此题目我们从最基础的数学归纳法的角度来考虑。
当只有 1,2两个数字时，黑板上只能留下1
当有1,2,3,4时，黑板上可能留下0,2,4
当有1,2,3,4,5,6,时，黑板上可能留下1,3,5
当有1，2,3,4,5,6,7,8时，黑板上可能留下0,2,4,6,8
由以上规律，我们假设：黑板上有1-2*n个数字，当n为奇数时，黑板上可能留下的数字为1到2*n-1之间的所有奇数；当n为偶数时，黑板上留下的是0到2*n之间所有的偶数。
由于25(50/2)属于奇数，我们先只考虑奇数的问题。
当n=1时，显然成立
假设当n=k时（k为奇数），1,2,3…..2*k满足假设（也就是黑板上可能剩下1到k之间所有的奇数）
则当n=k+2时，黑板上可能存在的数字"一定"包括（这里很矛盾，"可能"并且"一定"，"可能"是指黑板上可能留下的数字，这是一个总的集合，而"一定"是指这个总的集合里面一定包含某些数字，当然，这个总的集合也可能包含其它数字，比如偶数）先前的1到2*k-1之间所有的奇数，因为这时总的序列是1,2,3….2k,2k+1,2k+2,2k+3,2k+4，只要我们先把2k+2和2k+1去掉，留下1，然后把2k+3与2k+4去掉留下1，再把两个1去掉，得到0，前面2k个按照上一轮的操作得到1到2*k-1之间所有的奇数即可。想得到2*k+1的话，就让前2k个剩下2k-1，然后用2k+4减去2k+3,得到1,2k+1再减去1得到2k，然后2k减去前2k个剩下的2k-1，得到1，然后用2k+2减去1得到最终的2k+1；同理，可以得到2k+3.
以此，得证部分结论：黑板上有1-2*n个数字，当n为奇数时，黑板上可能留下的数字包含1到2*n-1之间的所有奇数
证明充分必要性
根据题意我们可以得知，最后剩下的数字肯定是0到2n之间的数字，因为绝对值不会出现负数，而非负数之间差的绝对值不会大于做运算的其中任意一个数字。所以，我们可以得知，黑板上最多存在0到2n的数字。那么，如何知道剩下的肯定不是偶数呢？
这里我们根据奇数和偶数之间的运算一堆奇数和偶数做减法，奇数与奇数相减，得到的是偶数，因此奇数的总数目减2；奇数与偶数相减，得到的还是奇数，奇数的总数目不变。也就是说，奇数的总个数的奇偶性不发生变化。因为n是奇数，代表奇数的个数是奇数，因为最后肯定只剩下一个数字，所以剩下的只可能是奇数。
充分必要性得证。
同理，偶数的情况也可以得证
Read full article from 20130922 阿里巴巴 笔试题 最后一题 消数字 - Tristan's blog
