数学研发论坛

 找回密码
 欢迎注册
查看: 489|回复: 15

[悬赏] 棋子排列问题

[复制链接]
发表于 2019-6-26 08:24:21 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
5年级数学。要求给出所有排列的图示。程序语言不限制。

5

5
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-26 13:20:13 | 显示全部楼层
9=2+2+2+3是唯一的四质数分解方案
我们记全部合适的放法之集为 A.
A 可分为两个子集:A1={3子行与3子列交于空者},A2={3子行与3子列交于子者}。
一个合适的放法经过行变换和列变换后还是一个合适的放法。
行变换和列变换各有4!=24个,所以行、列变换群的阶为242=576。
先找出 A 在行、列变换下的商集(商集即变换下的各等价类之集,一个等价类可以用该类中的任一元素代表)。
A1 显然只有1个等价类,以下是它的一个代表。A1中的任一元素(放法)都可变换成该代表.
A2 有2个等价类,我们记为 A21、A22,以下是它们的代表.
A21
A22
剩下的事情就是计算每个等价类的阶,即上述各代表在 576 个行列变换下能生成多少个不重合的放法。


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-26 13:57:46 | 显示全部楼层
黑子为 A1 v.s. A2 的分类特征,显然每个分类特征都有16个不同的衍生特征(包括代表自身)。
A1  的每个衍生特征再放3个白子,显然是 3! 种放法。故|A1|=16×3!=96
A21的每个衍生特征再放4个白子,共有4个不重合放法。故|A21|=16×4=64
A22的每个衍生特征再放4个白子,唯有1个不重合放法。故|A22|=16, |A2|=|A21|+|A22|=80。
|A|=|A1|+|A2|=176。

176个图都摆出来,有点多。把3个代表再放白子的所有图摆出来,共11个图,还可以接受。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-6-26 14:05:30 | 显示全部楼层
816个
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 2019-6-26 14:08:04 | 显示全部楼层
存在第816组解。
第一行:1,1,1,0

第二行:1,1,0,0

第三行:1,0,0,1

第四行:0,0,1,1

4*4正方形方格放9枚棋子,每行每列的棋子个数均为质数,总共存在816组方法。
程序运行时间 55.195427656173706 秒。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-26 14:55:44 | 显示全部楼层
hujunhua 发表于 2019-6-26 13:57
黑子为 A1 v.s. A2 的分类特征,显然每个分类特征都有16个不同的衍生特征(包括代表自身)。
...

@markfang2050
哦,这里有错误。
这个断言只对 A1 成立。
A2 的分类特征应该有9×16个不同的衍生特征(包括代表自身)。
A2 的特征具有以下标记格:1、黑子行和黑子列之公共黑子,记为A。2、空行和空列之公共空格,记为B。
B有16格可选,对于确定的B,A有9格可选。故有9×16个不同的衍生特征。

|A|=96+80×9=816,这就更不可能一个个画出来了。

点评

@markfang2050 来自3#  发表于 2019-6-26 20:51
80×9中的80咋来的?  发表于 2019-6-26 16:54
小学5年级咋做?  发表于 2019-6-26 15:21
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-26 18:03:32 | 显示全部楼层
结果确实是816
  1. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
  2.      b c d + a c d )^4, a^3 b^2 c^2 d^2] +
  3. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
  4.      b c d + a c d )^4, a^2 b^3 c^2 d^2] +
  5. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
  6.      b c d + a c d )^4, a^2 b^2 c^3 d^2] +
  7. Coefficient[(a b + b c + c d + a c + b d + a d + a b c + a b d +
  8.      b c d + a c d )^4, a^2 b^2 c^2 d^3]
复制代码
耗时几乎为零。

点评

耗时是打印结果造成的,  发表于 2019-6-26 18:49
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-26 18:49:17 来自手机 | 显示全部楼层
hujunhua的方案可以通过数不动点的数目达到。
我们把行、列变换群记为G,前面已指出|G|=4!×4!. 全体放法之集如2楼仍记为A。
所谓不动点,即对某个 a∈A, 满足g∈G, g(a)=a的变换g.
比如 2# 中 A1 的那个代表元,
使之看起来保持不变的变换,显然行1和列1不能动,行2,3,4和列2,3,4必须保持同步交换(转置对称),故有3!=6个不动点.
易证,对任意 a'∈A1, 满足h(a')=a'的不动点 h∈G 也是3!=6个。
因为唯一存在 g'∈G, 使得 a'=g'(a). 故 h(a')=a'←→hg'(a)=g'(a) ←→g'h(a)=g'(a)←→h(a)=a
                                                                                         (G 是交换群)
即 A1中任意元的不动点都与代表元的相同,所以|A1|=|G|/3!=96种。

A21的那个代表元的不动点显然只有一个,即 g 的单位元。
A22的那个代表元的不动点,显然行1,4、列1,4不能动,只能行2,3、列2,3互换,故有4个。
所以|A|=|G|(1/6+1+1/4)=816.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-27 11:46:43 | 显示全部楼层
markfang2050  耗时是打印结果造成的
用MMA会快很多
  1. p = Select[
  2.    SparseArray[#,
  3.       4] & /@ (Table[{i1, i2, i3, i4} // Flatten, {i1,
  4.         Map[{1, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}, {i2,
  5.         Map[{2, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}, {i3,
  6.         Map[{3, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}, {i4,
  7.         Map[{4, #} -> 1 &, Subsets[Range[4], {2, 3}], {2}]}] //
  8.       Flatten[#, 3] &),
  9.    SameQ[Total[#] // Sort, {2, 2, 2, 3}] &&
  10.      SameQ[Total[#, {2}] // Sort, {2, 2, 2, 3}] &];
  11. % // Length
  12. MatrixForm /@ p
复制代码
全部结果打印出来也不到1秒。
也可以在8秒内画出所有棋盘结果
  1. MatrixPlot[#, ColorFunction -> "Monochrome", ImageSize -> Tiny,
  2.    Mesh -> All, Frame -> None, FrameTicks -> None] & /@ p // AbsoluteTiming
复制代码

点评

@chyanog,十分感谢,原来Tuple可以用于规则的组合。  发表于 2019-7-1 13:49
SparseArray[Flatten[#],4]&/@Tuples[Table[Map[{i,#}->1&,Subsets[Range[4],{2,3}],{2}],{i,4}]] 稍微简化一下Select的第一个参数  发表于 2019-6-28 18:09
这个效率高!  发表于 2019-6-27 12:36
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-9-15 13:29 , Processed in 0.068904 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表