数学杂题(一)

· · 学习·文化课

一

我们约定对于 01 串 s,t

s\subseteq t\Longleftrightarrow s\operatorname{and} t=s

对于 m 阶排列 \sigma 和长为 m 的 01 串 s

\sigma(s)=s_{\sigma(1)}s_{\sigma(2)}\dots s_{\sigma(m)}

设所有长 n 的 01 串的集合为 S_{n}。

给定正整数 n\ge 5。设 A\subseteq S_n。若 A 同时满足:

则称 A 具有性质 P。

(1)当 n=8 时,若集合 A 具有性质 P,求 |A| 的最小值。
(2)若 A_1,A_2 都有性质 P 且 |A_1|,|A_2| 均为最小值,定义等价关系 \cong\colon A_1\cong A_2\Longleftrightarrow \exists \sigma, \{\sigma(a)\mid a\in A_1\}=A_2。找出所有等价类。

::::info[题解]

Subtask 1

求最小值的常见方法是:证一个足够紧的下界并构造下界。

注意到 1 个 a 最多覆盖 C_4^2=6 个 b,共 C_8^2=28 种 b。得到下界 \lceil28/6\rceil=5,但这还不够紧。

考虑维护一个初始为 0 的数组 \mathrm{cnt},每当一个 b 被一个 a 覆盖就令 \mathrm{cnt}\leftarrow \mathrm{cnt}+b。

考虑 b:每个 b 至少被覆盖 1 次,最后 \mathrm{cnt} 至少是 (7,7,7,7,7,7,7,7)。再考虑 a:每个 a 会使 \mathrm{cnt}\leftarrow \mathrm{cnt}+3a。最终 \mathrm{cnt} 每一位都是 3 的倍数,至少是 (9,9,9,9,9,9,9,9)。

考虑总和得到下界 \lceil72/12\rceil=6。

给出一组构造:

A_0=\left\{ \begin{aligned} &\texttt{11110000},\\ &\texttt{00001111},\\ &\texttt{11001100},\\ &\texttt{11000011},\\ &\texttt{00111100},\\ &\texttt{00110011} \end{aligned} \right\}

可以看成用 6 个 4 阶完全图覆盖 8 阶完全图。

或是 8 个维度两两分组,然后 4 个组两两连边。

Subtask 2

程序暴力枚举得到共 3 个等价类,代表元素:

A_0=\left\{ \begin{aligned} &\texttt{11110000},\\ &\texttt{00001111},\\ &\texttt{11001100},\\ &\texttt{11000011},\\ &\texttt{00111100},\\ &\texttt{00110011} \end{aligned} \right\}\qquad A_1=\left\{ \begin{aligned} &\texttt{11110000},\\ &\texttt{00001111},\\ &\texttt{11001100},\\ &\texttt{10100011},\\ &\texttt{00111100},\\ &\texttt{01010011} \end{aligned} \right\}\qquad A_2=\left\{ \begin{aligned} &\texttt{11110000},\\ &\texttt{11001100},\\ &\texttt{11000011},\\ &\texttt{00101011},\\ &\texttt{00011110},\\ &\texttt{00110101} \end{aligned} \right\}

此外,对于任意最优解 A(即 |A|=6),不难证明如下两条性质:

::::

二

已知 n,m\in \R^+ 满足:

\begin{cases} n+\ln n=3 \\ 1+\ln m=e^2/m \end{cases}

求 nm。

::::info[题解]

考虑对应函数单调性,n,m 均唯一。

设 x=\ln n,y=\ln m。我们考虑转而求 x+y。尽量把两个方程化成相同的形式:

\begin{cases} e^x+x=3 \\ e^{2-y}+(2-y)=3 \end{cases}

因此 x=2-y。从而 nm=e^2。

::::

三

解方程:

\sqrt{2y^2-1}+\sqrt{y^2-3y-2}=\sqrt{2y^2+2y+3}+\sqrt{y^2-y+2}

::::info[题解]

诈骗题。

