|
排 列 、 组 合 及 抽 屉 原 理 ·万精油·
【 上 期 题 目 讨 论 】 有 读 者 来 信 说 ， 这 次 的 题 目 就 是 一 个 编 码 解 码 问 题 。 说 得 很 对 。 编 码 解 码 在 现 代 生 活 中 可 以 说 是 无 所 不 在 。 广 义 说 起 来 ， 我 们 看 的 电 视 都 可 以 划 到 这 里 面 来 。 更 直 接 的 例 子 就 是 大 家 现 在 看 的 这 篇 文 章 所 用 的 国 标 码 。 大 家 知 道 ， 计 算 机 是 西 方 人 搞 起 来 的 。 在 计 算 机 上 传 递 信 息 自 然 用 他 们 的 一 套 字 母 与 符 号 。 作 为 拼 音 文 字 ， ８ 个 比 特 ２ ５ ６ 个 码 对 他 们 来 说 就 绰 绰 有 余 了 。 但 要 用 这 些 码 来 表 示 中 文 就 远 远 不 够 了 。 于 是 人 们 自 然 想 到 了 双 码 。 也 就 是 用 两 个 码 来 表 示 一 个 汉 字 。 双 码 等 于 一 维 变 两 维 ， 所 能 表 示 的 数 量 就 是 原 来 的 平 方 。 但 思 想 严 谨 的 人 马 上 会 意 示 到 一 个 问 题 。 怎 样 区 分 双 码 和 单 码 ？ 一 个 码 传 过 来 ， 我 们 怎 么 知 道 这 是 一 个 独 立 的 英 文 码 还 是 一 个 中 文 双 码 的 第 一 个 码 ？ 如 果 英 文 码 把 ２ ５ ６ 个 码 都 用 到 了 ， 那 这 个 问 题 就 很 严 重 了 。 所 幸 的 是 在 一 般 的 信 息 传 递 中 ， 英 文 码 并 不 需 要 用 到 所 有 的 ２ ５ ６ 个 码 。 事 实 上 ， 一 般 的 信 息 传 递 只 用 到 这 ２ ５ ６ 个 码 中 的 前 半 部 分 ， 也 就 是 ０ 到 １ ２ ７ 中 的 码 。 也 就 是 说 ， 英 文 码 的 ８ 个 比 特 中 的 最 高 一 个 比 特 都 是 ０ 。 这 样 一 来 ， 双 码 中 文 就 有 了 出 路 。 我 们 只 需 要 用 后 面 １ ２ ８ 个 码 就 行 了 。 一 个 码 传 过 来 ， 如 果 最 高 一 个 比 特 是 ０ ， 就 是 一 个 独 立 的 英 文 码 ， 否 则 就 是 双 码 的 第 一 个 码 。 由 于 一 些 技 术 原 因 ， 我 们 并 不 不 是 把 后 １ ２ ８ 个 码 都 用 到 了 。 而 是 只 用 到 了 后 １ ２ ８ 个 码 中 相 对 于 前 １ ２ ８ 个 码 中 可 印 的 那 些 码 。 我 们 知 道 ， 前 １ ２ ８ 个 码 中 有 很 多 是 不 可 印 的 ， 比 如 回 车 、 提 行 、 空 格 等 等 。 真 正 可 以 印 出 来 的 码 只 有 ９ ４ 个 ， （ ３ ３ － １ ２ ６ ） 。 所 以 ， 国 标 码 的 总 容 量 是 ９ ４ Ｘ ９ ４ ＝ ８ ８ ３ ６ 。 中 文 字 当 然 多 于 这 个 数 。 所 以 你 有 时 会 发 现 你 想 要 的 字 在 国 标 字 库 里 没 有 。 台 湾 用 的 大 五 码 没 有 这 些 限 制 ， 所 以 容 量 大 得 多 。 当 然 ， 问 题 并 不 完 全 这 么 简 单 。 由 于 历 史 原 因 ， 有 些 电 子 邮 件 系 统 根 本 不 支 持 ８ 比 特 码 ， 它 们 只 处 理 ７ 比 特 码 。 ８ 比 特 码 传 来 ， 它 们 一 律 把 最 高 一 个 比 特 处 理 为 ０ 。 这 样 一 来 ， 我 们 的 双 码 系 统 就 失 效 了 。 于 是 有 人 想 到 补 救 办 法 ， 在 前 １ ２ ８ 个 码 中 作 文 章 。 用 特 殊 状 态 符 号 来 区 分 英 文 码 与 中 文 码 。 比 如 汉 字 （ Ｈ Ｚ ） 码 就 是 用 ｔ ｉ ｌ ｄ ａ 加 花 括 弧 作 为 状 态 符 号 的 。 直 到 现 在 为 此 ， 在 许 多 中 文 网 与 邮 递 网 中 ， Ｈ Ｚ 码 还 占 有 很 大 一 席 地 位 。 现 在 流 行 的 什 么 统 一 码 ， 要 想 把 世 界 上 所 有 大 语 言 的 码 都 包 括 进 去 ， 那 又 是 另 外 一 个 故 事 了 。 现 在 回 到 我 们 的 题 目 。 从 一 副 有 ５ ２ 张 的 牌 中 随 机 抽 出 五 张 ， 怎 样 用 其 中 的 四 张 牌 来 表 示 第 五 张 牌 ？ 首 先 注 意 到 我 们 可 以 给 所 有 的 牌 定 一 个 大 小 顺 序 。 比 如 黑 桃 Ａ ， ２ ， … ， Ｋ ， 接 下 去 是 红 桃 Ａ ， ２ ， … ， Ｋ ， 再 接 下 去 是 方 块 ， 梅 花 。 这 样 一 来 这 ５ ２ 张 牌 就 相 当 于 从 １ 到 ５ ２ 个 数 。 ４ 张 牌 横 放 在 桌 上 ， 按 照 大 小 顺 序 不 同 可 以 有 ４ 的 阶 乘 ， 也 就 是 ２ ４ 种 放 法 。 我 们 可 以 用 这 ２ ４ 种 放 法 来 表 示 ２ ４ 个 不 同 的 数 （ 也 就 是 ２ ４ 张 不 同 的 牌 ） 。 但 是 ， 从 ５ ２ 张 牌 中 抽 出 ４ 张 以 后 ， 还 剩 ４ ８ 张 。 ２ ４ 只 是 它 的 一 半 ， 远 远 不 够 。 有 的 读 者 也 走 到 了 这 一 步 ， 其 实 已 经 很 接 近 了 。 可 惜 他 没 有 继 续 走 下 去 。 怎 样 解 决 另 一 半 呢 ？ 注 意 到 我 们 原 题 目 中 说 你 可 以 从 抽 出 来 的 五 张 牌 选 择 一 张 藏 起 来 。 选 哪 一 张 牌 就 很 有 讲 究 。 四 的 阶 乘 等 于 ２ ４ ， 没 有 什 么 文 章 好 做 ， 这 另 一 半 就 得 靠 这 选 牌 来 解 决 。 这 个 问 题 有 不 只 一 种 解 法 ， 也 就 是 说 有 多 种 方 法 来 表 示 第 五 张 牌 。 我 们 这 里 选 择 一 个 简 单 清 楚 的 办 法 来 讲 （ 但 由 于 此 办 法 不 能 推 广 ， 并 不 是 最 佳 办 法 ） 。 ５ ２ 张 牌 有 四 种 花 色 。 根 据 抽 屉 原 理 ， 五 张 牌 中 一 定 有 两 张 以 上 的 牌 是 属 于 同 一 花 色 ， 比 如 有 两 张 黑 桃 。 我 们 就 把 其 中 一 张 黑 桃 藏 起 来 ， 把 另 一 张 黑 桃 放 在 桌 面 第 一 张 。 朋 友 看 见 第 一 张 是 黑 桃 ， 就 知 道 藏 的 那 张 是 黑 桃 。 这 一 下 把 收 索 空 间 缩 小 到 四 分 之 一 。 但 这 还 不 够 ， 因 为 除 掉 一 张 牌 以 后 ， 我 们 只 剩 下 三 张 牌 可 以 用 。 而 三 张 牌 只 能 有 ６ 种 放 法 （ ３ 的 阶 乘 ） 。 除 了 放 在 桌 面 的 黑 桃 以 外 ， 还 有 １ ２ 张 黑 桃 ， ６ 种 放 法 只 能 表 示 出 其 中 的 一 半 。 我 们 还 需 要 再 动 脑 筋 来 想 怎 样 解 决 另 外 一 半 。 与 前 面 相 同 ， ３ 的 阶 乘 等 于 ６ ， 没 有 什 么 文 章 好 做 。 只 好 从 选 择 的 藏 牌 中 来 找 出 路 。 我 们 前 面 说 把 两 张 黑 桃 中 的 一 张 藏 起 来 ， 藏 哪 张 呢 ？ 用 抽 屉 原 理 我 们 已 经 去 除 了 四 分 之 三 的 牌 。 现 在 我 们 要 从 这 两 张 牌 的 选 择 中 来 去 掉 另 一 半 牌 。 把 所 有 的 黑 桃 按 顺 时 针 方 向 摆 成 一 圆 环 （ 想 像 时 钟 上 有 十 三 点 ， 它 们 是 Ａ ， ２ ， … ， Ｋ ） 。 这 是 一 个 有 十 三 节 的 圆 环 。 从 这 个 圆 环 中 任 取 两 张 ， 这 圆 环 被 分 为 两 段 。 因 为 总 长 度 为 十 三 ， 两 段 中 必 有 一 段 长 度 小 于 或 等 于 六 。 我 们 选 择 短 的 那 一 段 的 结 尾 那 张 牌 藏 起 来 （ 因 为 有 方 向 ， 所 以 每 一 段 都 有 开 始 和 结 尾 ） ， 把 另 一 张 牌 放 在 桌 面 第 一 张 。 这 一 张 牌 不 但 告 诉 我 们 的 朋 友 所 藏 那 张 牌 的 花 色 ， 而 且 还 告 诉 他 我 们 的 起 始 点 。 因 为 所 藏 的 牌 离 这 第 一 张 牌 不 超 过 六 ， 我 们 可 以 用 三 张 牌 的 顺 序 表 示 出 来 。 至 于 三 张 牌 的 顺 序 如 何 表 示 １ ， ２ ， ３ ， ４ ， ５ ， ６ 则 完 全 由 你 与 你 的 朋 友 决 定 。 最 简 单 的 办 法 是 按 照 自 然 数 的 大 小 决 定 。 我 们 前 面 已 经 说 过 ， 可 以 为 ５ ２ 张 牌 定 一 个 顺 序 。 这 样 一 来 ， 随 便 哪 三 张 牌 都 有 一 个 大 小 顺 序 。 我 们 不 妨 把 它 们 叫 做 １ ， ２ ， ３ 。 于 是 ， 这 三 张 牌 可 以 有 六 种 组 合 ， 按 照 自 然 数 大 小 ， 这 六 种 组 合 可 以 排 成 ： １ ２ ３ ， １ ３ ２ ， ２ １ ３ ， ２ ３ １ ， ３ １ ２ ， ３ ２ １ 。 我 们 可 以 用 它 们 来 表 示 １ ， ２ ， ３ ， ４ ， ５ ， ６ 。 现 在 我 们 给 一 个 例 子 ： 如 果 我 们 抽 到 的 五 张 牌 是 ： 黑 桃 三 ， 红 桃 七 ， 方 块 二 ， 方 块 Ｊ ， 草 花 Ｋ 。 因 为 方 块 有 两 张 ， 所 以 我 们 决 定 藏 方 块 。 在 方 块 二 与 方 块 Ｊ 中 ， 二 离 Ｊ 按 顺 时 针 方 向 比 较 远 （ 距 离 为 九 ） ， 而 Ｊ 离 二 比 较 近 （ 中 间 有 Ｑ ， Ｋ ， Ａ ， 二 ） ， 所 以 距 离 为 四 。 于 是 我 们 要 在 桌 面 上 用 剩 下 的 三 张 牌 表 示 出 四 来 。 剩 下 的 三 张 牌 按 大 小 顺 序 是 黑 桃 三 ， 红 桃 七 ， 草 花 Ｋ 。 按 照 我 们 上 面 的 顺 序 ， 要 摆 出 四 ， 就 是 要 摆 出 ２ ３ １ 。 于 是 ， 我 们 把 方 块 二 藏 起 来 ， 把 剩 下 的 四 张 牌 摆 成 ： 方 块 Ｊ ， 红 桃 七 ， 草 花 Ｋ ， 黑 桃 三 。 我 们 的 朋 友 看 见 第 一 张 是 方 块 Ｊ ， 所 以 知 道 藏 起 来 的 那 张 牌 是 方 块 。 看 见 剩 下 的 三 张 牌 摆 的 是 每 四 个 顺 序 ， 所 以 知 道 藏 的 那 张 牌 离 Ｊ 的 距 离 为 四 。 于 是 一 个 个 数 过 去 ， Ｑ ， Ｋ ， Ａ ， 二 。 所 以 推 出 藏 起 来 的 那 张 牌 是 方 块 二 。 这 不 仅 是 一 个 趣 味 题 ， 还 可 以 是 一 个 游 戏 。 你 可 以 和 你 的 朋 友 商 量 好 这 一 套 编 码 系 统 ， 然 后 为 许 多 人 表 演 。 一 般 人 在 短 时 间 内 是 不 会 看 出 其 中 的 明 堂 的 。 为 避 免 用 高 矮 ， 正 斜 之 类 的 手 段 做 假 ， 可 以 由 别 人 来 放 ， 只 不 过 必 须 按 你 规 定 的 顺 序 。 我 玩 过 两 次 ， 效 果 还 不 错 。 这 个 题 目 做 出 来 以 后 ， 最 自 然 的 想 法 就 是 ： 如 果 牌 张 数 再 多 一 点 会 有 什 么 结 果 ？ 当 然 ， 不 管 用 什 么 手 段 ， 几 张 牌 能 表 示 的 牌 张 数 总 有 个 上 限 。 这 上 限 是 多 少 ？ 做 一 些 排 列 组 合 的 数 学 推 理 ， 我 们 可 以 知 道 上 限 是 Ｎ ＝ Ｍ ！ ＋ Ｍ － １ 也 就 是 说 如 果 从 Ｎ 张 牌 中 抽 Ｍ 张 牌 出 来 ， 选 一 张 藏 起 来 ， 能 用 剩 下 的 Ｍ － １ 张 牌 把 它 表 示 出 来 ， 那 么 这 个 Ｎ 不 能 超 过 Ｍ ！ ＋ Ｍ － １ 。 这 公 式 只 是 给 出 上 限 ， 但 并 不 是 说 上 限 就 一 定 能 够 达 到 。 对 于 具 体 的 Ｍ ， 到 底 能 表 示 多 大 的 Ｎ 还 不 是 很 清 楚 。 当 Ｍ ＝ ２ ， ３ 时 ， 上 面 公 式 给 出 Ｎ ＝ ３ ， ８ ， 这 两 个 上 限 是 可 以 达 到 的 。 再 大 一 点 就 不 知 道 了 。 对 于 我 们 上 期 题 目 的 情 况 ， 也 就 是 Ｍ ＝ ５ 的 情 况 ， 上 面 的 公 式 说 Ｎ 最 大 可 以 到 １ ２ ４ ， 这 要 比 两 付 牌 都 多 ， 想 起 来 似 乎 不 太 可 能 。 即 使 是 一 副 ５ ４ 张 的 正 规 扑 克 我 也 没 能 找 到 解 。 上 期 题 目 中 还 出 了 另 一 个 题 ， 希 望 大 家 能 找 到 对 于 一 副 有 ５ ４ 张 牌 ， 但 大 小 王 等 同 的 牌 的 解 法 。 正 题 没 有 人 做 出 ， 这 个 题 自 然 也 没 有 人 解 。 有 一 位 读 者 来 信 说 他 找 到 了 对 ５ ４ 张 正 规 牌 （ 也 就 是 说 大 小 王 不 同 的 牌 ） 的 解 法 ， 但 没 找 到 大 小 王 相 同 时 的 解 法 。 我 想 这 大 约 是 对 题 目 的 理 解 有 误 。 否 则 ， 前 者 包 括 后 者 ， 不 会 只 有 前 者 没 有 后 者 的 道 理 。 这 等 于 是 说 我 会 从 一 数 到 一 百 ， 但 不 会 数 九 十 九 。 本 来 想 把 两 王 相 同 的 ５ ４ 张 牌 的 解 法 也 写 出 来 。 但 这 篇 文 章 已 经 太 长 ， 而 且 我 想 有 些 读 者 在 看 了 前 面 的 解 后 说 不 定 想 自 己 再 试 一 试 。 所 以 我 们 这 期 暂 时 不 写 ， 希 望 有 读 者 能 解 出 来 。 下 面 是 本 期 的 题 目 。 前 面 写 了 一 大 堆 ， 本 期 题 目 就 没 有 正 文 了 。 这 次 的 题 目 有 点 类 似 于 上 次 在 《 于 无 声 处 听 惊 雷 》 里 的 题 目 ， 不 过 味 道 有 些 不 同 ， 数 学 性 更 浓 一 点 。
|
Please write your anwser using the following form or reguler E-mail if you prefer.