数学杂题(一)
ReLU
·
·
学习·文化课
一
我们约定对于 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 同时满足:
-
\forall a\in A,\operatorname{popcnt}(a)=4
-
\forall b\in \{s\in S_n\mid\operatorname{popcnt}(s)=2\},\exists a\in A,b\subseteq 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$,矛盾。
::::