问答 逻辑推理类-《乔迁之期》√已有答案√欢迎拓展和应用√

horky

楼上2位的理论太高深，一下子搞不明白。

不过为什么不看过了我的答案再说呢？

我可是画了表格，用纸写上家具名称动手验算过了。

提醒一下：题目只要求对换冰箱和床的位置，至于别的家具的位置怎么变换，是否可以放进房间，

都不在限制范围之内。

horky

引用第19楼jingmouren于2007-12-26 18:33发表的 :

我在8楼的回复已经说了，交换相领两个是不可能的

Bookish老师提供了一个很好的思路

我想也可以从逆序数来证明此题之不可行
每移动一次家具，逆序数或者不变，或者改变偶数。所以无论如何移动，初始位置与终止位置的逆序数的奇偶性是相同的
空位有6种可能，共有14种移动可能
AB
CDE         B向右移，逆序数不变     E向上移，逆序数+2

A B
CDE        A右移或B左移，逆序数不变   D上移，逆序数+2

AB
CDE  等剩余的空位可能出现的四种可能对应9种可能移动，但情形与以上两种类似

一般的，空位左移或右移不改变逆序数
空位上移或下移改变偶数个逆序数

但我开始确实看错物品了
这个题目是要从
A B
CDE
变到
A B
EDC也是不可能的因为初始逆序数为0 期望的最终逆序数为3

同理，期望最终为
C B
ADE 也不可能


.......

我真是受不了了。

jingmouren老大，你第一次把写字台错认成床还情有可愿，

这次又把沙发认成床。

我真的晕倒。

阶梯

拿5张标签，左右两边都要先后转，转的关键是要两物品出来后，做到上下依次进入，达到对换目的，但那样的搬运实在太累了。

944f4fe875fb39d

jingmouren兄能否证明，已知一个数列的逆序数为偶数或0，移动数列中的一个数字，移动中该数字的逆序情况变化偶数次，那么，移动后，这个数列的逆序数仍为偶数或0。

如果这点能证明，此题无解就得到证明了。（题目中，房间的主人只想对调床和冰箱。）

或者有其他方法证明此题无解。

jingmouren

引用第23楼bookish　于2007-12-26 20:04发表的 :
jingmouren兄能否证明，已知一个数列的逆序数为偶数或0，移动数列中的一个数字，移动中该数字的逆序情况部变化或变化偶数次，那么，移动后，这个数列的逆序数仍为偶数或0。

如果这点能证明，此题无解就得到证明了。（题目中，房间的主人只想对调床和冰箱。）

或者有其他方法证明此题无解。

何谓移动中该数字的逆序情况变化偶数次或者不变

即：移动前逆序数为奇且移动后逆序数为奇
或者移动前逆序数为偶且移动后逆序数为偶

所以
已知一个数列的逆序数为偶数或0，移动数列中的一个数字，移动中该数字的逆序情况部变化或变化偶数次，那么，移动后，这个数列的逆序数仍为偶数或0。

944f4fe875fb39d

我还不懂逆序数。查了一下，逆序数是一个数列中，数值大的数在数值小的数值前的个数之和。

已知一个数列的逆序数为偶数或0，移动数列中的一个数字偶数个位置，那么，移动后这个数列的逆序数仍为偶数或0。有没有证明？

944f4fe875fb39d

谢谢jingmouren兄的提示，让我学习了逆序数知识。

逆序数的定义

在一个排列中，当其中某两个元素的次序与标准顺序中这两个元素的次序不一致时，我们称这两个元素产生了一个逆序(an inverse－order)。一个排列中所有的逆序数的总数称为这个排列的逆序数(number of the inverse-orders)。

根据逆序数的定义，我们可以得到逆序数的计算方法如下：

设有n个自然数，b1, b2, ..., bn为这n个数的一个排列。则对每个bi, 如果比bi大且排在bi前面的元素个数为ti，就称bi在这个排列中的逆序数为ti，而t=t1+t2+...+tn就是这个排列的逆序数。

如果一个排列的逆序数为奇数，则称此排列为奇排列（odd permutation）；如果一个排列的逆序数为偶数，则称此排列为偶排列（even permutation）。

在一个排列中，将某两个元素对调位置而其余元素保持不变的操作称为对换。

在一个排列中，进行一次对换，排列改变奇偶性。

证：

先证对换两个相邻元素的情形。

设排列为a1 a2 ... an a b b1 b2 ... bn逆序数为t。对换a和b后，排列为a1 a2 ... an b a b1 b2 ... bn，其逆序数为t*。显然排列中除了a和b，其它元素的逆序数保持不变，只有a和b的逆序数有可能发生变化。当a<b时，a的逆序数增加1而b的逆序数不变；当a>b时，a的逆序数不变而b的逆序数减少1，总之，t*=t+1或者t*=t-1。因此，排列改变奇偶性。

