魔方吧·中文魔方俱乐部

标题: 以最少點決定唯一長方體問題的解题思路探讨 [打印本页]

作者: lulijie 时间: 2009-1-10 20:59:45 标题: 以最少點決定唯一長方體問題的解题思路探讨

以最少點決定唯一長方體問題
分为2步：
  1.  定点  从一个长方体的表面或棱上选N点。
  2. 构体  构造出新的长方体，这N个点都在它的表面或棱上。（新的长方体不能和原长方体重合。）
   若不能构造出至少1个新的长方体，就称构体不成功。
若N点选好后，构体不成功，我们就称定点成功。
以最少點決定唯一長方體問題就可表示成：
求定点成功的N 的最小值。
--
---------------------------------------
定点问题：

N=9能否定点成功呢？
要想定点成功，长方体的每个面上都至少要选择1个点（这个点还不能在棱上）。不然，那么至少有一个面上，没有点，那么沿着这个面的垂直方向延伸的任何长方体都符合条件（N个点都在它的表面或棱上），故肯定定点不成功。
这样已经6点定好了，还有3点如何定呢，都选在一个面上，那么就是111114类型，若分在两个面上，就是111123类型，若分在三个面上，就是111222类型。
   （abcdef类型表示，6个面上分别有a、b、c、d、e、f个点），若有点既在一个面上又在另个面上（即在棱上），那么无论算在哪个面上都可以。
所以要定点成功，只有3个类型：
111114类型    这个类型很容易被大家忽视。
111123类型
111222类型
这三个类型无论哪个类型能定点成功，那么所求最小值就不会大于N（=9），若再能排除 N=8能定点成功，那么最小值就是9.
若无论哪个类型都不能定点成功，那么最小值只能大于9了。

大家讨论的最多的是 111123类型和111222类型，无论那种都没关系，只要能定点成功就可，但若都不成功，那么还不能得出最小值大于9，还要讨论111114类型能不能定点成功。
------------------------------------------------------------------
构体问题：

很多人在这个步骤都受到了原长方体的影响，比如原来定点是111123类型，那么认为构出的新长方体也是该类型，这是不对的。
我们构造新的长方体，不应受原长方体的影响，那么这N个点在新长方体各面的分布又是如何呢？
是不是也要求每个面上必须至少有1个点，没有，绝对没有，构体条件中没有这样要求。（但万一你构出了这样的一个新的长方体，也就能  够出无数个长方体了，朝没点的面延长长方体即可。）所我们定点时一定要注意。
下面分析一下它的可能分布类型：
9个点，没有4点共面（定点111114类型除外），故每个面的点最多3点。
我们要构体成功，一定要排除所有的可能分布类型。
构体类型可能如下：
333000类型  每3点确定1个面，9点能确定3个平面，但它们是不是互相垂直就不尽然，可通过定点让它构体不成功。
332100类型  从9点中先任取3点确定一个面，另取3点确定另一个面，我们可以通过定点让这两个面都不能垂直或平行，也就是构体不能成功。
331110类型  道理同332100类型。
222210类型  9个点中先任取2点，可定无数个平面，另2点定无数个平面，再2点定无数个平面，但要求它们3个面两两垂直，只能有有限数个组合。这样过剩下的3点中的任一点，作前3个面的平行面或垂直面，不一定通过最后剩下的2点中的任一点，，故就和4个面上各有2点不符合，故通过定点，可使该类型的构体不成功。
322200类型  道理同222210类型
322110类型  从9点中先任取3点确定一个面，再通过其他2点与前面的面垂直的面唯一确定，再通过另外2点与第一个面垂直的面也唯一确定，而让后两个面刚好垂直或平行，可以通过定点让它不可能。故通过定点可让这种类型不成功。
222111类型
321111类型
----------------------------------------------------------
因此我们要想定点成功，只要讨论后两种类型，即222111类型和321111类型。
若这两种类型定点不成功，我们还要讨论（定点111114类型）。
构体321111类型：
32确定唯一的两个垂面，但3点和2点是任取的，共有  （9*8*7）/（1*2*3 ）  * （6*5）  /  （1*2） =1260种，过剩下的点作它们的平行面或垂面，以确定长方体的其他面，若出现平面分割点在两边的情况，这种组合就淘汰。  要一一淘汰这1260中组合，比红军长征还要苦啊。
由于这种类型我们可以通过作图，一一检验，有的放矢。（我们知道平面如何作出来）
构体222111类型：
222确定有限数个两两垂直的3个面（比如ABC3个面）。这些组合中若出现某个面把其他面的2点分割在两边，那么这个组合就必然构体不成功，就不必考虑。剩下的组合中，我们还剩下3点，我们先选前面定好的3个面中的任何一面（比如A面），以这3点各作该面的平行面（D，X,Y），在最外面的那个平行面(D面)就是我们要定的长方体的一个面（若不是，而是其他两个平面X，Y中的一个，那么这个平面必然把空间的9点分割在平面的两边，就不符合要求了。）但若这个平行面D把前面的6个点分割在平面的两边，那么这个组合也必然构体不成功。然后过剩下2点，，作B面的平行面，取最外的平行面，若出现分割两边的情况，也淘汰，过最后1点作C面的平行面，若出现分割两边的情况，也淘汰。上述步骤中只要有一步出现平面分割点在两边的情况，这种组合就淘汰。故定点能否淘汰构体222111类型的所有组合呢？
222确定的两两垂直的3个面，我们如何作出图来（以检验是否分割点在两边以及后3点作出的平行面或垂直面是否分割点在两边。）这第一步是难点。我们空口说无凭，说服力不够。

