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

2026年国际数学奥林匹克中国国家集训队测试四 第一天试题 题1．给定正整数．用个多米诺骨牌不重不漏地覆盖方格表．一个“字形”是指由一对多米诺骨牌构成的如下图形之一： 求字形个数的最大值． 题2．是否存在质数和正整数，同时满足 （1）； （2）？ 题3．设正整数是正整数，对，定义，规定．定义多项式 其中． 证明：的系数均非负当且仅当． 2026年国际数学奥林匹克中国国家集训队测试四 第一天试题解答 题1．给定正整数．用个多米诺骨牌不重不漏地覆盖方格表．一个“字形”是指由一对多米诺骨牌构成的如下图形之一： 求字形个数的最大值． 解：字形个数的最大值是． 设由两个水平多米诺构成的字形个数为，由两个垂直多米诺构成的字形个数为．设分别表示包含于水平，垂直多米诺的内部方格（不与边界相邻）的个数．因为每个内部方格要么包含于水平多米诺，要么包含于垂直多米诺，因此．我们将证明，这样就有字形的个数． 对于由两个水平多米诺构成的字形，我们称它中间一列为字形的中轴．固定1}，我们考察有多少个水平的字形中轴位于第列．标记出第列所有包含于水平多米诺的方格，并写上字母和，表示该水平多米诺覆盖的是第列，或第列．于是，第列的相邻两个方格构成某个字形的中轴，当且仅当它们都被标记并写上不同的字母．对于连续的个标记方格，它至多能包含个水平字形的中轴（当交替时取等号）．注意到： · 如果这连续的个标记方格中没有边界方格（即第1行或第行的方格），则它包含个内部方格，且对应的水平字形个数． · 如果这连续的个标记方格中恰有一个边界方格，则它包含个内部方格，且对应的水平字形个数． · 如果这连续的个标记方格中恰有一个边界方格（即，第列的所有方格都标记），则它包含个内部方格，根据下面的引理，它们的方向不可能是一直交替的，因此它对应的水平字形个数． 综合以上情况，第列中，每一段连续的标记方格对水平字形个数的贡献不超过对内部方格个数的贡献．对求和即得．同理有，因此结论得证． 最后我们补充引理和证明． 引理：第列不可能所有个方格都是标记方格，并且方向交替． 引理的证明：假设第列发生了这种情况，我们考察第列．对于第列每个标记的方格，它所在的水平多米诺覆盖了左边的方格，该方格（位于第列）标记． 对于第列每个标记为的方格，它左边的方格（位于第列）所在的多米诺不能向右，也不能向上或向下（因为第列是交替，它上方或下方的方格已经与第列的方格被一个水平多米诺覆盖），因此只能向左，该方格标记． 于是，第列的方格也都被标记，并且方向交替．重复这一过程，最终第1列也是交替；但这是不可能的，因为第1列方格不可能标记，矛盾． 下面给出构造．不妨设．当时，将的方格表都用水平多米诺覆盖．当时，先将第1行和第行分别用个水平的多米诺覆盖，再将第1列和第列的剩余部分分别用个垂直的多米诺覆盖．将中间剩下的方格表按此方式递推地覆盖． 设为上述覆盖方式下字形的个数．我们考虑边界的多米诺贡献的字形个数：第2行由个水平的多米诺组成，每个多米诺与第1行的2个多米诺形成一个字形，贡献个；第行类似．第2列由个垂直的多米诺构成，每个多米诺与第1列的2个多米诺形成一个字形，贡献；第列类似．因此 由于，归纳易知． 题2．是否存在质数和正整数，同时满足 （1）； （2）？ 解：不存在． 假设存在满足条件的质数和正整数．显然有．设，．由可知． 由条件（1）可知．由条件（2）可知，于是． 首先考虑是奇素数的情况．考虑集合 对于，一方面，利用可得．另一方面，1，所以中每个元素都是的（在模意义下不同的）解，共有个解． 设．对固定的，满足条件的的个数是，因此 由于，我们有 但对奇素数是循环群（亦即存在模的原根），因此在模意义下的解的个数不超过，矛盾． 最后考虑的情况．此时均为奇素数，且由易知，故．下面对的奇偶性分类讨论． 如果是奇数，由LTE引理可知，于是 进而，矛盾． 如果是偶数，由LTE引理可知，于是 进而．由于，这表明 对于函数，求导易知在上递增．于是，此即，这与矛盾． 题3．设正整数是正整数，对，定义，规定．定义多项式 其中． 证明：的系数均非负当且仅当． 证明：设．定义平移算子为，于是 定义多项式 满足． 注意到，，进而有 于是 由易知：（a）的所有系数非负；（b）；（c）是次回文多项式，即． 先证明必要性．假设的所有系数非负；特别地，系数非负．对固定的，，其中系数为，于是 由于，因此，故 因为，所以上式非负当且仅当，即． 再证明充分性．假设，即．我们只需证明的所有零点实部非正．这是因为实系数多项式在上分解得到的因式均形如，或，它们的系数均非负，因而的系数非负． 注意到的所有根都在单位圆上，因此的所有根都在单位圆上，设．归纳定义多项式：；对，定义．于是． 我们归纳证明：对，有 其中多项式的所有零点都在直线上． 对于，我们有，因此满足条件．假设结论对某个成立，即，则 因此．下面验证多项式的所有零点都在直线上．事实上，假设是的零点，则 其中乘积取遍的所有零点．两边取模长，得到 由归纳假设，，因此 以及 因此，若，则右边每个乘积都大于1．若，则右边每个乘积都小于1．两种情况均导致矛盾，因此只能，这就完成了归纳，因此成立． 特别地，若，由可知的所有零点都满足，因此的所有零点实部非正．若，由可知的所有零点都在直线上．类似上述证明过程，可知 并且多项式的所有零点都在直线上．因此的所有零点实部非正．结论得证． 学科网（北京）股份有限公司 $