2023年南京大学计算机拔尖班二次选拔考试（数学部分） .pdf

2023年南京大学计算机拔尖班二次选拔考试数学试题

第一题(20分)

在黑板上写有2023个1,下面进行2022次如下操作：每次操作擦掉黑板上的任

意两个数。和人，并写下(。+人)或者血｛。2+//｝,最后只剩下一个数，把这个数

的最大可能值记为尸・求证：

20232023

Er?Tr

第二题(20分)

设f是定义域为非零实数、值域为实数的函数，对于x,y,zeK,当母z=l时，有

[f⑴]之—/(y)/(z)=x(x+y+z)(/(x)+/(y)+/(z)).

求满足上述条件的所有函数f・

第三题(20分)

若定义域和值域均为5=｛1,2,.../｝的函数f满足：当时，/(%)f(y),则

称f为S的“排列函数”，｛x,f(x),f(f(x)),｝(xgf的一个“轨道”，

把f的所有不同的轨道个数记为c(f).(例如，如果n=3,f:S^S定义为

/(1)=2/(2)=1/(3)=3,拓的所有不同轨道有｛1,2｝和｛3｝,于是c(f)=2.)

设k3,n3・,，fk为S的)个排列函数,记f⑴=方(为(…(九⑴)))，证明:

c(k)+c(£)c(fQVn(^-l)+c(/)

第四题（20分）

对于正整数〃，可以把〃的所有约数排成一列：四,・・握广求满足存在〃的所有

约数的一个排列，使得《+%+•••+《。=12•••*）均为整数的平方的所有正整数

n・

2023年南京大学计算机拔尖班二次选拔考试数学试题解答

第一题：

本题是2022年加拿大奥林匹克数学竞寒试题・

⑴假设黑板上有n个1时,执行n—1次上述操作后，剩下的数的最大值为Q”.则本题取

r=Q2023•我们来给出{如}的遂推式.可以先列举几个：

Qi=1,=2,Q3=3,Q4=4,«5=5,=9,Q7=10,ag=16,ag=17,Q10

=25.

an=26,ai2=81,ai3=82,44=100,=101,=256.

⑵观察：对于一般的n个1的情形，因为最后一次操作是对黑板上的剩下两馋进行操作，而黑板

上剩下两个数必定分别由TF始的2个1和n—匕个1执行若干次操作得到.再考虑最大值的情形，

那么我们有

an=maxmax{a,+,min{a?,•}}

=maxmax（a（+q“t）,maxmin{a?,a^-}

U=12・・,n-1£=1,2,・•J

所以

QnN+Qn-1=1+1•

即{。曷是严格递增的数列.于是

maxmin{a?,a^-}

i=L2,..,”iin~lS

必定是Q1，•--,ani的中位数的平方.所以

72■―2k,

max己-

n=2fc+1.

⑶再来证明下界估计:我们猜测：如3夸对n/1都成立.

我们第二归纳法证明，当n1时，Qn它3夸・

由⑴,结论对1n6都成立・

m允+1

假设当Qm3号对6Vm气n都成立，下证如+i3—.首先