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

2023年南京大学计算机拔尖班二次选拔考试数学试题 第一题(20分) 在黑板上写有2023个1，下面进行2022次如下操作：每次操作擦掉黑板上的任 意两个数a和b,并写下(a+b)或者min{a2+b2},最后只剩下一个数，把这个数 的最大可能值记为.求证： 2003 2023 22<r<32 第二题(20分) 设f是定义域为非零实数、值域为实数的函数，对于x,y,zeR,当z=1时，有 [f(x)P-f(y)f(z)=x(x+y+zXf(x)+f(y)+f(2)). 求满足上述条件的所有函数∫， 第三题(20分) 若定义域和值域均为S={1,2,,n的函数f满足：当x≠y时，f(x)≠f(y),则 称∫为S的“排列函数”，{x,f(x,f(f(x,…x∈S记为f的一个“轨道”， 把f的所有不同的轨道个数记为c(f),(例如，如果n=3,f:S→S定义为 f)=2,f(2)=1,f3)=3,则S的所有不同轨道有1,2}和3，于是c()=2.) 设k>3,n>3,f,…,/为S的k个排列函数，记f(x)=(f(…(f(x)m,证明： c(f)+c(f2)+…+c(f)≤n(k-1)+c(f) 第四题(20分) 对于正整数n,可以把n的所有约数排成一列：d,…,d:·求满足存在n的所有 约数的一个排列，使得d,+d2+…+d,(=1,2,…,k)均为整数的平方的所有正整数 n 2023年南京大学计算机拔尖班二次选拔考试数学试题解答 第一题： 本题是2022年加拿大奥林匹克数学竞寒试题。 (1)假设黑板上有n个1时，执行n一1次上述操作后，剩下的数的最大值为am.则本题取 r=a2023.我们来给出{an}的递推式.可以先列举几个： a1=1,a2=2,ag=3,a4=4,a5=5,a6=9,a7=10,a8=16,ag=17,a10 =25. a11=26,a12=81,a13=82,a14=100,a15=101,a16=256. (2)观察：对于一般的个1的情形，因为最后一次操作是对黑板上的剩下两个数进行操作，而黑板 上剩下两个数必定分别由一开始的i个1和肌一个1执行若干次操作得到，再考虑最大值的情形， 那么我们有 an= max max {ai an-i,minfa,az =1,2,,n-1 =max max,（ai+am-i,.,max =1,2,,n-1 i=1.2.,n-1 in,a吃-} 所以 am≥a1+an-1=1+am-1. 即{am}是严格递增的数列，于是 max minfa?, =1,2,n-1 必定是a1,·,an-1的中位数的平方，所以 2-1mina,听-}= ∫a， n=2k, n=2k+1. 3)再来证明下界估计：我们猜测：am≤3分对n≠1都成立. 我们用第二归纳法证明，当n≥1时，a1≤35。 由(1)，结论对1≤n≤6都成立. 假设当am≤3号对6≤m≤n都成立.下证an+1≤3学.首先，对i=1,2,…,n,有 a,+an+1-4≤3行+3≤3学. 这是因为，对=3，当1≤ 。时 (+xn+1-)-(c+1++1-+）=(3时-3学)+(3学-3学) =3(1-3)+3号(3-1) =(3号-3)3-1)≥0. 所以{r十xn+1-i1≤is号关于弹调递减，因此 3行+3≤3时+3. 下面证明3时+3号≤3学，即证明1+xn≤1xn,即(3号-1)(3宁-1)≥1.当 n≥6时， (32-1)(3-1)=8(3-1)≥1. 这就完成了证明· 另一方面，由于 a晚≤(3)2=3'， 当n+1=2k时，l学=k,晚≤3号=3学，所以 an+1 =max a+a1小学}≤3学. 1=12.,n 当n+1=2k+1时，l"生」=k,候≤3宁=3号<3学，所以 an+1 =max a+a1a学}s3. 综上，用归纳法证明完毕，特别地， r=a2028≤3号， 但是等号不可能成立(r是正整数，3学不是)，所以上界证明完毕 4为了证明下界，我们只需找一个操作方法使得它的最终数大于2学.我们这样操作：首先 2023=337×6+1,我们把每6个1用题中的操作变成9，得到337个9和1个1.然后把256个 9不断用"min{a2,b2}的操作得到128个92、64个92、32个92°、16个92、8个92、4个 92“、2个92”、1个92”.剩下的数很小，在估计时可以放掉.因此 a2028>92=32°=3512=2512og23 因为l0g23= 21og29 21og28=3 ·所以 51210g23>512×,=768>2023 3 =674.33… 这样我们就得到了 a2023>2学. 本题证明完成， 第二题： 解：(1)冷x=y=2=1,可得 [f(1)]2-f1)f1)=9f(1), 得f1