参 赛 队 员 : 杨 燊 谢 皓 何 振 梁 学 校 : 广 东 实 验 中 学 省 份 : 广 东 省 指 导 教 师 : 程 建 华 论 文 题 目 : 从 游 戏 都 市 摩 天 楼 引 出 的 组 合 图 论 问 题 及 扩 展
论 文 题 目 : 从 游 戏 都 市 摩 天 楼 引 出 的 组 合 图 论 问 题 及 扩 展 摘 要 : 本 文 研 究 的 是 从 手 机 游 戏 都 市 摩 天 楼 引 申 出 来 的 一 个 有 趣 组 合 图 论 问 题 及 其 扩 展, 其 游 戏 规 则 是 在 规 定 的 5*5 的 格 阵 中 通 过 摆 放 不 同 颜 色 且 承 载 人 口 数 不 同 的 楼 房 ( 各 种 颜 色 的 楼 房 摆 放 规 则 各 不 相 同, 见 论 文 正 文 ), 目 的 是 使 人 口 总 量 尽 量 大 本 文 通 过 将 游 戏 简 化 成 数 学 模 型 从 而 进 行 分 析 和 证 明, 最 终 得 出 此 游 戏 的 最 优 化 结 局 及 其 扩 展 问 题 的 算 法 关 键 词 : 都 市 摩 天 楼 人 口 总 量 最 优 化 算 法
Summary: This test discusses about an interesting issue of combinatory and graph theory & its extension which originates from a cell-phone game called Tower Bloxx(TM). The game rule is to make up different buildings according to different color and house holding of the building in a 5*5 matrix in order to make the population as large as possible. The text analyzes and proves the issue by simplifying the game to be a mathematical model, and finally concludes the best outcome of the game and algorithm of the extension Keyword: Tower Bloxx(TM) population the best algorithm
正 文 : 都 市 摩 天 楼 是 现 在 十 分 流 行 的 手 机 游 戏 (NOKIA 有 很 多 款 手 机 有 这 个 游 戏 ), 它 是 通 过 摆 放 不 同 的 楼 房, 目 的 是 在 规 定 的 5*5 的 格 阵 中 实 现 楼 房 可 承 载 总 人 数 最 大 化 在 大 家 为 这 款 有 趣 的 游 戏 疯 狂 时, 我 们 小 组 也 从 游 戏 中 发 现 了 一 个 非 常 有 趣 的 组 合 图 论 问 题, 于 是 就 开 始 了 对 此 的 研 究 与 扩 展 首 先, 我 们 先 介 绍 一 下 游 戏 规 则 : 场 地 :25 个 小 正 方 形 按 5*5 排 列 成 一 个 大 的 格 阵 人 口 承 载 量 由 小 到 大 : 蓝 红 绿 黄 楼 房 摆 放 规 则 :. 楼 房 放 置 在 矩 阵 中 任 意 一 个 小 正 方 形 ( 即 场 地 中 一 共 有 25 个 位 置 可 供 建 楼 选 择 );. 蓝 楼 可 以 随 便 放 ;. 红 楼 要 建 在 蓝 楼 旁 ;. 绿 楼 要 临 蓝 红 楼 建 造 ;. 黄 楼 要 周 围 有 蓝 红 绿 楼 才 可 以 建 造 游 戏 目 的 : 使 城 市 人 口 尽 可 能 大 下 面 先 转 载 一 些 玩 家 的 心 得 ( 这 些 心 得 只 限 于 便 于 研 究, 不 能 作 为 结 论 使 用 ) 1. 先 把 蓝 楼 铺 满, 这 样 盖 红 楼 就 方 便 了 ; 2. 盖 红 楼 时 就 要 考 虑 绿 楼 和 黄 楼 的 位 置 了 ; 3. 本 着 让 高 级 楼 尽 量 靠 边 角 的 原 则, 能 建 更 多 的 高 级 楼 ; 4. 到 规 模 大 时, 会 有 必 要 把 蓝 楼 和 红 楼 重 建 成 其 它 色 楼 的 ; 5. 不 防 先 设 计 一 下 各 阶 段 各 色 楼 的 分 布 情 形, 这 样 会 省 去 很 多 重 建 的 麻 烦 绿 红 红 蓝 绿 绿 黄 红 黄 绿 绿 黄 红 黄 绿 绿 黄 红 黄 绿 结 果 : 蓝 蓝 蓝 蓝 红 黄 蓝 蓝 蓝 黄 黄 绿 蓝 绿 黄 黄 绿 黄 绿 黄 黄 楼 :12 栋 红 红 蓝 红 红 > 红 红 蓝 红 红 > 红 红 蓝 红 红 > 红 黄 蓝 黄 红 > 绿 楼 :8 栋 红 蓝 蓝 蓝 蓝 黄 蓝 蓝 蓝 黄 黄 绿 蓝 绿 黄 黄 绿 黄 绿 黄 红 楼 :4 栋 绿 蓝 红 红 绿 绿 黄 红 黄 绿 绿 黄 红 黄 绿 绿 黄 红 黄 绿 蓝 楼 :1 栋 研 究 大 纲 : 一 都 市 摩 天 楼 的 建 设 城 市 最 理 想 布 局 ( 只 研 究 颜 色 数 量 关 系, 不 考 虑 布 局 总 数 ) 的 研 究 1. 两 色 2. 三 色 3. 四 色 二 扩 大 到 N N 的 城 市 方 格 的 推 论 下 面 是 我 们 对 这 一 项 目 的 研 究 : 我 们 首 先 把 它 简 化 成 的 数 学 模 型 :( 之 后 的 讨 论 都 将 用 数 字 代 替 颜 色 ) N N 的 方 格 阵 用 数 字 1-4 填 满 :1( 蓝 色 ) 2( 红 色 ) 3( 绿 色 ) 4( 黄 色 ), 目 的 : 数 字
和 达 到 最 大 * 其 中 1 随 便 填 * 填 入 2 的 时 候 旁 边 ( 相 邻 的 4 格 中, 斜 角 不 算 ) 必 须 有 1 * 填 入 3 的 时 候 旁 边 必 须 有 1 2 * 填 入 4 的 时 候 旁 边 必 须 有 1 2 3 * 但 是 填 入 后 可 以 替 换 掉 旁 边 的 低 阶 数 字, 比 如 一 个 4 旁 边 有 123, 其 中 2 的 旁 边 又 有 12 那 么 当 4 被 填 入 后,2 可 以 用 3 替 换 掉 Ⅰ 两 色 可 以 看 出, 这 是 一 个 比 较 复 杂 的 图 论 问 题, 为 了 清 晰 了 解 其 实 质 并 且 进 行 充 分 证 明 首 先, 我 们 先 从 只 有 两 色 的 情 况 进 行 分 析, 因 为 最 后 一 个 2 必 须 建 在 一 个 1 旁 边, 所 以 格 阵 中 至 少 有 一 个 1, 我 们 是 否 可 以 设 想 5 5 乃 至 N N 的 格 阵 中 可 以 建 出 只 有 一 个 1 最 理 想 情 况 于 是 我 们 经 过 实 际 操 作 之 后 可 以 证 明 这 一 点 是 可 行 的, 操 作 如 下 :( 画 圆 圈 的 是 要 改 动 的 ) 第 一 行 2 1 > 2 2 1 > 2 2 2 1 > 第 二 行 2 1 > 2 2 1 > 2 2 2 1 > 第 三 行 2 1 > 2 2 1 > 2 2 2 1 > 直 到 最 后 一 行 完 成, 格 阵 中 就 除 了 最 后 一 列 全 是 1 之 外, 其 余 都 是 2 了, 然 后 我 们 处 理 最 后 一 列 :( 我 们 将 其 定 为 5 格 ) 1 2 2 2 2 1 1 2 2 2 1 > 1 > 1 > 2 > 2 1 1 1 1 2 1 1 1 1 1 这 样, 我 们 就 完 成 只 有 一 个 1 其 余 全 是 2 的 最 理 想 请 况 了, 同 时 我 们 可 以 得 出 : 结 论 A:(1) 2 在 格 阵 中 任 何 位 置 建 设 都 是 没 问 题 的, 只 要 保 证 有 一 个 1 存 在 因 此, 我 们 在 考 虑 有 3 和 4 得 情 况 时, 不 必 多 考 虑 2 的 建 设, 即 布 局 是 否 理 想 取 决 于 3 和 4 的 多 少 同 理 可 得,(2) 格 阵 中 必 须 存 在 一 个 3 有 两 个 非 3 格 子 与 之 相 邻 II 三 色 在 分 析 完 两 色 之 后, 我 们 下 面 开 始 从 三 色 ( 蓝 红 绿 ) 分 析 : 在 分 析 的 时 候, 我 们 得 出 了 一 条 结 论 : 结 论 B:(1) 一 条 最 外 围 的 边 不 能 出 现 全 都 是 3 证 明 :B 假 设 一 条 的 外 围 边 全 是 3, 则 在 这 条 边 上, 设 任 一 个 3 为 最 后 铺 成 的 格 子, 此 格 子 必 须 有 两 个 与 之 相 邻 的 非 3 格 子 由 于 这 条 边 上 全 是 3, 可 知 每 个 格 子 只 存 在 一 个 非 3 格 子 与 之 相 邻 因 此 前 后 矛 盾, 假 设 不 成 立, 则 最 外 围 的
一 条 边 不 能 出 现 全 都 是 3 结 论 A 成 立 由 (1) 易 知, (2) 格 阵 最 外 围 的 所 有 边 上 至 少 要 存 在 两 个 非 3 格 子, 即 处 于 同 一 对 角 线 的 两 个 角 位 上 有 了 这 些 结 论, 我 们 就 可 以 借 助 他 们 让 下 面 的 分 析 简 单 化 了 : <1>. 由 于 三 色 情 况 比 较 复 杂, 我 们 先 从 2 2 开 始 : 明 显, 先 将 其 铺 成 除 一 个 1 外 全 是 2 ( 先 不 考 虑 重 建 次 数, 只 考 虑 布 局 最 优 化 ), 然 后 将 画 圈 的 两 个 2 重 建 成 3 即 能 达 到 最 理 想 布 局, 根 据 结 论 B(2) 可 知 操 作 如 下 : 1 2 > 1 3 2 2 3 2 <2>. 然 后, 我 们 就 研 究 3 3, 由 于 格 阵 是 对 称 的 图 形, 为 了 便 于 研 究 我 们 在 边 为 奇 数 的 格 阵 中 将 蓝 色 放 与 中 间, 操 作 如 下 : * 仍 先 将 格 阵 铺 成 除 一 个 1 外 全 是 2 2 2 2 2 2 2 3 2 2 3 3 2 2 1 2 > 1 1 1 > 1 1 1 > 3 1 3 2 2 2 2 2 2 2 2 3 2 3 3 经 过 以 上 操 作 之 后, 是 否 就 已 经 达 到 最 理 想 状 况 了 呢, 我 们 必 须 对 此 作 出 证 明 证 明 : (1) 1 已 经 达 到 最 少, 不 须 讨 论 ; (2) 上 图 格 阵 中 有 3 个 非 3 格 子, 是 否 能 减 少 一 个 变 成 3 呢 假 设 减 少 一 个 成 立, 根 据 结 论 B(2) 与 第 (1) 点 证 明, 即 剩 下 存 在 一 个 1 和 一 个 2 在 处 于 同 一 对 角 线 的 两 个 角 位 上, 此 时 与 结 论 A(2) 矛 盾, 则 假 设 不 成 立, 即 上 图 是 最 理 想 状 况 可 知 这 已 经 是 最 理 想 的 情 况 了 (* 在 此 只 考 虑 理 想 布 局 的 颜 色 数 量 关 系, 不 考 虑 理 想 布 局 的 个 数 提 供 另 外 一 种 理 想 布 局 ) 1 3 2 3 3 3 2 3 3 <3>. 下 面 就 是 4 4 的 情 况, 一 : 假 设 有 一 个 角 位 为 2, 且 这 个 角 位 的 两 条 外 围 边 除 了 那 一 个 2 之 外 全 都 是 3 如 此 一 来, 则 可 将 格 阵 分 为 两 个 独 立 的 部 分, 一 部 分 是 那 两 条 外 围 边 ( 蓝 色 部 分 ), 另 一 部 分 是 剩 下 的 3 3 的 格 阵 ( 红 色 部 分 ), 如 下 图 因 为 与 红 色 部 分 相 邻 的 都 是 3 ( 根 据 游 戏 规 则, 3 对 1 2 3 的 建 设 没 帮 助 ), 所 以 不 影 响 红 色 部 分 的 建 设 ( 如 一 堵 墙 ) 使 内 部 成 为 一 个 独 立 的 3 3 的 格 阵 ( 即 可 按 照 <2> 所 证 3 3 的 最 理 想 情 况 布 局 ), 再 加 上 外 围, 就 是 4 4 的 最 理 想 情 况 了 2 3 3 3
3 2 3 3 3 3 1 3 3 3 3 2 二 : 但 是, 若 是 两 条 相 邻 的 外 围 边 除 了 角 位 的 一 个 2 之 外, 还 有 其 他 2 呢? 我 们 就 要 将 这 种 情 况 与 以 上 的 假 设 一 对 比 了 我 们 假 设 将 上 图 的 布 局 改 动, 将 外 围 边 的 任 一 个 3 换 成 2, 外 围 边 其 它 不 变 ( 使 其 不 符 合 假 设 一 ) 如 图 ( 画 圈 的 是 将 要 换 色 的 ), 而 2 只 可 能 支 持 2 变 成 3, 所 以 外 围 边 的 一 个 3 换 成 2 后, 而 3 3 与 其 相 接 的 部 分 至 多 只 能 将 一 个 2 色 换 成 一 个 3, 即 3 的 数 量 不 变 ( 有 一 种 情 况 是 2 可 以 支 持 放 置 在 3 3 角 位 的 1 变 成 3, 但 1 是 至 少 有 一 个 的, 因 此 在 其 它 位 置 必 定 会 有 1, 所 以 此 种 改 动 不 必 要 ) 2 3 3 3 2 2 3 3 2 2 3 3 3 2 3 3 3 2 3 3 3 3 3 3 3 3 1 3 > 3 3 1 3 > 3 3 1 3 3 3 3 2 3 3 3 2 3 3 3 2 明 显 看 出, 若 将 3 3 的 部 分 看 作 独 立, 则 其 外 围 就 出 现 了 全 是 3, 又 可 将 3 3 的 部 分 分 为 了 两 个 独 立 的 两 个 小 部 分, 就 是 3 3 的 外 围 ( 红 色 ), 和 2 2 的 小 部 分, 则 可 用 2 2 的 理 想 布 局 解 决 这 表 明, 若 4 4 的 外 围 换 多 些 2 后, 最 多 也 只 能 以 3 3 的 部 分 的 外 围 补 充 相 同 数 量 的 3, 最 多 只 能 与 假 设 一 理 想 情 况 相 等 因 此 可 得 出 的 结 论 是 假 设 是 一 种 最 理 想 的 情 况 假 设 一 是 最 理 想 情 况 成 立 下 面 我 们 就 以 实 际 操 作 证 实 : 2 2 2 2 2 2 2 2 2 2 2 3 2 2 3 3 2 3 3 3 2 2 2 2 2 1 1 1 2 1 1 1 2 1 1 1 3 1 1 1 2 2 1 2 > 2 1 1 2 > 2 1 1 2 > 3 1 1 2 > 3 1 1 2 2 2 2 2 2 1 2 2 3 1 2 2 3 1 2 2 3 1 2 2 这 样 外 围 就 完 成 了, 而 3 3 的 部 分 就 和 点 <2>. 中 的 操 作 一 样, 就 可 以 完 成 4 4 的 最 理 想 布 局 了, 如 下 : 2 3 3 3 3 2 3 3 3 3 1 3 3 3 3 2 <4>. 经 过 以 上 分 析, 我 们 可 以 得 出,4 4 的 最 理 想 布 局 可 以 由 3 3 的 最 理 想 布 局 推 出 我 们 再 一 步 分 析, 是 否 5 5 的 最 理 想 布 局 可 以 由 4 4 的 最 理 想 布 局 推 出 呢? 答 案 是 : 可 以 的 我 们 可 以 仿 照 证 明 4 4 的 最 理 想 布 局 的 方 法, 可 将 N N 的 格 阵 分 为 外 围 和 (N-1) (N-1) 的 两 个 独 立 部 分, 以 (N-1) (N-1) 的 最 理 想 布 局 推 出 N N 格 阵 的 最 理 想 布 局, 因 此, 我 们 可 以 从 3 格 阵 的 最 理 想 布 局 将 任 何 N N 格 阵 的 最 理 想 布 局 ( 注 意 : 此 种 乃 其 中 一 种 最 理 想 情 况 的 布 局 ) 并 且, 我 们 可 以 从 图 中 观 察 出 各 种 颜 色 的 数 目 关 系 : 蓝 :1 个 ; 红 :(N-1) 个 ; 绿 :(N^2-N) 个 因 为 2 2,3 3,4 4 都 符 合 假 设 在 N N 格 阵 中 的 最 理 想 情 况, 符 合 上 述 规 律, 即 有 一 个 1,(N-1) 个 2, (N^2-N) 个 3 (N-1) (N-1) 亦 符 合 证 明 在 (N+1) (N+1) 格 阵 中 的 最 理 想 情 况, 有 一 个 1,N 个 2, (N+1)
^2-(N+1) 个 3 证 明 : 假 设 一. 假 设 有 一 个 角 位 为 2, 且 这 个 角 位 的 两 条 外 围 边 除 了 那 一 个 2 之 外 全 都 是 3 如 此 一 来, 则 可 将 格 阵 分 为 两 个 独 立 的 部 分, 一 部 分 是 那 两 条 外 围 边 ( 蓝 色 部 分 ), 另 一 部 分 是 剩 下 的 N N 的 格 阵 ( 红 色 部 分 ), 如 下 图 因 为 与 红 色 部 分 相 邻 的 都 是 3 ( 根 据 游 戏 规 则, 3 对 1 2 3 的 建 设 没 帮 助 ), 所 以 不 影 响 红 色 部 分 的 建 设 使 内 部 成 为 一 个 独 立 的 N N 的 格 阵 ( 即 可 按 照 题 设 的 N N 的 最 理 想 情 况 布 局 ), 再 加 上 外 围, 就 是 (N+1) (N+1) 的 最 理 想 情 况 了 ( 下 图 为 假 设 一 的 布 局 ) 即 2 3 3 3 1, 一 个 ; 3 2 3 3 2,(N-1)+1=N 个 ; 3 3 2 3 3,(N^2-N)+2*N = (N+1)^2-(N+1) 个 3 N 个 3 3 3 3 3 3 1 N 个 3 符 合 题 意 假 设 二. 我 们 假 设 将 上 图 的 布 局 改 动, 将 外 围 边 的 任 一 个 3 换 成 2, 外 围 边 其 它 不 变 ( 使 其 不 符 合 假 设 一 ) 如 图 ( 画 圈 的 是 将 要 换 色 的 ), 而 换 了 之 后 的 2 只 可 能 支 持 2 变 成 3, 所 以 外 围 边 的 一 个 3 换 成 2 后, 而 3 3 与 其 相 接 的 部 分 至 多 只 能 将 一 个 2 色 换 成 一 个 3, 即 3 的 数 量 不 变 2 3 3 3 2 2 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 2 3 3 N 个 3 > 3 3 3 3 3 3 3 1 3 3 3 1 N 个 3 明 显 看 出, 若 将 N N 的 部 分 看 作 独 立, 则 其 外 围 就 出 现 了 全 是 3, 又 可 将 N N 的 部 分 分 为 了 两 个 独 立 的 两 个 小 部 分, 就 是 N N 的 外 围 ( 红 色 ), 和 (N-1) (N-1) 的 小 部 分, 则 可 用 (N-1) (N-1) 的 理 想 布 局 解 决 ( 即 3 数 量 不 变 ) 这 表 明, 若 (N+1) (N+1) 的 外 围 换 多 些 2 后, 最 多 也 只 能 以 N N 的 部 分 的 外 围 补 充 相 同 数 量 的 3, 最 多 只 能 与 假 设 一 理 想 情 况 相 等 因 此 可 得 出 的 结 论 是 假 设 一 是 一 种 最 理 想 的 情 况 这 样, 我 们 就 完 成 了 3 色 建 楼 关 于 N N 格 阵 的 最 理 想 布 局 的 推 导 了
III. 四 色 接 下 来, 就 是 我 们 最 后 的 4 色 研 究 了,4 色 又 比 三 色 多 了 一 种 颜 色, 则 是 更 加 复 杂 了, 我 们 也 从 较 小 的 格 阵 中 开 始 分 析 1. 先 是 3 3 的 情 况, 在 之 前 已 经 有 提 供 过 一 种 4 色 5 5 的 较 理 想 的 布 局, 仍 是 1 只 有 1 个, 于 是 我 们 以 至 少 的 一 个 1 为 准, 1 能 够 影 响 所 有 颜 色 的 建 设, 因 此, 我 们 把 至 少 的 一 个 1 放 在 中 间, 而 角 位 是 无 法 建 4 的, 所 以 我 们 在 角 位 上 尽 可 能 地 建 上 3 现 在 我 们 开 始 分 析 : 最 后 一 个 4 要 建 在 与 一 个 3 2 1 都 相 邻 的 位 置, 并 且 也 只 能 建 在 每 条 边 的 中 间 位 置 了, 那 与 其 相 邻 的 1 必 定 就 是 中 间 的 一 个 了, 而 角 位 也 必 会 出 现 2 了, 明 显, 理 想 的 布 局 如 下 : 2 4 3 4 1 4 3 4 2 实 际 操 作 如 下 : 2 2 2 3 2 2 2 4 3 1 1 1 > 1 1 1 > 4 1 4 2 2 2 2 2 3 3 4 2 2. 经 过 以 上 3 3 的 分 析, 我 们 可 以 清 晰 了 解 到 两 点 : 第 一, 至 少 需 要 的 一 个 1 是 必 须 充 分 利 用 的, 就 是 说, 这 个 与 这 4 的 相 邻 的 四 个 格 子 都 建 上 要 4 ; 第 二, 角 位 尽 可 能 地 建 绿 色 ; 外 加 的 第 三 点 就 是 最 外 围 的 边 上 的 4 无 法 与 另 一 4 相 邻, 因 为 外 围 边 上 的 格 子 除 角 外, 都 只 有 三 个 格 子 与 其 相 邻, 而 在 这 些 格 子 上 建 4, 必 须 相 邻 的 三 个 格 子 分 填 上 3 2 1, 则 两 4 不 能 相 邻 然 后 我 们 分 析 4 4 的 布 局 我 们 先 进 行 实 际 操 作 : 3 2 2 3 3 4 2 3 3 4 2 3 3 4 2 3 3 4 2 3 1 1 2 1 4 1 2 2 4 1 2 2 4 1 2 2 4 1 4 2 1 1 1 1 > 2 1 1 1 > 2 1 1 4 > 2 1 3 4 > 2 4 3 4 3 2 2 3 3 2 4 3 3 2 4 3 3 2 4 3 3 2 4 3 明 显 看 出, 4 的 个 数 已 经 是 最 大 化 了, 而 现 在 就 在 于 在 这 个 基 础 上, 3 的 个 数 是 否 也 已 经 达 到 了 最 大 化 现 在 的 布 局 中, 有 4 个 2, 而 且 都 是 再 外 围 边 上 的 我 们 试 着 将 一 个 2 换 成 3, 如 下 : 3 4 2 3 3 4 3 3 4 1 4 2 4 1 4 2 2 4 3 4 > 2 4 3 4 3 2 4 3 3 2 4 3 接 下 来, 我 们 来 分 析 它 的 可 行 性 首 先, 4 的 建 立 是 在 作 为 基 底 的 其 他 三 种 数 字 之 后 的, 就 是 说, 建 4 之 前, 必 须 在 相 邻 的 位 置 建 好 其 余 三 数 在 上 图 中, 标 红 色 的 3 旁 边 的 4 ( 外 围 边 上 的 一 个 ), 在 建 4 之 前 必 须 有 1 2 3 与 其 相 邻, 在 图 中 1 3 已 经 具 备, 没 有 2, 则 证 明 了 红 色 的 3 是 由 2 重 建 的, 而 建 3 之 前, 又 必 须 有 1 2, 因 此 3 ( 标 为 3) 旁 边 的 3 ( 标 记 为 3``) 一 定 是 又 是 由 2 或 1 重 建 的, 而 同 样 道 理, 也 必 须 有 2 和 1 相 邻, 但 别 无 选 择, 可 以 改 动 的 格 子 只 由 3`` 下 面 的 一 个
了, 因 此, 无 法 重 建 出 3`` 最 大 可 能 也 只 可 以 在 那 个 位 置 上 建 2 因 此 改 动 是 不 成 立 的 此 种 情 况 是 最 理 想 状 况 3. 我 们 现 在 来 分 析 5 5 的 情 况, 在 之 前 转 载 玩 家 心 得 的 时 候, 已 经 有 了 5 5( 这 是 原 游 戏 的 格 阵 ) 的 操 作 了, 我 们 不 妨 一 看 : 3 2 2 2 3 3 4 2 4 3 3 4 2 4 3 3 4 2 4 3 1 1 2 1 1 4 1 1 1 4 4 3 1 3 4 4 3 4 3 4 2 2 1 2 2 > 2 2 1 2 2 > 2 2 1 2 2 > 2 4 1 4 2 1 1 2 1 1 4 1 1 1 4 4 3 1 3 4 4 3 4 3 4 3 2 2 2 3 3 4 2 4 3 3 4 2 4 3 3 4 2 4 3 这 时, 大 家 是 否 有 发 现 规 律 呢? 就 是 无 论 是 横 排 还 是 竖 排, 每 一 排 上 的 4 都 是 相 隔 着 放 的, 并 且 无 论 将 任 何 一 个 非 4 的 数 字 换 成 4, 都 会 出 现 3 个 4 相 邻, 明 显, 这 是 不 能 成 立 的 这 是 否 能 够 证 明 了 4 已 经 到 达 了 最 大 化? 这 规 律 是 否 能 推 广 到 N N 呢? 我 们 再 接 着 分 析 这 个 图, 绿 色 是 否 也 达 到 最 大 化? 我 们 再 来 研 究 7 7 的 布 局 然 后 再 作 分 析 4. 7 7 的 布 局, 仿 照 5 5 的 操 作 方 法, 作 出 7 7 的 布 局 : 3 2 2 1 2 2 3 3 4 2 1 2 4 3 3 4 2 1 3 4 3 1 1 1 1 1 1 1 4 1 1 1 1 1 4 4 3 1 1 1 3 4 2 2 1 1 1 2 2 2 2 1 1 1 2 2 2 2 1 1 1 2 2 1 1 1 1 1 1 1 > 1 1 1 1 1 1 1 > 1 1 1 1 1 1 1> 2 2 1 1 1 2 2 2 2 1 1 1 2 2 3 2 1 1 1 2 3 1 1 1 1 1 1 1 4 1 1 1 1 1 4 4 3 1 1 1 3 4 3 2 2 1 2 2 3 3 4 2 1 2 4 3 3 4 2 1 3 4 3 3 4 2 4 3 4 3 3 4 2 4 3 4 3 3 4 2 4 3 4 3 4 3 1 1 1 3 4 4 3 4 1 2 3 4 4 3 4 2 2 3 4 2 2 1 1 1 2 2 2 4 1 1 1 4 2 2 4 1 1 1 4 2 4 1 1 1 1 1 4 > 4 2 1 1 1 2 4 > 4 2 1 1 1 2 4> 3 2 1 1 1 2 3 3 2 1 1 1 2 3 3 2 1 1 1 2 3 4 3 1 1 1 3 4 4 3 4 1 2 3 4 4 3 2 2 4 3 4 3 4 2 4 3 4 3 3 4 2 4 3 4 3 3 4 2 4 3 4 3 3 4 2 4 3 4 3 3 4 2 4 3 4 3 3 4 2 4 3 4 3 4 3 4 2 4 3 4 4 3 4 2 4 3 4 4 3 4 2 4 3 4 2 4 1 2 1 4 2 2 4 3 2 3 4 2 2 4 3 4 3 4 2 4 2 1 1 1 2 4 > 4 2 1 1 1 2 4 > 4 2 4 1 4 2 4 3 4 1 2 1 4 3 3 4 3 2 3 4 3 3 4 3 4 3 4 3 4 3 4 2 4 3 4 4 3 4 2 4 3 4 4 3 4 2 4 3 4 3 4 2 4 3 4 3 3 4 2 4 3 4 3 3 4 2 4 3 4 3 从 最 后 的 布 局 可 看 到,7 7 的 格 阵 也 是 能 做 到 横 排 竖 排 黄 色 相 隔 的 状 况, 而 且 这 种 排 布 的 一 种 方 法 还 是 很 有 规 律 的,. 如 下 图 的 颜 色 分 布 : 3 4 2 4 3 4 3
4 3 4 2 4 3 4 2 4 3 4 3 4 2 4 2 4 1 4 2 4 3 4 3 4 3 4 3 4 3 4 2 4 3 4 3 4 2 4 3 4 3 排 布 时, 我 们 所 采 用 的 方 法 是 先 从 最 外 层 处 理, 将 最 外 层 建 成 4 角 是 3, 然 后 4 相 隔 着 放, 而 每 一 条 边 都 有 一 个 2, 共 有 4 个 2, 然 后 再 里 面 一 层 亦 是 如 此, 到 最 后 的 5 5(N 为 奇 数 ) 或 4 4(N 为 偶 数 ) 时 就 利 用 他 们 的 最 理 想 状 况 的 排 布 就 可 以 了 或 者 另 一 种 理 解 就 是 N N 的 格 阵 中 镶 嵌 了 (N-2) (N-2) 的 格 阵, 如 此 类 推, 则 可 用 5 5 或 4 4 的 格 阵 的 理 想 状 况 推 出 任 何 N N 的 理 想 状 况 了 但 是, 最 后 一 个 问 题 就 是 这 是 否 是 最 理 想 的 状 况 了 呢? 这 时 我 们 必 须 证 明 两 点 : 1. 每 一 横 排 竖 排 黄 色 都 相 隔 得 排 法 是 黄 色 个 数 最 大 值 化 的 排 法 ; 2. 在 点 1. 的 基 础 上, 每 一 层 都 有 4 个 2 ( 每 边 一 个 ) 是 使 3 个 数 最 大 化 的 排 法 这 是 我 们 的 证 明 : 证 明 :1. 这 个 证 明 在 之 前 5 5 的 讨 论 中 已 经 提 到 过, 就 是 因 为 无 论 是 横 排 还 是 竖 排, 每 一 排 上 的 4 都 是 相 隔 着 放 的, 并 且 无 论 将 任 何 一 个 非 4 的 数 字 换 成 4, 都 会 出 现 3 个 4 相 邻, 明 显, 这 是 不 能 成 立 的 因 为 已 经 无 法 在 增 加 4 数 量, 因 此 这 就 是 4 最 大 化 的 排 法 2. 我 们 利 用 图 来 证 明 : 3 4 2 4 3 4 3 3 4 3 4 3 4 3 4 3 4 2 4 3 4 4 3 4 2 4 3 4 2 4 3 4 3 4 2 2 4 3 4 3 4 2 4 2 4 1 4 2 4 > 4 2 4 1 4 2 4 3 4 3 4 3 4 3 3 4 3 4 3 4 3 4 3 4 2 4 3 4 4 3 4 2 4 3 4 3 4 2 4 3 4 3 3 4 2 4 3 4 3 假 设 我 们 最 外 一 层 的 一 个 2 换 成 了 3 ( 绿 色 标 记 ), 而 在 建 3 时 必 须 相 邻 着 1 和 2, 因 此 相 邻 的 三 个 格 子 中, 比 必 有 两 个 是 1 和 2, 则 此 边 上 与 3 相 邻 的 两 个 4 至 少 有 一 个 是 由 1 或 2 重 建 的, 而 在 建 这 一 个 4 时, 相 邻 的 三 个 格 子 必 有 1 2 3, 而 且, 4 是 必 须 在 改 动 后 的 3 之 后 建 的, 因 此, 最 后 在 边 上 至 少 会 会 有 一 个 1 或 2 第 2 点 成 立 5. 经 过 以 上 一 系 列 的 分 析, 我 们 已 经 可 以 推 出 并 且 证 明 4 色 关 于 任 何 N N 的 最 理 想 状 况 是 的 颜 色 数 量 关 系, 和 一 种 理 想 状 况 的 排 布 方 法 最 后, 我 们 的 结 论 就 是 : 1.N=3 时, 蓝 :1 个 ; 红 :2 个 ; 绿 :2 个 ; 黄 :4 个 ; 2.N= 偶 数 (N 大 于 等 于 4) 蓝 :1 个 ; 红 :(2N-4) 个 ; 绿 :(N^2-4N+10)/2 个 ; 黄 :(N^2-4)/2 个 ;
3.N= 奇 数 (N 大 于 等 于 5) 蓝 :1 个 ; 红 :(2N-6) 个 ; 绿 :(N^2-4N+11)/2 个 ; 黄 : (N^2-1)/2 个 ; 尾 声 : 由 于 时 间 问 题 我 们 的 研 究 有 些 不 完 善, 我 们 发 现 了 关 于 最 理 想 情 况 的 布 局 数 推 广 到 任 意 图 上, 如 nxm 格 子,n 不 等 于 m 的 布 局 如 何 保 证 重 建 尽 量 少 推 广 到 有 M 个 等 级 的 楼 的 情 况 等 值 得 研 究 的 问 题, 但 无 法 完 成, 希 望 以 后 有 机 会 继 续 深 入 在 作 品 制 作 和 研 究 的 过 程 中, 队 员 们 互 相 学 习, 互 相 鼓 励, 体 现 出 我 们 团 体 可 贵 的 团 队 精 神 经 过 不 断 的 研 究 和 交 流, 在 队 员 们 的 努 力 拼 搏 下, 参 赛 作 品 终 于 完 成 由 于 时 间 紧 促, 我 们 作 品 的 一 些 证 明 不 免 会 有 写 疏 漏, 证 法 也 许 也 不 够 严 谨, 这 是 我 们 团 队 的 一 大 遗 憾 当 然, 我 们 参 加 比 赛 的 意 义 不 仅 仅 是 为 了 比 赛 而, 而 是 为 了 锻 炼 我 们 的 思 维, 学 习 更 多 的 知 识, 提 高 对 数 学 研 究 的 兴 趣, 很 高 兴, 我 们 都 感 受 到 了 在 数 学 海 洋 中 艰 辛 打 捞 的 宝 贵 成 果 在 日 后 的 生 活 中, 我 们 也 将 以 这 一 份 热 情 挑 战 每 一 天
参 考 文 献 :( 无 ) 如 果 有 需 要, 最 后 可 以 介 绍 团 队 成 员 简 历