设:

\begin{aligned} a&=2y^2-1 \\ b&=y^2-3y-2 \\ c&=2y^2+2y+3 \\ d&=y^2-y+2 \end{aligned}

显然 a,b,c,d\ge 0。

发现 a,c 和 b,d 二次项系数相同,这启发我们随机手玩一下发现 c-a=d-b=2y+4。

因此原方程化为

\sqrt{a}+\sqrt{b}=\sqrt{a+2y+4}+\sqrt{b+2y+4}

考虑从左边到右边是怎么变的,由于平方根函数单调增,两项同时变大或同时变小。由于等号成立,只能是 2y+4=0 即 y=-2,检验合法。

::::

四

已知 a,b,c\in \R,a+b+c=0。求证 2(a^4+b^4+c^4)=(a^2+b^2+c^2)^2。

::::info[题解]

暴力题。代入 c=-a-b 暴力展开就做完了。

::::

五

集合 S=\{1,2,3,\dots,n\}。正整数列 \{c_i\}_{i=1}^m 满足 \sum_{i=1}^m c_i=n。集合 \{A_i\}_{i=1}^m 是对 S 的一个划分,满足 |A_i|=c_i。设 k=\sum_{i=1}^m \left(\min(A_i)+\max(A_i)\right)。设 K 为所有可能的 k 取值组成的集合。求 \min(K)+\max(K)。

::::info[题解]

我们考虑某种“反转”大小关系的对称性。

对于一个合法划分 A_1\sim A_m,构造 B_i=\{n+1-x\mid x\in A_i\}。显然 B_1\sim B_m 也是合法划分。

不难证明

\sum_{i=1}^m \left(\min(B_i)+\max(B_i)\right)=2m(n+1)-\sum_{i=1}^m \left(\min(A_i)+\max(A_i)\right)

设 K 为所有可能的 k 取值组成的集合。则

\forall k\in K,2m(n+1)-k\in K

因此 \min(K)+\max(K)=2m(n+1)。

::::

六

已知实数 a,b,c,x,y 满足:

\begin{align} & a+b+c = 1 \tag{1}\\ & a^2+b^2+c^2 = 3 \tag{2}\\ & bc-x-2ya = 0 \tag{3}\\ & ca-x-2yb = 0 \tag{4}\\ & ab-x-2yc = 0 \tag{5} \end{align}

证明 abc=-1 或 abc=5/27。

::::info[题解]

注意到

(a+b+c)^2=(a^2+b^2+c^2)+2(ab+bc+ca)

代入 (1)(2) 得

