轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 找头盔3 [打印本页]

作者: 墨叶 时间: 2011-12-21 00:09 标题: 找头盔3

源头：http://www.xycq.net/forum/thread-225830-1-1.html
题：有5个洞窟，排成一排，前一天晚上有人会在其中一个洞窟放一个头盔，次日白天你可以去找头盔，但是只能找一个洞窟，如果没有找到，那么那人会在晚上移动一次头盔，但是只能向右或者向左移动一格，必须移动，请给出一个方案，必定能够找到头盔。

引申：http://www.xycq.net/forum/thread-226001-1-1.html
题：有9个洞窟排成三行三列，前一天晚上有人会在其中一个洞窟放一个头盔，次日白天你可以去找头盔，但是只能找两个洞窟，如果没有找到，那么那人会在晚上移动一次头盔，但是只能向“前后左右”四个方向中的某个方向移动一格，必须移动，请给出一个方案，必定能够找到头盔。

新题1：立方体8个顶点。一个球在某一个点上。每一个回合，甲可以查看3个（原来错写成2个）点是否有球；查看完毕乙将球换到临近的一个点中。请给出一个方案，甲必定能够找到该球。（第一个给出完整答案的100TB）

新题2：立方体8个顶点和12条棱共20个点。一个球在某一个点中。每一个回合，甲可以查看3个点是否有球；查看完毕乙将球换到临近的一个点中。请给出一个方案，甲必定能够找到该球。（第一个给出完整答案的100TB）
注：球位于顶点时，可以跳到该顶点所在的棱的中点。
球位于某条棱的中点时，可以跳到该棱的二个端点。

新题3：立方体8个顶点、12条棱的中点和6个面的中心共20个点。一个球在某一个点中。每一个回合，甲可以查看n个点是否有球；查看完毕乙将球换到临近的一个点中。请问n的最小值，甲能使A必定能够找到该球。（第一个给出完整答案的500TB）
注：球位于顶点时，可以跳到该顶点所在的棱的中点。
球位于某条棱的中点时，可以跳到该棱的二个端点或者该棱所在面的中心。
球位于某个面的中点时，可以跳到该面的四条棱的中点。

本人用图像解题，提供本人解题用到的图。
不能上传附件，将附件放到以下位置。
http://www.xycq.net/forum/viewth ... ;page=11#pid3321611

[ 本帖最后由墨叶于 2011-12-21 08:21 编辑 ]

作者: 墨叶 时间: 2011-12-21 00:09 标题: 定义和定理

点：
球：每一个回合结束，球会移动到附近的一个点。
回合：每回合开始甲查看N个点。若所有的球均在这些点中，游戏结束；
      否则该回合结束，乙必须将所有球移动到临近的点上。
邻点与相邻：球能在一个回合从A点移动到的B点，则B点为A点的邻点。
               AB为相邻关系，用线段连结。任意点的邻点个数为该点的邻点数。
图：图包含所有点以及相邻点之间的连线。
白点：该回合不可能有球的点。条件为该点的所有邻点前一回合均为明点或者白点。
灰点与黑点：无法确定是否有球的点为灰点。多球状态有球的点为黑点。
明点：明点为该回合甲查看的点。每回合甲查看的明点的个数为定值，记为x。
起点：规定最早确定为一个白点的为起点。
                  第一个回合能确定多个点时选择邻点最少的点为起点。
                  一般情况下，选择邻点最少的点为起点。
奇（偶）点：从起点移动到该点需要的回合数一定为奇数（偶数），则该点为奇点（偶点）。
非奇非偶点：从起点移动到该点需要的回合数可以是奇数也可以是偶数，
               则该点为非奇非偶点，可简称为非点。
对称图：只有奇点和偶点，没有非点的图为对称图。
解：对一个确定的图和确定的球数。存在一个最小的N使甲能在有限回合之后必定能找到所有的球，则N为该图的解。
   明点取最小值N时，需要的最少回合数为P。则（N、P）为最优解。

定理：
1、N不少于邻点数的最小值。
2、若存在一种方式使对称图的所有奇点（或者偶点）为明点，则该图有解。

[ 本帖最后由墨叶于 2011-12-21 14:01 编辑 ]

作者: 墨叶 时间: 2011-12-21 00:10 标题: 常见对称图及答案

