离散数学证明题记录（1）

PS1 Problem 1

断言：令 \(n, \ c, \ p \in \mathbb{Z}\)，且 \(c\) 整除 \(10^p\)。则有 \(c\) 整除 \(n\) 当且仅当 \(c\) 整除 \(n\) 的最后 \(p\) 位数字的值。

名词解释：

• 当且仅当：如果 \(p \Rightarrow q\) 且 \(q \Rightarrow p\)，则可得 \(p \Leftrightarrow q\)，其中 \(\Leftrightarrow\) 意为“当且仅当”

代入验证

\(n\)	\(p\)	\(10^p\)	\(c\)	\(c \mid 10^p?\)	\(c \mid n?\)	\(n\)的最后\(p\)位数	\(c \mid n\) 的最后 \(p\) 位数？	\(c \mid n \Leftrightarrow c \mid n\) 的最后 \(p\) 位数？
\(123456\)	\(3\)	\(10^3 = 1000\)	\(4\)	T	T	\(456\)	T	T
\(98765\)	\(2\)	\(10^2 = 100\)	\(5\)	T	T	\(65\)	T	T
\(93380\)	\(2\)	\(10^2 = 100\)	\(4\)	T	T	\(80\)	T	T

证明

\[ \begin{aligned} \Rightarrow \ & n \text{可被写作}d_k d_{k-1}...d_{p}...d_1d_0 \text{的形式，} && \text{根据我们记录数字的方法} \\ & d_i \in \{ x : 0 \leq x \leq 9 \} \\ \Rightarrow \ & n = d_0+10^1d_1+...+ 10^{p}{d}_p+...+10^kd_k && \text{根据十位数的定义} \\ \Rightarrow \ & n = d_0+10^1d_1+...+ 10^{p}({d}_p+...+10^{k-p}d_k) && \text{因式分解出}10^p \\ \Rightarrow \ & n = d_0+10^1d_1+...+ (c \cdot l)({d}_p+...+10^{k-p}d_k) && \text{因为} c \mid 10^p \Rightarrow \\ & && 10^p = c \cdot l, \ l \in \mathbb{Z} \\ \Rightarrow \ & \dfrac{n}{c} = \dfrac{d_0+10^1d_1+...+10^{p-1}d_{p-1}}{c}+ l({d}_p+...+10^{k-p}d_k) && \text{等式两边除以}c \\ \Rightarrow \ & \dfrac{n}{c} = \dfrac{d_0+10^1d_1+...+10^{p-1}d_{p-1}}{c}+t, \ t \in \mathbb{Z} && \text{因为整数的积与和为整数，且}\\ & && l, 10^{k-p}, d_p,...,d_k \in \mathbb{Z} \\ \Rightarrow \ & \dfrac{n}{c} \text{为整数} \Leftrightarrow \frac{d_0+10^1d_1+...+10^{p-1}d_{p-1}}{c} \ (1)+t \text{为整数} && 因为等式两边相等 \\ \Rightarrow \ & \dfrac{n}{c} 为整数 \Leftrightarrow \dfrac{d_0+10^1d_1+...+10^{p-1}d_{p-1}}{c} 为整数 && 因为整数与整数的和为整数， \\ & && 整数与非整数的和为非整数； \\ & && 如果 t 和 t + (1) 为整数 \\ & && 则 (1) 必定为整数 \\ \Rightarrow \ & n可被c整除 \Leftrightarrow d_0+10^1d_1+...+10^{p-1}d_{p-1} \ (2) 可被 c 整除 && 因为 \tfrac{n}{c} 和 (1) 都为整数，\\ & && 即分子除以c后仍为整数 \\ \Rightarrow \ & n 可被 c 整除 \Leftrightarrow n 的最后 p 位数字的值可被 c 整除 && 因为 (2) 为 n 的最后 p 位 \\ & && 数字 \end{aligned} \]

反例反证

断言更改：令 \(n,c \geq 1, \ p \geq 2 \in \mathbb{Z}\)，且 \(c\) 整除 \(10^p\)。则有 \(c\) 整除 \(n\) 当且仅当 \(c\) 整除 \(n\) 的最后 \(p - 1\) 位数字的值。

名词解释：

• 反例反证（Disproof by Counterexample）：对于任意全称命题（Universal Claim）的反证，可以使用单个反例来举例证明。

反例：\(n = 52936, \ p = 2, \ c = 4\)

代入验证：

\(n\)	\(p\)	\(10^p\)	\(c\)	\(c \mid 10^p?\)	\(c \mid n?\)	\(n\)的最后\(p-1\)位数	\(c \mid n\) 的最后\(p-1\)位数？	\(c \mid n \Leftrightarrow c \mid n\) 的最后\(p-1\)位数？
\(52936\)	\(2\)	\(100\)	\(4\)	T	T	\(6\)	F	F