其次，证明一般情况。

设排列为a1 a2 ... an a b1 b2 ... bm b c1 c2 ... ck, 对换a和b后，变为a1 a2 ... an b b1 b2 ... bm a c1 c2 ... ck。我们可以把它看成是先m次对换相邻元素a与bi(i=1,...,m)变成a1 a2 ... an b1 b2 ... bm a b c1 c2 ... ck，再对换a和b，然后作m次对换相邻元素bi与b(1=1,...,m)，变成a1 a2 ... an b b1 b2 ... bm a c1 c2 ... ck。因此，这种情况下，对换a和b，相当于作了2m+1次相邻元素的对换，故它改变排列的奇偶性。

由于标准顺序的排列的逆序数为0，所以，奇排列变成标准顺序的排列须经过奇数次对换；偶排列变成标准顺序的排列须经过偶数次对换。

设标准顺序为12345，奇排列21345变成标准顺序的排列须经过奇数次对换，本题的移动只能作偶数次对换，故奇排列21345不能变成标准顺序，所以此题无解。

证毕。

jingmouren

引用第25楼bookish　于2007-12-26 20:21发表的 :
我还不懂逆序数。查了一下，逆序数是一个数列中，数值大的数在数值小的数值前的个数之和。

已知一个数列的逆序数为偶数或0，移动数列中的一个数字偶数个位置，那么，移动后这个数列的逆序数仍为偶数或0。有没有证明？

AB
CDE         B向右移，逆序数不变     E向上移，逆序数+2

若E只是表示某个与ABCD都不同的数
则E向上移  （C,E)变成了(E,C)逆序数改变量为1
（D,E)变成了(E,D)逆序数改变量为1
其他数对的逆序数不改变
数列a1a2.....an的逆序数可以用数列的所有二元数对(ai,aj)(i<j)的逆序情况求和得到
所以E上移逆序数改变0或2或-2
这只是个思路 可以用于说明本题
不能说明一般地移动偶数个位置

一般地证明可能要用数学归纳法
但是移动数列中的一个数字偶数个位置 可以看成是偶数次相邻位置元素交换。每交换一次，逆序数增1或减1（其他数对的逆序情况不变）。偶数次交换后，逆序数改变为偶数。

磁铁

shuchuxs 楼主，您没有说是否其它家具还必须保持不变啊？如果是其它家具返回原样的话看来真没有解了。

horky

引用第28楼磁铁于2007-12-26 21:11发表的 :
shuchuxs 楼主，您没有说是否其它家具还必须保持不变啊？如果是其它家具返回原样的话看来真没有解了。

这还用说啊，当然没有这个要求了。
要有这么严格的、会直接影响到题目结果的要求，题目里早就写明了。

我觉得应该是保持不变，因为其他家俱并没有搬错。
今天晚上我好好摆一次，看到底是什么情况。

磁铁

上传个excel的可移动家具版，大家试试吧

其它家具不恢复原样条件下，已经有17步的，欢迎比这个少的

更欢迎其它家具恢复原地情况下的解决方法或者证明。

horky

其它家具不恢复原样条件下，已经有17步的，欢迎比这个少的



不可能有更少的。


更欢迎其它家具恢复原地情况下的解决方法或者证明。


这是不可能有答案的。



总之我的那个就是对的。

磁铁

32楼，对于无解进行证明也是很好的一种思考呀，考验你的时候到了！

944f4fe875fb39d

只考虑冰箱和大床的位置，不考虑其他家具的位置，最少需要17步，只有2个方案，其中1个是horky兄的方案。

如果要求中间上方的房间仍然空着，只有4个方案，最少需要18步。

如果对调冰箱和大床的位置，其他家具的位置不变，那已经证明是不可能的（我个人给予提供证明思路的jingmouren兄30财富奖金）。

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

昨天一夜没睡好，把五件家俱倒过来倒过去的，折腾了一宿，最后还是安排不好。其中有一次居然办到了——可能有错误——再试的时候还是不成，后来想，这事的确不好办，很多专家用计算机都没法办到的事，很可能就是题出错了。
今天找到那道题，找到答案http://www.dx.pte.sh.cn/xsly/xiuxian/tounao/shuxue/qwsx_001.htm，竟是17步，同样没考虑其它家俱。
对于我曾坚持的“其他不动，两件对调”这件不可能事件给大家引起的不快，表示道歉。

yibai

我晕 原来其他的可以变

多发点钱钱就原谅你了

磁铁

引用第36楼yibai于2007-12-27 11:13发表的 :
我晕 原来其他的可以变

多发点钱钱就原谅你了

请按bookish骑士的提示，继续探索，继续有奖！

killl

bookish的第一种解法：

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

killl

试试啊