2026年国际数学奥林匹克中国国家集训队测试一第二天试题+答案

2026年国际数学奥林匹克中国国家集训队测试一第二天试题题1．给定简单图G=V,E，其中V={x,y,z∣x,y,z∈ℤ3,1≤x,y,z≤2026}v题2．求满足下述条件的最小整数k：可将2026阶完全图K2026的每条边标记1,2,…,20262之一，每个数恰使用一次题3．设数列ai满足a1=2，对n≥2,an是不整除k=1n−1n−k+ak的最小质数i2026年国际数学奥林匹克中国国家集训队测试一第二天试题解答题1．给定简单图G=V,E，其中V={x,y,z∣x,y,z∈ℤ3,1≤x,y,z≤2026}，v证明．记N=2026，我们证明题目中的6677可以改进为3N．对顶点u=x,y,z,w=x′,y′,zf这里lenPu,w为路径Pu因为V=N3，且v∈V​ff对u∈u对每条边e，设me表示使得e∈Pu,w的有序顶点对u,w的个数，则上式表明对于平行于x轴的边e=a,b,c,a+1,b,c，路径Pu,w包含边e的充要条件是x对于平行于y轴的边e=a,b,c,a,b+1,c，路径Pu,w包含边e的充要条件是y对于平行于z轴的边e=a,b,c,a,b,c+1，路径Pu,w包含边e的充要条件是z因此总有me≤N题2．求满足下述条件的最小整数k：可将2026阶完全图K2026的每条边标记1,2,…,20262之一，每个数恰使用一次解答：k的最小值是3962．我们称一条道路的权重为其上所有边的标数之和．取最小的正整数m∈20264050不难得到m=首先给出构造：设K2026的顶点为u,v1,v2,…,v2025，标记方式如下：对k=1,2,…,2025，边uvk标数k；将满足i+j>m的边vivj分别标数2026,2027,…,m；其余边任意标数再证明k≥m．反证法，假设存在一种标数方法，使得任意两个顶点之间都存在一条权重不超过m−1的道路．待定正整数t>m/3，考虑标数1,2,…,t的边构成的子图，设它的连通分支为V1,…,Vr，则r≥2026−t．对i<j，从Vi中某顶点到Vj中某顶点的权重最小的路径至多包含2条长边（否则该路径的权重≥t+1+t+2+t+3>m−1因为fi,j≥t+1且互不相同，所以满足（a）的i<j至多有m#{于是m取t=m−2026>m/3，可得题3．设数列ai满足a1=2，对n≥2,an是不整除k=1n−1n−k+ak的最小质数i证明：设bn=n−an．由条件，an是不整除k=1固定素数p．对任意正整数r，记Ar=r+pℤ+=r+ℓp:ℓ∈ℤ+（1）满足an=p的所有下标n模p互不同余（特别地，这表明fp≤p）．事实上，假设a（2）若an>p，则p∉aAn．这是因为an>p意味着n设cn=n−minan,引理1：设r≡cnmod p，其中证明：如果an≤p，则cn=bn如果an>p，则cn=n−p，于是r下面我们证明可重集c1,c2,…,cp在模（i）如果i<j满足ci=事实上，ci=cj表明i−minai,p=j−minaj,p，因此mina（ii）如果ci=cj事实上，ci=cj−p表明i−minai,p=j−minaj,p−如果还有ai≥p，则意味着j−i=p+aj−p=aj．于是aj=j−i是素数，并且是满足j≠bkmod引理2：在模p意义下，可重集c1,…,c证明：假设存在两两不同的i,j,k使得ci≡cj如果ci=cj=ck，不妨设i<j<k，则性质（i）要求ai<p<aj且aj<p<ak，矛盾．否则引理3：如果an=p，在模p意义下，cn在可重集证明：如果cn mod p不是唯一的，则性质（i）和（ii）表明必须有回到原题．对任意素数p，我们证明fp≤12p+gp，其中gp为p在a1,a2,…,ap中出现的次数．由引理4和5，可