一些有趣的MO构造题

· · 个人记录

准备MO高联摸鱼划水的时候碰到了点有趣的构造题 分享一下 隔晚扔答案

当然是改编成了OI题的风格（

有的题真的好啊 但是为什么会有人把他们扔到公开赛里呢

8.31

给定一个正整数 n，求出一个 1 \dots n 的排列（记为 a，下标从 1 开始），满足 \sum\limits_{i=1}^na_i(-2)^{i-1}=0，或报告无解

Tip: 大胆取模猜想然后求证 Sol: 考虑这个式子对 $3$ 取模。 显然 $(-2)^{(i-1)} \equiv 1 (\mod x) $，所以原式 $\equiv \sum\limits_{i=1}^na_i (\mod 3)$。 于是大胆猜想当 $\frac{n\times(n+1)}{2} \equiv 0 (\mod 3)$ 时有解，否则无解。即 $n \equiv 0$ 或 $2 (\mod 3)$ 时有解。 考虑构造答案。 将 $1\dots n$ 中所有模 $3$ 为 $1$ 的数按照从大到小排序，记为 $b$。将剩余的数从小到大排序，记为 $c$。则 $c+b$ 即为所求，就是将 $b$ 接在 $c$ 的后面。 举个例子，当 $n=8$ 时，答案之一为 $2 \ 3 \ 5 \ 6 \ 8 \ 7 \ 4 \ 1$。 证明的话直接爆算求一下就行了。 --- 9.1 有 $n$ 个人参加循环赛，每对人比一场，310积分制，最后这 $n$ 个人的分数呈公差为 $1$ 的等差数列。问得分最少的人最多得多少分，并给出一组解。 $1 \le n \le 2\times10^3

Tip：蒙

Sol:

通过总分算出这个答案最大为 n-1。但是这样的条件是所有场次都能打出胜负，没有平，故每个人的分数都是 3 的倍数，不符合条件。

所以我们就降一个，考虑答案是 n-2。

考虑归纳的构造答案。

设当前是考虑加入第 a 个人。

让第一个人平第 n 个人，然后以“胜负负”为循环节填满。

同上，让第一个人平第 n 个人，然后以“胜负负”为循环节填满。

从第一个人开始以“胜负负”为循环节填，且让第 n-1 个人平第 n 个人。

9.2

（有点偏数学）

确定并求出是否存在满足下列条件的正整数 n：n|2^n+1 且 n 恰好能被 114 个互不相同的质数整除。

9.4

确定并证明是否存在非负整数集 X，满足对于任意整数 n\ge 0，恰有一组 a,b \in X （a 可以等于 b），满足 a+2b=n

Sol:

选取所有在四进制下每一位都为 0 或 1 的数。证明显然。

9.7

前几天咕了，今天多更几道。

(1)

给定正整数对 (m,n) ，判断其是否能让 1\dots 10^6 分成两个两两不交的非空自己满足没有一个子集中存在两个数，其差的绝对值等于 n 或 m，并给出一组解。

(2)

在 2n\times2n 的方格表中，每个格填实数 1 或 -1，使得恰有 2n^2 个格子填 1。令 M 为所有的行和（同行小格中所有数的和）及列和（同列小格中所有数之和）的绝对值的最小值。试确定 M 的最大值，并构造一组解。