2022年中国台湾IMOC——数论、组合组

每年，我国台湾的前IMO参赛者组成的小团体都会举办一个夏令营，讲解知识和技巧，还有8次模拟考试．从2017年开始，他们取消了模拟考试，用若干练习题来取代．下面就是2022年中国夏令营的IMOC练习题．

数论组

1. 求所有正整数𝑛，使得对任意𝑖=1，2，⋯，𝑛，(𝑛!)/(𝑖!(𝑛−𝑖+1)!)均为整数．

2. 对正整数𝑛，定义𝑓(𝑛)为满足如下要求的最小正整数𝑥：存在正整数𝑘和𝑘个不同的正整数𝑛=𝑎_(0)<𝑎_(1)<𝑎_(2)<⋯<𝑎_(𝑘−1)=𝑥，使得𝑎_(0)𝑎_(1)⋯𝑎_(𝑘−1)为完全平方数．求正实数𝑐的最小值，使得存在正整数𝑁，对任意𝑛>𝑁，都有𝑓(𝑛)≤𝑐𝑛．

3. 求所有正整数𝑛，满足2𝑛+3∣𝑛!−1．

4. 求所有正整数对(𝑚,𝑛)，使得𝑚𝑛(𝑚^(2)+6𝑚𝑛+𝑛^(2))为完全平方数．

5. 求不定方程

   公式：p^p+(p+1)^p+\cdots(p+r)^p=(p+r+1)^p

   的所有解(𝑝,𝑟)，其中𝑝为素数，𝑟为正整数．

6. 求所有整系数多项式𝑃(𝑥)，使得对任意正整数𝑥，有𝜏(𝑃(𝑥))≥𝜏(𝑥)．其中𝜏(𝑛)为𝑛的正约数个数，定义𝜏(0)=∞．
   注：本题可以使用如下结论：对任意𝜀≥0，存在整数𝐶_(𝜀)，使得对任意正整数𝑛，从小到大的第𝑛个素数不超过𝐶_(𝜀)𝑛^(1+𝜀)．

组合组

1. 给定正整数𝑘，一只鸽子和一只海鸥在𝑛×𝑛的网格中玩游戏．从鸽子开始，双方轮流行动．鸽子选择其中𝑚个格子，并在它选择的每个格子中下一个蛋．海鸥选择一个𝑘×𝑘的网格，吃掉里面的所有蛋．如果在某一时刻，𝑛×𝑛网格中的每一个格子内都有一个蛋，那么鸽子获胜；否则海鸥获胜．对任意𝑛≥𝑘，求出所有的𝑚，使得鸽子能够获胜．

2. 桌子上有2022块石头．游戏开始时，老师选择一个正整数𝑚，并让A和B进行游戏．从A开始，A能在他的回合内移走至多𝑚块石头．两人轮流移走石头，每一回合能移走的石头数目至少为1，且不超过对方上一回合移走石头数目的2倍．无法移走石头者失败．求最小的正整数𝑚，使得𝐴有必胜策略．

3. 用如下三种形状的木板覆盖一个101×101的正方形木板，没有缝隙和重叠．至少需要多少块1×1的木板？

4. 给定正整数𝑁．考虑1，2，⋯，𝑁的一个排列𝑝_(1)，𝑝_(2)，⋯，𝑝_(𝑁)．对该排列的一段𝑝_(𝑙)，𝑝_(𝑙+1)，⋯，𝑝_(𝑟)，称它为“极端的”，若𝑝_(𝑙)和𝑝_(𝑟)分别为这一段的最大值和最小值．称排列𝑝_(1)，𝑝_(2)，⋯，𝑝_(𝑁)为“超级平衡的”，若其不存在长度不少于3的“极端的”段．例如：1，4，2，3是“超级平衡的”，但3，1，2，4不是．回答以下问题：
   (1)有多少个“超级平衡的”排列？
   (2)对任意正整数𝑀≤𝑁，有多少个满足𝑝_(1)=𝑀的“超级平衡的”排列？

5. 称一个每项均为0，1，2之一的数列为“三元数列”．对三元数列(𝑥_(1),𝑥_(2),⋯,𝑥_(𝑛))，定义其“差数列”为

   公式：(|x_1-x_2|,|x_2-x_3|,\cdots,|x_{n-1}-x_n|)

   每次求差数列会使得数列长度减少1，在求𝑛−1次差数列后，数列中将只剩下一项，定义其为原数列的特征值．
   有多少个长度为2023的三元数列，其特征值为0？

6. 给定整数𝑘≥4．Sunny和Ming进行一个字符串游戏．字符串是一个数列，其每项均为1到𝑘之间的整数（包括1和𝑘）．起初，Sunny选择两个正整数𝑁，𝐿≥2，并写下𝑁个字符串，每个字符串长度均为𝐿．然后Ming标记至多(𝑁)/(2)个字符串．然后Sunny选择一个未被标记的字符串𝑠，并求出最大整数𝑛，使得存在另一个字符串满足它的前𝑛个字符和𝑠的前𝑛个字符相同．接着Sunny移除那些前𝑛个字符和𝑠的前𝑛个字符不同的字符串，只留下前𝑛个字符和𝑠的前𝑛个字符相同的字符串．最后，Ming选择1到𝑘之间（包括1和𝑘）的一个整数𝑑，移除第𝑛+1个字符为𝑑的所有字符串．Sunny的得分为剩余字符串的个数．求Sunny可以保证得到的最高分．