为了表述简单，本贴所有题都满足“总题干”。不同题M、N不同。不能保证答案完全正确。
总题干：某图形中有M个点。有线段连结的两点为邻点。
开始前乙将一个球放入任意一点。每回合开始甲查看N个点。若所有的球均在这些点中，游戏结束；
否则该回合结束，乙必须将所有球移动到邻点上。求以下各题的解，即甲能找到球的N的最小值。
题型一、一维。
题1：已知常数M。线段上有M个点，端点有1个邻点，其他的点均有2个邻点（M>1）。
解:N=1。

题2：已知常数M。闭合线段上有M个点，每个点均有2个邻点（M>2 ）。
解：N=2。

题型二、二维
题3：已知常数L，L>3。有一个2*（L-1）的矩形，均匀分布3*L个点。距离为1的两点为邻点。
即顶点有2个邻点，边上的点有3个邻点，中间的点有4个邻点。
解：N=2。

题4：已知常数A和L，L>2A-1。有一个（2A-2）*（L-1）的矩形，均匀分布（2A-1）*L个点。距离为1的两点为邻点。
即顶点有2个邻点，边上的点有3个邻点，中间的点有4个邻点。
解：N=A。

[ 本帖最后由墨叶于 2011-12-21 14:08 编辑 ]

作者: 墨叶 时间: 2011-12-21 00:11 标题: 典型非对称图分析

为了表述简单，本贴所有题都满足“总题干”。不同题M、N不同。不能保证答案完全正确。
总题干：某图形中有M个点。有线段连结的两点为邻点。
开始前乙将一个球放入任意一点。每回合开始甲查看N个点。若所有的球均在这些点中，游戏结束；
否则该回合结束，乙必须将所有球移动到邻点上。求以下各题的解，即甲能找到球的N的最小值。

题型一、三角形
题1：正三角形。答案：N=2

题2：正四面体。
等价图形：正三角以及中心点，且中心点与三个顶点相邻。答案：N=3

题3：梯形以及底边的中心，且底边的中点与四个顶点都相邻，底边的两个顶点不相邻。答案：N=3
等价图形：3个正三角形边重合得到的图形。

题4：正六边形及其中心，且中心点与所有顶点相邻。答案：N=3
等价图形：六棱锥。

题5：棱锥。答案：N=3

题6：三棱柱。答案：N=3

题7：四棱柱，即长方体、正方体。答案：N=3

题8：棱柱。答案：N=3

[ 本帖最后由墨叶于 2011-12-21 14:27 编辑 ]

作者: 墨叶 时间: 2011-12-21 00:11 标题: 两球问题分析

略

作者: zhouhuan 时间: 2011-12-26 20:59

貌似很难，而且还很专业

作者: dasha1989 时间: 2012-5-7 19:05

是不是说就是要27天……

作者: toushion 时间: 2012-7-15 19:10

这个里头全是精华啊。待俺慢慢学习。。好吃力的说。。

作者: toushion 时间: 2012-7-15 22:18

基本看懂了，就是不知道咋证明的

作者: 墨叶 时间: 2012-7-15 22:50 标题: 回复 #9 toushion 的帖子

严格证明很麻烦。用反证法可以大致说明结论的合理性。

作者: toushion 时间: 2012-7-16 17:17

题4：已知常数A和L，L>2A-1。有一个（2A-2）*（L-1）的矩形，均匀分布（2A-1）*L个点。距离为1的两点为邻点。
即顶点有2个邻点，边上的点有3个邻点，中间的点有4个邻点。

L>=2A-1也可以好像。以短边的一半去卡N就对了

试了一下4*4（3点）和6*6（4点）的分别需要12天和28天。。

方案通解是什么呢？

[ 本帖最后由 toushion 于 2012-7-16 17:29 编辑 ]

作者: 墨叶 时间: 2012-7-16 17:42 标题: 回复 #11 toushion 的帖子

我也没算。
二元的通解有点麻烦，可能还要分类。
思路不变。也没必要写通解。

作者: toushion 时间: 2012-7-16 17:50 标题: 回复 #12 墨叶的帖子

开始好像只要保证每个图的黑点比上一张多一个，就不会有错

详细步骤的通解会很麻烦，如果只求总天数，感觉应该不会很难。。

[ 本帖最后由 toushion 于 2012-7-16 17:53 编辑 ]

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)