第一页为封面

Size: px

Start display at page:

Download "第一页为封面"

沣币冉
7 years ago
Views:

1 参赛队员 : 杨燊谢皓何振梁学校 : 广东实验中学省份 : 广东省指导教师 : 程建华论文题目 : 从游戏都市摩天楼引出的组合图论问题及扩展

2 论文题目 : 从游戏都市摩天楼引出的组合图论问题及扩展摘要 : 本文研究的是从手机游戏都市摩天楼引申出来的一个有趣组合图论问题及其扩展, 其游戏规则是在规定的 5*5 的格阵中通过摆放不同颜色且承载人口数不同的楼房 ( 各种颜色的楼房摆放规则各不相同, 见论文正文 ), 目的是使人口总量尽量大本文通过将游戏简化成数学模型从而进行分析和证明, 最终得出此游戏的最优化结局及其扩展问题的算法关键词 : 都市摩天楼人口总量最优化算法

房 ( 各种颜色的楼房摆放规则各不相同, 见论文正文 ), 目的是使人口总量尽量大本文通过将游戏简化成数学模型

3 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

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

4 正文 : 都市摩天楼是现在十分流行的手机游戏 (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( 黄色 ), 目的 : 数字

楼房放置在矩阵中任意一个小正方形 ( 即场地中一共有 25 个位置可供建楼选择 );. 蓝楼可以随便放 ;. 红楼要建在蓝楼旁 ;. 绿楼要临蓝红楼建造 ;.

5 和达到最大 * 其中 1 随便填 * 填入 2 的时候旁边 ( 相邻的 4 格中, 斜角不算 ) 必须有 1 * 填入 3 的时候旁边必须有 1 2 * 填入 4 的时候旁边必须有 * 但是填入后可以替换掉旁边的低阶数字, 比如一个 4 旁边有 123, 其中 2 的旁边又有 12 那么当 4 被填入后,2 可以用 3 替换掉 Ⅰ 两色可以看出, 这是一个比较复杂的图论问题, 为了清晰了解其实质并且进行充分证明首先, 我们先从只有两色的情况进行分析, 因为最后一个 2 必须建在一个 1 旁边, 所以格阵中至少有一个 1, 我们是否可以设想 5 5 乃至 N N 的格阵中可以建出只有一个 1 最理想情况于是我们经过实际操作之后可以证明这一点是可行的, 操作如下 :( 画圆圈的是要改动的 ) 第一行 2 1 > > > 第二行 2 1 > > > 第三行 2 1 > > > 直到最后一行完成, 格阵中就除了最后一列全是 1 之外, 其余都是 2 了, 然后我们处理最后一列 :( 我们将其定为 5 格 ) > 1 > 1 > 2 > 这样, 我们就完成只有一个 1 其余全是 2 的最理想请况了, 同时我们可以得出 : 结论 A:(1) 2 在格阵中任何位置建设都是没问题的, 只要保证有一个 1 存在因此, 我们在考虑有 3 和 4 得情况时, 不必多考虑 2 的建设, 即布局是否理想取决于 3 和 4 的多少同理可得,(2) 格阵中必须存在一个 3 有两个非 3 格子与之相邻 II 三色在分析完两色之后, 我们下面开始从三色 ( 蓝红绿 ) 分析 : 在分析的时候, 我们得出了一条结论 : 结论 B:(1) 一条最外围的边不能出现全都是 3 证明 :B 假设一条的外围边全是 3, 则在这条边上, 设任一个 3 为最后铺成的格子, 此格子必须有两个与之相邻的非 3 格子由于这条边上全是 3, 可知每个格子只存在一个非 3 格子与之相邻因此前后矛盾, 假设不成立, 则最外围的

少有一个 1, 我们是否可以设想 5 5 乃至 N N 的格阵中可以建出只有一个 1 最理想情况于是我们经过实际操作之后可以证明这一点是可行的, 操作如下 :( 画圆圈的是要改动的 ) 第一行 2 1 > 2 2 1 > 2 2 2 1 > 第二行 2 1 > 2 2

6 一条边不能出现全都是 3 结论 A 成立由 (1) 易知, (2) 格阵最外围的所有边上至少要存在两个非 3 格子, 即处于同一对角线的两个角位上有了这些结论, 我们就可以借助他们让下面的分析简单化了 : <1>. 由于三色情况比较复杂, 我们先从 2 2 开始 : 明显, 先将其铺成除一个 1 外全是 2 ( 先不考虑重建次数, 只考虑布局最优化 ), 然后将画圈的两个 2 重建成 3 即能达到最理想布局, 根据结论 B(2) 可知操作如下 : 1 2 > <2>. 然后, 我们就研究 3 3, 由于格阵是对称的图形, 为了便于研究我们在边为奇数的格阵中将蓝色放与中间, 操作如下 : * 仍先将格阵铺成除一个 1 外全是 > > > 经过以上操作之后, 是否就已经达到最理想状况了呢, 我们必须对此作出证明证明 : (1) 1 已经达到最少, 不须讨论 ; (2) 上图格阵中有 3 个非 3 格子, 是否能减少一个变成 3 呢假设减少一个成立, 根据结论 B(2) 与第 (1) 点证明, 即剩下存在一个 1 和一个 2 在处于同一对角线的两个角位上, 此时与结论 A(2) 矛盾, 则假设不成立, 即上图是最理想状况可知这已经是最理想的情况了 (* 在此只考虑理想布局的颜色数量关系, 不考虑理想布局的个数提供另外一种理想布局 ) <3>. 下面就是 4 4 的情况, 一 : 假设有一个角位为 2, 且这个角位的两条外围边除了那一个 2 之外全都是 3 如此一来, 则可将格阵分为两个独立的部分, 一部分是那两条外围边 ( 蓝色部分 ), 另一部分是剩下的 3 3 的格阵 ( 红色部分 ), 如下图因为与红色部分相邻的都是 3 ( 根据游戏规则, 3 对的建设没帮助 ), 所以不影响红色部分的建设 ( 如一堵墙 ) 使内部成为一个独立的 3 3 的格阵 ( 即可按照 <2> 所证 3 3 的最理想情况布局 ), 再加上外围, 就是 4 4 的最理想情况了

<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

7 二 : 但是, 若是两条相邻的外围边除了角位的一个 2 之外, 还有其他 2 呢? 我们就要将这种情况与以上的假设一对比了我们假设将上图的布局改动, 将外围边的任一个 3 换成 2, 外围边其它不变 ( 使其不符合假设一 ) 如图 ( 画圈的是将要换色的 ), 而 2 只可能支持 2 变成 3, 所以外围边的一个 3 换成 2 后, 而 3 3 与其相接的部分至多只能将一个 2 色换成一个 3, 即 3 的数量不变 ( 有一种情况是 2 可以支持放置在 3 3 角位的 1 变成 3, 但 1 是至少有一个的, 因此在其它位置必定会有 1, 所以此种改动不必要 ) > > 明显看出, 若将 3 3 的部分看作独立, 则其外围就出现了全是 3, 又可将 3 3 的部分分为了两个独立的两个小部分, 就是 3 3 的外围 ( 红色 ), 和 2 2 的小部分, 则可用 2 2 的理想布局解决这表明, 若 4 4 的外围换多些 2 后, 最多也只能以 3 3 的部分的外围补充相同数量的 3, 最多只能与假设一理想情况相等因此可得出的结论是假设是一种最理想的情况假设一是最理想情况成立下面我们就以实际操作证实 : > > > > 这样外围就完成了, 而 3 3 的部分就和点 <2>. 中的操作一样, 就可以完成 4 4 的最理想布局了, 如下 : <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)

