对于正整数n，数列a1，a2，…，ak在满足下列条件下称为关于（1，2，3，…，n）的万能数列：自然数1，2，3，…，n的任意一个排列都能从数列a1，a2，…，ak中去掉一些项后得到．（1）构造一

Question

对于正整数n，数列a₁，a₂，…，a_k在满足下列条件下称为关于（1，2，3，…，n）的万能数列：自然数1，2，3，…，n的任意一个排列都能从数列a₁，a₂，…，a_k中去掉一些项后得到．
（1）构造一个有n²项的关于（1，2，3，…，n）的万能数列的例子，并证明；
（2）构造一个有n²-n+1个项的关于（1，2，3，…，n）的万能数列的例子并证明；
（3）判断数列A：是否是关于（1，2，3，…，n）的万能数列，并证明你的结论．

Answer 1

（1）     …3分
显然在上述数列中，对于1，2，3，…，n的任意一个排列的第k个位置上的数字，总能在该数列的第k段中找到…4分
（2）…6分
把1，2，3，…，n的一个排列，由左到右构成的数列记作{b_k}
①若该排列中不存在数字b_i，b_i+1满足 b_i＜b_i+1（1≤i＜n-1），则b₁＞b₂＞…＞b_n
显然这个排列在上述数列中可以找到…7分
②若该排列中存在b_i，b_i+1满足 b_i＜b_i+1（1≤i＜n-1，则在上述数列中的第i组留下b_i，b_i+1，其余的都去掉，其余的各组留下排列中相应的数就可以得到这一排列
综上讨论可得该数列为1，2，3，…，n的万能数列．…9分
（3）数列A是万能数列
由（2）的证明可知，数列A中从首相之后到倒数第二项之前的这些项，是一个关于（1，2，3，…，n-1）的万能数列
所以以n为首项或末项的任何一个排列都可以从数列A中划去一些项而得到
设a₁，a₂，…，a_r，a_r+1，…，a_n是关于自然数1，2，3，…，n的一个排列，且a_r=n，1＜r＜n
把数列A中第r个n之前和之后的所有n都划掉，则在含第r个n之前的数为

因为a₁，a₂，…，a_r-1中最小一项的最大值为n-r+1，
所以由（2）证明可得在上面这组数①中划掉一些项可得a₁，a₂，…，a_r-1
在含第r个n之后的数为
由（2）证明可得，若a_r+1，a_r+2，…，a_n中最小值为1，2，显然a_r+1，a_r+2，…，a_n可以通过划掉一些项得到．
若a_r+1，a_r+2，…，a_n中最小值为大于2，此时a_r+1，a_r+2，…，a_n中最大的数的最小值为n-r+2，
所以由（2）证明可得在上面一组数②中划掉一些项可得a_r+1，a_r+2，…，a_n．
所以数列A是关于（1，2，3，…，n）的万能数列．