对于正整数 $a$,$b$,存在唯一一对整数 $q$ 和 $r$,使得 $a = bq + r$,其中 $0 \leqslant r < b$.特别地,当 $r = 0$ 时,称 $b$ 能整除 $a$,记作 $b\mid a$.已知 $A = \left\{ {1,2,3, \cdots ,23} \right\}$.
【难度】
【出处】
【标注】
  • 知识点
    >
    数论初步
    >
    整除与同余
  • 知识点
    >
    数论初步
    >
    整除与同余
  • 题型
    >
    组合数学
    >
    组合极值
  • 知识点
    >
    函数
    >
    集合与映射
  1. 存在 $q \in A$,使得 $2011 = 91q + r\left(0 \leqslant r < 91\right)$,试求 $q$,$r$ 的值;
    标注
    • 知识点
      >
      数论初步
      >
      整除与同余
    答案
    $q = 22$,$r = 9$
    解析
    因为$$2011 = 91 \times 22 + 9,$$所以 $q = 22$,$r = 9$.
  2. 求证:不存在这样的函数 $f:A \to \left\{ {1,2,3} \right\}$,使得对任意的整数 ${x_1}$,${x_2} \in A$,若 $|{x_1} - {x_2}| \in \left\{ {1,2,3} \right\}$,则 $f\left({x_1}\right) \ne f\left({x_2}\right)$;
    标注
    • 知识点
      >
      数论初步
      >
      整除与同余
    答案
    解析
    用反证法.
    假设存在这样的函数 $f:A \to \left\{ {1,2,3} \right\}$,使得对任意的整数 $x$,$y$,若 $|x - y| \in \left\{ {1,2,3} \right\}$,则 $f\left(x\right) \ne f\left(y\right)$.
    取 $A$ 中的整数 $m,m+1,m+2,m+3$,则有$$\begin{cases}f(m)\ne f(m+1),\\f(m)\ne f(m+2),\\f(m)\ne f(m+3),\\f(m+1)\ne f(m+2),\\f(m+1)\ne f(m+3),\\f(m+2)\ne f(m+3),\end{cases}$$也就是说 $f(m),f(m+1),f(m+2),f(m+3)$ 两两不等.
    因此$$\mathrm{card}\{y|y=f(x),x\in A\}\geqslant 4,$$而$$\mathrm{card}\{1,2,3\}=3,$$矛盾.
    因此原命题成立.
  3. 若 $B \subseteq A$,${\rm Card}\left(B\right) = 12$(${\rm Card}\left(B\right)$ 指集合 $B$ 中的元素的个数),且存在 $a$,$b \in B$,$b < a$,$b\mid a$,则称 $B$ 为"和谐集".求最大的 $m \in A$,使含 $m$ 的集合 $A$ 的有 $ 12 $ 个元素的任意子集为"和谐集",并说明理由.
    标注
    • 题型
      >
      组合数学
      >
      组合极值
    • 知识点
      >
      函数
      >
      集合与映射
    答案
    $7$
    解析
    从非“和谐集”$$\{12,13,14,15,16,17,18,19,20,21,22,23\}$$出发可得符合条件的 $m<12$.
    将其调整:删去 $22$,写下 $11$;
    删去 $20$,写下 $18$;
    删去 $18$,写下 $10$;
    删去 $16$,写下 $8$;
    此时已经通过构造非“和谐集”得到符合题意的 $m<8$.
    下面证明 $m=7$ 时符合题意.
    将集合 $A$ 除 $7$ 外的元素划分为
    $A_0=\{23,19,15,17,13\}$,$A_1=\{22,11\}$,$A_2=\{20,10,5\}$,$A_3=\{18,9,3\}$,$A_4=\{16,8,4,2\}$,$A_5=\{12,6\}$,$A_6=\{14,1\}$.
    设含有 $7$ 的集合 $A$ 的 $12$ 元子集为 $X$.
    若 $X$ 中含有 $A_6$ 中的元素,则 $X$ 是“和谐集”;
    若 $X$ 中不含中 $A_6$ 的元素,则除了 $A_0$ 中的 $5$ 个元素以及元素 $7$ 以外,$X$ 至少要在 $A_1$ 到 $A_5$ 中选 $6$ 个元素,也就是说一定有 $2$ 个元素来自 $A_1$ 到 $A_5$ 中的同一个集合,于是 $X$ 是“和谐集”.
    综上知,$m$ 的最大值为 $7$.
题目 问题1 答案1 解析1 备注1 问题2 答案2 解析2 备注2 问题3 答案3 解析3 备注3
0.107623s