而 3 3 与其相接的部分至多只能将一个 2 色换成一个 3, 即 3 的数量不变 ( 有一种情况是 2 可以支持放置在 3 3 角位的 1 变成 3, 但 1 是至少有一个的, 因此在其它位置必定会有 1, 所以此种改动不必要 ) 2 3 3 3 2 2 3 3 2 2 3 3

8 ^2-(N+1) 个 3 证明 : 假设一. 假设有一个角位为 2, 且这个角位的两条外围边除了那一个 2 之外全都是 3 如此一来, 则可将格阵分为两个独立的部分, 一部分是那两条外围边 ( 蓝色部分 ), 另一部分是剩下的 N N 的格阵 ( 红色部分 ), 如下图因为与红色部分相邻的都是 3 ( 根据游戏规则, 3 对的建设没帮助 ), 所以不影响红色部分的建设使内部成为一个独立的 N N 的格阵 ( 即可按照题设的 N N 的最理想情况布局 ), 再加上外围, 就是 (N+1) (N+1) 的最理想情况了 ( 下图为假设一的布局 ) 即 , 一个 ; ,(N-1)+1=N 个 ; ,(N^2-N)+2*N = (N+1)^2-(N+1) 个 3 N 个 N 个 3 符合题意假设二. 我们假设将上图的布局改动, 将外围边的任一个 3 换成 2, 外围边其它不变 ( 使其不符合假设一 ) 如图 ( 画圈的是将要换色的 ), 而换了之后的 2 只可能支持 2 变成 3, 所以外围边的一个 3 换成 2 后, 而 3 3 与其相接的部分至多只能将一个 2 色换成一个 3, 即 3 的数量不变 N 个 3 > 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 格阵的最理想布局的推导了

