Question

信息学奥赛选拔题

在N阶的方针中随机取一个位子（x,y)，并规定x小于等于y，问这个位置上应填的数字是多少？5阶方阵的示意图如下 11 7 4 2 1 16 12 8 5 3 20 17 13 9 6 23 21 18 14 10 25 24 22 19 15

Answer 1

x≤y,即方针中的右上半三角. 第一行从右到左的右上半三角元素是:1 2 4 7 11 第二行从右到左的右上半三角元素是:3 5 8 12 第三行从右到左的右上半三角元素是:6 9 13 第四行从右到左的右上半三角元素是:10 14 第五行从右到左的右上半三角元素是:15 第一行减去1得:0 1 3 6 10,通项是:n(n-1)/2 第二行减去2得:1 3 6 10,通项是:(n+1)n/2, 第三行减去3得:3 6 10,通项是:(n+2)(n+1)/2, 第四行减去4得:6 10,通项是:(n+3)(n+2)/2, 第五行减去5得:10,通项是:(n+4)(n+3)/2, x=0时表示第一行,y=0表示第一列 x=1时表示第二行,y=1表示第二列 ... x=4时表示第五行,y=4表示第五列 对于5阶方阵:n=5-y 所以 第一行减去1得:0 1 3 6 10,通项是:(5-y)(5-y-1)/2 第二行减去2得:1 3 6 10,通项是:(5-y+1)(5-y)/2 第三行减去3得:3 6 10,通项是:(5-y+2)(5-y+1)/2, 第四行减去4得:6 10,通项是:(5-y+3)(5-y+2)/2, 第五行减去5得:10,通项是:(5-y+4)(5-y+3)/2, 即当x=0时通项是:(5-y)(5-y-1)/2 + 1,即(5-y+0)(5-y-1+0)/2 + 1 当x=1时通项是:(5-y+1)(5-y)/2 + 2,即(5-y+1)(5-y-1+1)/2 + 2 当x=2时通项是:(5-y+2)(5-y+1)/2 + 3,即(5-y+2)(5-y-1+2)/2 + 3 ... 当x=4时通项是:(5-y+4)(5-y+3)/2 + 5,即(5-y+4)(5-y-1+4)/2 + 5 所以通项是:(5-y+x)(5-y-1+x)/2 + (x+1) 对于N阶方阵的通项是(N-y+x)(N-y+x-1)/2 + (x+1) 所以对于任意取(x,y),x≤y,这个位置上的数字是(N-y+x)(N-y+x-1)/2 + (x+1) 验证:对于5阶方阵: 当x=0,y=0时(N-y+x)(N-y+x-1)/2 + (x+1)=(5-0+0)(5-0+0-1)/2 + (0+1)=11正确. 当x=2,y=3时(N-y+x)(N-y+x-1)/2 + (x+1)=(5-3+2)(5-3+2-1)/2 + (2+1)=9正确.