ab+bc+ca=-1 $$ \begin{aligned} (bc+ca+ab)-3x-2y(a+b+c)&=0\\ -1-3x-2y&=0\\ y&=-\frac{1}{2}-\frac{3}{2}x \end{aligned} $$ 代入 $(3)$ 得 $$ \begin{aligned} bc-x-2\left(-\frac{1}{2}-\frac{3}{2}x\right)a&=0 \\ bc-x+a+3ax&=0 \\ (-1-ab-ca)-x+a+3ax&=0 \\ a(-b-c+1+3x)-x-1&=0 \\ a\left((a-1)+1+3x\right)-x-1&=0 \\ a(a+3x)-x-1&=0 \\ a^2+3ax-x-1&=0 \\ \end{aligned} $$ 解得 $$ a=\frac{-3x\pm \sqrt{9x^2+4x+4}}{2} $$ $b,c$ 同理。 固定 $x$,$a,b,c,y$ 都可以用 $x$ 表示。 设 $$ \begin{aligned} f(x)&=\frac{-3x+\sqrt{9x^2+4x+4}}{2}\\ g(x)&=\frac{-3x-\sqrt{9x^2+4x+4}}{2} \end{aligned} $$ 那么 $a,b,c$ 每个都会从 $\{f(x),g(x)\}$ 中二选一。我们分类讨论 $f(x)$ 的个数,根据式 $(1)$ 求 $x$。 1. $3$ 个 $f(x)$:$3f(x)=1$,无实数解。 2. $2$ 个 $f(x)$:$2f(x)+g(x)=1$,解得 $x=0$,回代得 $abc=-1$。 3. $1$ 个 $f(x)$:$f(x)+2g(x)=1$,解得 $x=-4/9$,回代得 $abc=5/27$。 4. $0$ 个 $f(x)$:$3g(x)=1$,无实数解。 综上,$abc=-1$ 或 $abc=5/27$。 :::: ## 七 求证:$\forall a,b,c\in (0,+\infty)$,有 $$ \sqrt{\frac{a}{a+2b+c}}+\sqrt{\frac{b}{a+b+2c}}+\sqrt{\frac{c}{2a+b+c}}\le \frac{3}{2} $$ ::::info[题解] 柿子看上去很繁琐,设 $$ \begin{aligned} s&=a+b+c \\ x&=s+a \\ y&=s+b \\ z&=s+c \end{aligned} $$ 则上式简化为 $$ \sqrt{\frac{a}{y}}+\sqrt{\frac{b}{z}}+\sqrt{\frac{c}{x}}\le \frac{3}{2} $$ 先看何时取等,显然 $a=b=c$ 是取等的充分条件。 我们的目标是找到一些 $\textcolor{#E74C3C}{T}$ 满足 $$ \sqrt{\frac{a}{y}}+\sqrt{\frac{b}{z}}+\sqrt{\frac{c}{x}}\le \textcolor{#E74C3C}{T}\le \frac{3}{2} $$ 由于左右两侧在 $a=b=c$ 时取等,这里两个 $\le$ 都必须在 $a=b=c$ 时取等。 根号很难处理,标准的技巧是 AM-GM $\sqrt{uv}\le (u+v)/2$。 对于第一项 $\sqrt{a/y}$,我们需要找到 $u,v$ 使得 $uv=a/y$ 且当 $a=b=c$ 时有 $u=v=1/2$。 经过一些尝试发现 $$ u=\frac{2a}{x},v=\frac{x}{2y} $$ 恰好满足要求。 得到 $$ \sqrt{\frac{a}{y}}+\sqrt{\frac{b}{z}}+\sqrt{\frac{c}{x}}\le\frac{1}{2}\left( \frac{2a}{x}+\frac{2b}{y}+ \frac{2c}{z}+\frac{x}{2y}+\frac{y}{2z}+\frac{z}{2x}\right) $$ 只需要证右边 $\le 3/2$。 对右边恒等变形,只保留 $x,y,z$,分别用 $x,y,z$ 表示 $a,b,c$,代入并整理,得 $$ 右边=\frac{9}{4}-\frac{1}{4}\left(\frac{y}{x}+\frac{z}{y}+\frac{x}{z}\right) $$ 由 AM-GM 得 $$ \frac{y}{x}+\frac{z}{y}+\frac{x}{z}\ge 3 $$ 因此 $$ \text{右边}\le \frac{3}{2} $$ 证毕。 :::: ## 八 设 $A\subseteq \R$ 且 $A\ne \varnothing$。若 $\forall x,y\in A$,都有 $x+y\in A,xy\in A$ 那么称 $A$ 具有性质 $P$。证明:若 $A$ 具有性质 $P$ 且 $a\neq \R$,则 $\complement_\R A$ 不具有性质 $P$。 ::::info[题解] 显然 $A$ 和 $\complement_\R A$ 均非空。 考虑反证,设 $\complement_\R A$ 也具有性质 $P$。 我们尝试考虑 $+,\times$ 的单位元也就是 $0,1$ 这两个特殊数。不妨设 $0\in A$。因此 $\complement_\R A$ 中就不能出现相反数对。 若 $x\in \complement_\R A$,那么显然 $-x\notin \complement_\R A$ 即 $-x\in A$。 可以平方消去负号,得到 $x^2\in A$ 且 $x^2\in \complement_\R A$,矛盾。 ::::