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）举出数列，利用有关万能数列的定义加以证明．
（2）举出数列，分该排列中不存在数字bi，bi+1满足 bi＜bi+1（1≤i＜n-1）和该排列中存在bi，bi+1满足 bi＜bi+1（1≤i＜n-1两类，利用万能数列的定义加以证明．
（3）利用能数列的定义结合（2）的证明判断出数列为万能数列，再利用万能数列的定义加以证明．
【解析】
（1）     …3分
显然在上述数列中，对于1，2，3，…，n的任意一个排列的第k个位置上的数字，总能在该数列的第k段中找到…4分
（2）…6分
把1，2，3，…，n的一个排列，由左到右构成的数列记作{bk}
①若该排列中不存在数字bi，bi+1满足 bi＜bi+1（1≤i＜n-1），则b1＞b2＞…＞bn
显然这个排列在上述数列中可以找到…7分
②若该排列中存在bi，bi+1满足 bi＜bi+1（1≤i＜n-1，则在上述数列中的第i组留下bi，bi+1，其余的都去掉，其余的各组留下排列中相应的数就可以得到这一排列
综上讨论可得该数列为1，2，3，…，n的万能数列．…9分
（3）数列A是万能数列
由（2）的证明可知，数列A中从首相之后到倒数第二项之前的这些项，是一个关于（1，2，3，…，n-1）的万能数列
所以以n为首项或末项的任何一个排列都可以从数列A中划去一些项而得到
设a1，a2，…，ar，ar+1，…，an是关于自然数1，2，3，…，n的一个排列，且ar=n，1＜r＜n
把数列A中第r个n之前和之后的所有n都划掉，则在含第r个n之前的数为

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