求证：三阶任意一次90度转动改变簇奇偶性

pengw

我自已出，不等于是我自已来答，你愿意答就答，不愿意答就拉倒，不用在那里酸不溜蹴，我承认错解了你的定义，但我没有看见你证明了什么，更没有见到你发现了魔方什么新规律。希望以后有事就正面说事，不说跟事无关的人。我可以很负责任地说，证明这个问题只有一句话，且完全不用你的定义。

[ 本帖最后由 pengw 于 2008-9-10 21:51 编辑 ]

pengw

关于三元置换可以证明色向的问题，三元置换本身就可以用来改变色向，但不能解释色向和为零。同一个三元置换，色向可能有9种方式或4种方式。

[ 本帖最后由 pengw 于 2008-9-10 22:11 编辑 ]

pengw

<P>我试过多次，偶数个逆秩对对应任意次奇元置换，奇数个逆秩对对应奇数次偶元置换，没有发现例外，但这是举例，不是一般性证明。必须找出逆秩对与偶元环数目的奇偶性的一般性对应关系才算证明。</P>

[ 本帖最后由 pengw 于 2008-9-11 15:04 编辑 ]

pengw

感谢管理员恢复了被误删的贴子

Cielo

<P>

原帖由 <I>pengw</I> 于 2008-9-11 14:52 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=236475&amp;ptid=13343" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 我试过多次，偶数个逆秩对对应任意次奇元置换，奇数个逆秩对对应奇数次偶元置换，没有发现例外，但这是举例，不是一般性证明。必须找出逆秩对与偶元环数目的奇偶性的一般性对应关系才算证明。

</P>
<P>&nbsp;</P>
<P>前面有人说过，“奇（偶）元置换”可以分解为偶（奇）数个“对换”（也就是两个数之间的交换），</P>
<P>&nbsp;</P>
<P>很容易可以证明，任何一个“对换”会改变总的“逆序对”个数的奇偶性。这就提供了对应关系了。</P>

pengw

<P>说得有理，但作为证明，总得给出一个基本的一般性证明过程，要不然怎么向大家交待？任意二个数交换的结果，只少在逆序对的数量上不完全一致。</P>
<P>&nbsp;</P>
<P>其实大家早就明白偶元置换与偶元环数量的关系，缺的也是一个一目了然的一般性证明。</P>

[ 本帖最后由 pengw 于 2008-9-11 16:49 编辑 ]

pengw

<P>如何把有限几个举例推向一般性，这是一个很正式的话题，须要认真对待才能令人信服，相信105楼可以给大家一个完美的结局。</P>
<P>&nbsp;</P>
<P>我也有一种方法，与逆顺对无关，完全可以证明这个问题，且异常简单，但做为出题者，我希望不是由我来证明，我承诺一定给得出来。</P>

[ 本帖最后由 pengw 于 2008-9-11 16:59 编辑 ]

Cielo

<P>忍大师说的有理！</P>
<P>&nbsp;</P>
<P>我就把105楼补完整吧：</P>
<P>设第ｉ和ｊ（ｉ＜ｊ）位的两个数交换了，我们重新考察所有可能的下标对ｋｌ</P>
<P>&nbsp;</P>
<P>那么前ｉ-１和后ｎ-ｊ个数完全没变，而且交换前在它们前面（或后面）的数，交换之后仍在它们的前面（或后面）的。所以交换后，再考察的下标对ｋｌ（ｋ＜ｌ），如果ｋ≤ｉ-１或ｌ≥ｊ+１，那么之前是（或者不是）逆序对的话，交换之后仍然是（或者不是）逆序对。</P>
<P>&nbsp;</P>
<P>考虑第ｉ+１到第ｊ-１位，一共ｊ-ｉ-１个数，再考察的下标对ｋｌ（ｋ＜ｌ），如果ｉ+１≤ｋ＜ｌ≤ｊ-１，那么之前是（或者不是）逆序对的话，交换之后仍然是（或者不是）逆序对。</P>
<P>&nbsp;</P>
<P>这样，只有在下标对ｋｌ中恰含ｉ或者ｊ时，才与交换之前有差别。</P>
<P>&nbsp;</P>
<P>仍然考虑第ｉ+１到第ｊ-１位。第ｉ位原本在它们前面，但交换后到它们后面去了，所以ｊ-ｉ-１对改变了（即交换之前是／不是逆序对，交换之后不是／是逆序对）。同理，第ｊ位原本在它们后面，但交换后到它们前面去了，所以也是ｊ-ｉ-１对改变了。最后ｉ、ｊ位交换了，所以一共改变了２ｘ（ｊ-ｉ-１）+１次，是奇数次，</P>
<P>所以“对换”改变了逆序对个数的奇偶性，对应于排列的奇偶性。</P>

pengw

楼上证明得非常专业，还能不能更简单一点？

pengw

<P>设：A与B之间有T 个元素，则AB互换带来的逆序对改变是C=2T+1 </P>
<P>设变换前：</P>
<P>全体逆序对数是N </P>
<P>X是A与T个元素构成的逆序对数,0&lt;=X&lt;=T </P>
<P>Y是B与T个元素构成的逆序对数,0&lt;=Y&lt;=T </P>
<P>Z是A与B构成的逆序对数，Z值域{0，1} </P>
<P>D=X+Y+Z </P>
<P>变换后新增逆顺对数 P=(2T+1)-(X+Y+Z)=C-D </P>
<P>当前全体逆序对数E=N-D+C-D=N-2D+C </P>
<P>显然，如果N是奇数，E一定是偶数，反之则是奇数 </P>
<P>------------------------- </P>
<P>我这个证明看上去有点土得掉渣，希望大家不要嫌弃哈，还有更简单的反证法，以后再说。</P>

[ 本帖最后由 pengw 于 2008-9-11 20:47 编辑 ]