作者: 水磨鱼 时间: 2009-1-10 21:07:07

2. 构体构造出新的长方体，这N个点都在它的表面或棱上。（新的长方体不能和原长方体重合。）
若不能构造出至少1个新的长方体，就称构体不成功。
新的长方体不能和原长方体重合这是办不到的``

作者: lulijie 时间: 2009-1-10 21:52:57

构体222111类型其实比大家想象中复杂多了。
9个点中先任取2点（点A、点B），在M1面上，9*8/2=36种取法。又取2点（点C、点D），在M2面上，有7*6/2=21种取法。再取2点（点E、点F），在M3面上，有5*4/2=10种取法。总共有36*21*10/6=1260种。M1、M2、M3 三个面两两垂直，通过立方程组，代入法，最后化为1个一元二次方程，可能有0个、1个或2个解。（为了解这个，花了多大的功夫啊，最后，系数列出来都有1米长，也不知道前面解题过程中有没有把哪个数写错了，或正负号写错了，但不影响最后的方程是一元2次方程。）。M1、M2、M3三个面也可以有两个面平行，（这种情况大家忽略了），列出的方程同前面的方程形式一样，最后也化为1个一元二次方程，可能有0个、1个或2个解。也就是说取好ABCDEF点后，最多可能解出4种解。
也就是说构体222111类型要完全排除，要排除这最多1260*4=5040种组合。
大家千万不要想当然，就认为其他组合不可能，对每种组合都要一一排除。
难，解题难，要解骰迷这题难上加难。

作者: WenZhouRen 时间: 2009-1-10 23:48:28

排除321111类型，要1260种，排除222111类型，至少要5040种，这不是要命么？

作者: WenZhouRen 时间: 2009-1-10 23:55:58

楼主讲的新的长方体不能和原长方体重合
应该指两个长方体，不能完全一样（即形状大小和空间位置完全一样）。

作者: WenZhouRen 时间: 2009-1-11 00:41:08

我觉得321111类型和222111类型，无非就是先从9点中取6点，让它们构成3个面，确定了这3个面，另外3个面的3点，只要过每个点作前面确定的3个面的平行面或垂面就可，然后检验构造出的长方体合不合格就行了。而6点构成的3个面，其中大部分不合格，因为它们把点分隔在平面的两边。
因此讨论任意6点能否构成有效的长方体的3个面（有效是指任何一个面都不会把平面外其他点分隔在平面的两边）及有多少种可能，很有意义。这种可能性远比1260种，5040种少得多。但从9点中取6点，也有9*8*7/2*3=84种。

作者: 第8个小笼包 时间: 2009-1-11 12:16:57

我觉得不论是什么型的，关键是经过这些定点的平面不能把其余点分割在两个空间。能不能用不等式去表示呢？

作者: kexin_xiao 时间: 2009-1-11 14:19:00

一个问题衍生出这么多问题，看来魔方真是和数学有很大关系，这里的高手（数学）很多啊

作者: 骰迷 时间: 2009-1-11 16:00:07

噢，看來我只能旁觀了。樓主很牛。

作者: ggglgq 时间: 2009-1-11 23:58:14

　　
　　
　　
　　可以看得出 lulijie 具有很强的几何抽象能力。

没有时间仔细考虑，我初步认为 lulijie 1 楼提到的 222111、 321111 两个

构体问题类型的简化结果总结得很好。

　　
　　
　　
　　本想合并有关“最少点确定长方体问题”的所有帖子，但合并帖子反而更乱，

为尊重发帖人的个人意愿，我就不合并帖子了。只是对 lulijie 的这个超强主题

加精，对 以最少點決定唯一長方體問題 固顶处理，相关内容请发帖人自行在固顶

主题 以最少點決定唯一長方體問題 中链接说明。
　　
　　
　　
　　
　　
　　

作者: lulijie 时间: 2009-1-12 00:56:48

版主过奖了，我觉得noski具有更强的几何抽象能力，他举的那些构体例子，比如三角形、正三角形，都能击中题目的要害，非常让人信服。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)