的都是 3 ( 根据游戏规则, 3 对 1 2 3 的建设没帮助 ), 所以不影响红色部分的建设使内部成为一个独立的 N N 的格阵 ( 即可按照题设的 N N 的最理想情况布局 ), 再加上外围, 就是 (N+1) (N+1) 的最理想情况了 ( 下图为假设一的布

9 III. 四色接下来, 就是我们最后的 4 色研究了,4 色又比三色多了一种颜色, 则是更加复杂了, 我们也从较小的格阵中开始分析 1. 先是 3 3 的情况, 在之前已经有提供过一种 4 色 5 5 的较理想的布局, 仍是 1 只有 1 个, 于是我们以至少的一个 1 为准, 1 能够影响所有颜色的建设, 因此, 我们把至少的一个 1 放在中间, 而角位是无法建 4 的, 所以我们在角位上尽可能地建上 3 现在我们开始分析 : 最后一个 4 要建在与一个都相邻的位置, 并且也只能建在每条边的中间位置了, 那与其相邻的 1 必定就是中间的一个了, 而角位也必会出现 2 了, 明显, 理想的布局如下 : 实际操作如下 : > > 经过以上 3 3 的分析, 我们可以清晰了解到两点 : 第一, 至少需要的一个 1 是必须充分利用的, 就是说, 这个与这 4 的相邻的四个格子都建上要 4 ; 第二, 角位尽可能地建绿色 ; 外加的第三点就是最外围的边上的 4 无法与另一 4 相邻, 因为外围边上的格子除角外, 都只有三个格子与其相邻, 而在这些格子上建 4, 必须相邻的三个格子分填上 3 2 1, 则两 4 不能相邻然后我们分析 4 4 的布局我们先进行实际操作 : > > > > 明显看出, 4 的个数已经是最大化了, 而现在就在于在这个基础上, 3 的个数是否也已经达到了最大化现在的布局中, 有 4 个 2, 而且都是再外围边上的我们试着将一个 2 换成 3, 如下 : > 接下来, 我们来分析它的可行性首先, 4 的建立是在作为基底的其他三种数字之后的, 就是说, 建 4 之前, 必须在相邻的位置建好其余三数在上图中, 标红色的 3 旁边的 4 ( 外围边上的一个 ), 在建 4 之前必须有与其相邻, 在图中 1 3 已经具备, 没有 2, 则证明了红色的 3 是由 2 重建的, 而建 3 之前, 又必须有 1 2, 因此 3 ( 标为 3) 旁边的 3 ( 标记为 3``) 一定是又是由 2 或 1 重建的, 而同样道理, 也必须有 2 和 1 相邻, 但别无选择, 可以改动的格子只由 3`` 下面的一个

地建上 3 现在我们开始分析 : 最后一个 4 要建在与一个 3 2 1 都相邻的位置, 并且也只能建在每条边的中间位置了, 那与其相邻的 1 必定就是中间的一个了, 而角位也必会出现 2 了, 明显, 理想的布局如下 : 2 4 3 4 1 4 3 4 2 实际

10 了, 因此, 无法重建出 3`` 最大可能也只可以在那个位置上建 2 因此改动是不成立的此种情况是最理想状况 3. 我们现在来分析 5 5 的情况, 在之前转载玩家心得的时候, 已经有了 5 5( 这是原游戏的格阵 ) 的操作了, 我们不妨一看 : > > > 这时, 大家是否有发现规律呢? 就是无论是横排还是竖排, 每一排上的 4 都是相隔着放的, 并且无论将任何一个非 4 的数字换成 4, 都会出现 3 个 4 相邻, 明显, 这是不能成立的这是否能够证明了 4 已经到达了最大化? 这规律是否能推广到 N N 呢? 我们再接着分析这个图, 绿色是否也达到最大化? 我们再来研究 7 7 的布局然后再作分析的布局, 仿照 5 5 的操作方法, 作出 7 7 的布局 : > > > > > > > > 从最后的布局可看到,7 7 的格阵也是能做到横排竖排黄色相隔的状况, 而且这种排布的一种方法还是很有规律的,. 如下图的颜色分布 :

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 这时, 大家是否有发现规律呢?

11 排布时, 我们所采用的方法是先从最外层处理, 将最外层建成 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. 我们利用图来证明 : > 假设我们最外一层的一个 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 个 ;

的理想状况了但是, 最后一个问题就是这是否是最理想的状况了呢? 这时我们必须证明两点 : 1. 每一横排竖排黄色都相隔得排法是黄色个数最大值化的排法 ; 2. 在点 1.

12 3.N= 奇数 (N 大于等于 5) 蓝 :1 个 ; 红 :(2N-6) 个 ; 绿 :(N^2-4N+11)/2 个 ; 黄 : (N^2-1)/2 个 ; 尾声 : 由于时间问题我们的研究有些不完善, 我们发现了关于最理想情况的布局数推广到任意图上, 如 nxm 格子,n 不等于 m 的布局如何保证重建尽量少推广到有 M 个等级的楼的情况等值得研究的问题, 但无法完成, 希望以后有机会继续深入在作品制作和研究的过程中, 队员们互相学习, 互相鼓励, 体现出我们团体可贵的团队精神经过不断的研究和交流, 在队员们的努力拼搏下, 参赛作品终于完成由于时间紧促, 我们作品的一些证明不免会有写疏漏, 证法也许也不够严谨, 这是我们团队的一大遗憾当然, 我们参加比赛的意义不仅仅是为了比赛而, 而是为了锻炼我们的思维, 学习更多的知识, 提高对数学研究的兴趣, 很高兴, 我们都感受到了在数学海洋中艰辛打捞的宝贵成果在日后的生活中, 我们也将以这一份热情挑战每一天

可贵的团队精神经过不断的研究和交流, 在队员们的努力拼搏下, 参赛作品终于完成由于时间紧促, 我们作品的一些证明不免会有写疏漏, 证法也许也不够严谨, 这是我们团队的一大遗憾当然, 我们参加比赛的

13 参考文献 :( 无 ) 如果有需要, 最后可以介绍团队成员简历

,,,, (,, - ;, ;, ;, ;, ;,, - ;, - ) (,, ~ ),,,, (, ),,,, ( ), () () ( ),,,,,,,.,, :.,. (,, ) : ( ), ;( ), ;( ) ;( ), :.,. %(,, ),,,,, (,, - ) :( ) ( )

,,,, (,, - ;, ;, ;, ;, ;,, - ;, - ) (,, ~ ),,,, (, ),,,, ( ), () () ( ),,,,,,,.,, :.,. (,, ) : ( ), ;( ), ;( ) ;( ), :.,. %(,, ),,,,, (,, - ) :( ) ( ) * 张文宏阮丹青内容提要 : 本文运用年天津城乡居民社会网的问卷调查资料, 对市民和农民的社会支持网进行了比较研究我们的研究发现 :( ) 亲属在城乡居民的财务支持网中发挥着非常重要的作用 ( ) 亲属在精神支持网中的作用也