PS1 Problem 2

断言：令 \(n\) 为任意整数，则 \(n^4 + 10n^3 + 23n^2 + 14n\) 可被 \(4\) 整除。

证明：我们考虑以下两种情况

• 情况1：\(n\) 为偶数 \(\Rightarrow\) \(n = 2k, \ k \in \mathbb{Z}\)

\[ \begin{aligned} 原式 & = (2k)^4 + 10(2k)^3 + 23(2k)^2 + 14(2k) && 代换n为2k \\ & = 16k^4 + 80k^3 + 92k^2 + 28k \\ & = 4k(4k^3+20k^2+23k + 7) \\ & = 4t, \ t \in \mathbb{Z} && 因为整数的积与和必定为整数 \\ & && 且k, \ 4, \ 20, \ 34, \ 7 \in \mathbb{Z} \\ & \Rightarrow n^4+10n^3+23n^2+14n 可被 4 整除 && 根据整除的定义： \\ & && 即n = a \cdot k, \ k \in \mathbb{Z} \Rightarrow a \mid n \end{aligned} \]

• 情况2：n 为奇数 \(\Rightarrow\) \(n = 2k + 1, \ k \in \mathbb{Z}\)

\[ \begin{aligned} 原式 & = (2k+1)^4 + 10(2k+1)^3 + 23(2k+1)^2 + 14(2k+1) && 代换n为2k + 1 \\ & = 16k^4 + 112k^3 + 236k^2 + 188k + 48 \\ & = 4(4k^4+28k^3+59k^2+47k+12) \\ & = 4t, \ t \in \mathbb{Z} && 因为整数的积与和必定为整数 \\ & && 且k, \ 4, \ 28, \ 59, \ 47, \ 12 \in \mathbb{Z} \\ & \Rightarrow n^4+10n^3+23n^2+14n 可被 4 整除 && 根据整除的定义： \\ & && 即n = a \cdot k, \ k \in \mathbb{Z} \Rightarrow a \mid n \end{aligned} \]

对于任意整数 \(n\) 而言，\(n\) 为奇数或者 \(n\) 为偶数，所以情况的分类是详尽的。

PS1 Problem 3

断言：对任意实数 \(x, y\)，\(\vert x + y \vert \leq 2 \cdot \max\{ \vert x \vert, \vert y \vert \}\)

符号解释：

• \(\max\{a, b\}\)：返回\(a, b\)中较大的数

证明：我们考虑以下两种情况

• 情况1：\(x + y \geq 0\)

\[ \begin{aligned} \Rightarrow \ & \vert x + y \vert = x + y && 对于任意实数 z \geq 0, \vert z \vert = z \\ & && 同时 x + y \geq 0 \\ \Rightarrow \ & \vert x + y \vert \leq \vert x \vert + \vert y \vert && 对于任意实数w, \ z，w \leq \vert w \vert, \ z \leq \vert z \vert \\ & && 则 w + z \leq \vert w \vert + \vert z \vert \\ \Rightarrow \ & \vert x + y \vert \leq \max\{ \vert x \vert, \vert y \vert \} + \max\{ \vert x \vert, \vert y \vert \} && 根据 a, b \leq \max\{ a, b \} \\ & && 则 a + b \leq \max\{a, b\} + \max\{a, b\} \\ \Rightarrow \ & \vert x + y \vert \leq 2 \cdot \max\{ \vert x \vert, \vert y \vert \} \\ \end{aligned} \]

• 情况2：\(x + y < 0\)

\[ \begin{aligned} \Rightarrow \ & \vert x + y \vert = -(x + y) && 对于任意实数z \leq 0，\vert z \vert = -z \\ \Rightarrow \ & \vert x + y \vert = -x - y \\ \Rightarrow \ & \vert x + y \vert \leq \vert x \vert + \vert y \vert && 对于任意实数z，(z \geq -\vert z \vert) \Rightarrow (-z \leq \vert z \vert) \\ & && 则代换(-x), (-y)为 \vert x \vert 和 \vert y \vert \\ \Rightarrow \ & \vert x + y \vert \leq \max\{ \vert x \vert, \vert y \vert \} + \max\{ \vert x \vert, \vert y \vert \} && 根据 a, b \leq \max\{ a, b \} \\ & && 则 a + b \leq \max\{a, b\} + \max\{a, b\} \\ \Rightarrow \ & \vert x + y \vert \leq 2 \cdot \max\{ \vert x \vert, \vert y \vert \} \end{aligned} \]

对于任意实数 \(a\) 而言，\(a \geq 0\) 或者 \(a < 0\)，所以情况的分类是详尽的。