数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【数学研究】 › 难题征解 › 一个选数游戏
返回列表 发新帖
查看: 269|回复: 9

[讨论] 一个选数游戏

[复制链接]
好地方
发表于 2024-5-12 13:00:49 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
不知这里有没有发过？
两人轮流从给定的n个正整数中选数，要求是不能选已选过的数的因子，谁首先无数可选就算输。
容易证明，如果这些数中有1，则先手有必胜策略。
但如果没有1，好像就有难度了。比如对于从2到n的连续整数，有没有什么好的算法能判定胜负？已有的算法确定到多大的n了？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

aimisiyou
发表于 2024-5-12 14:26:17 | 显示全部楼层
从小往大选？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

好地方
 楼主| 发表于 前天 18:55 | 显示全部楼层
想了几天，没想出什么好的解法，只能暴力搜索。写了个穷举的python程序来判断一个局面是胜局还是败局。对于从2到n的连续整数的初始局面，目前用我的笔记本验证到了n=39。结果是n=3，7，28，34，35时为败局，其余都是胜局。再大的n就困难了，计算量指数增长。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

KeyTo9_Fans
发表于 昨天 10:54 | 显示全部楼层
你的计算量可能是O(2^n)，我优化到了O(2^(n/2))，算到了65，没有新发现，后面全是赢：
  1. 'n 胜负 尼姆值
  2. 02  win  1
  3. 03 lose  0
  4. 04  win  3
  5. 05  win  2
  6. 06  win  1
  7. 07 lose  0
  8. 08  win  1
  9. 09  win  1
  10. 10  win  2
  11. 11  win  3
  12. 12  win  3
  13. 13  win  2
  14. 14  win  1
  15. 15  win  2
  16. 16  win  8
  17. 17  win  9
  18. 18  win  2
  19. 19  win  3
  20. 20  win  5
  21. 21  win  7
  22. 22  win  4
  23. 23  win  5
  24. 24  win  3
  25. 25  win  2
  26. 26  win  1
  27. 27  win  6
  28. 28 lose  0
  29. 29  win  1
  30. 30  win  8
  31. 31  win  9
  32. 32  win 10
  33. 33  win  3
  34. 34 lose  0
  35. 35 lose  0
  36. 36  win 13
  37. 37  win 12
  38. 38  win  9
  39. 39  win  9
  40. 40  win 13
  41. 41  win 12
  42. 42  win  8
  43. 43  win  9
  44. 44  win  7
  45. 45  win 16
  46. 46  win  9
  47. 47  win  8
  48. 48  win 15
  49. 49  win 12
  50. 50  win  9
  51. 51  win  9
  52. 52  win 11
  53. 53  win 10
  54. 54  win 13
  55. 55  win  2
  56. 56  win 19
  57. 57  win 19
  58. 58  win 17
  59. 59  win 16
  60. 60  win 21
  61. 61  win 20
  62. 62  win 16
  63. 63  win  1
  64. 64  win 12
  65. 65  win  1

  67. --------------------------------
  68. Process exited after 11.52 seconds with return value
  69. 请按任意键继续. . .
复制代码

我感觉这个优化没啥用，计算量还是指数级增长的
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 1 反对 0

使用道具 举报

mathe
发表于 昨天 11:59 来自手机 | 显示全部楼层
推荐用nauty库可以将每个图标准化
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

好地方
 楼主| 发表于 昨天 12:46 | 显示全部楼层
KeyTo9_Fans 发表于 2024-5-28 10:54
你的计算量可能是O(2^n)，我优化到了O(2^(n/2))，算到了65，没有新发现，后面全是赢：

我感觉这个优化没啥 ...

厉害！敢问您都做了哪些优化？
另一个问题是，为啥败局数量这么少？有没有可能败局数量是有限的？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

KeyTo9_Fans
发表于 昨天 13:54 | 显示全部楼层
当连通块个数为1时，我计算连通块的尼姆数

如果尼姆数为0，表明这是先手必败局面，如果尼姆数非0，表明这是先手必胜局面，胜法就是取走一个数字，使得剩下局面的尼姆数为0

当连通块个数大于1时，我分别计算每个连通块的尼姆数，然后求这些数值的异或和

如果异或和为0，表明这是先手必败局面，不论我方怎么取，都会使得异或和非0，对方每次走到异或和为0的局面即可获胜

我开了一个从 [1,2,3,……,2^64] 到 尼姆数 的映射表，每次遇到一个新局面，先查询这个局面是否在表里

如果在，直接从表中读出这个局面的 尼姆数，如果不在，则递归计算这个局面的尼姆数，然后存到映射表里

我使用的整数变量只有64个二进制位，这就是我为什么只计算到65的原因

再多一个数，局面数就超过64个二进制位了，需要改用128个二进制位的整数变量，才能继续算

点评

KeyTo9_Fans
根据数值拟合的结果，目前的空间复杂度大约是O(1.174^n)  发表于 昨天 22:36
mathe
空间复杂度大概有多大？O(2^(n/2)),如果这样将比特数放大也很难扩张下去了。 可以试一试将同构的图归并  发表于 昨天 15:40
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

KeyTo9_Fans
发表于 昨天 22:29 | 显示全部楼层
改用128比特的整数来存储局面，继续计算，就卡在时间和空间的消耗上了：计算了20个小时，还差13个比特没用完

计算结果如下表所示：
  1. n        胜负        尼姆值        内存消耗(KB)
  2. 2        win        1        0.1
  3. 3        lose        0        0.2
  4. 4        win        3        0.4
  5. 5        win        2        0.5
  6. 6        win        1        0.9
  7. 7        lose        0        1
  8. 8        win        1        1.4
  9. 9        win        1        1.7
  10. 10        win        2        2.3
  11. 11        win        3        2.4
  12. 12        win        3        3.4
  13. 13        win        2        3.5
  14. 14        win        1        4.5
  15. 15        win        2        5.7
  16. 16        win        8        7.1
  17. 17        win        9        7.2
  18. 18        win        2        9.4
  19. 19        win        3        9.5
  20. 20        win        5        12.3
  21. 21        win        7        14.3
  22. 22        win        4        16.9
  23. 23        win        5        17
  24. 24        win        3        22.5
  25. 25        win        2        24.8
  26. 26        win        1        29.8
  27. 27        win        6        35.1
  28. 28        lose        0        44.2
  29. 29        win        1        44.3
  30. 30        win        8        59.2
  31. 31        win        9        59.3
  32. 32        win        10        72.8
  33. 33        win        3        81.2
  34. 34        lose        0        94.2
  35. 35        lose        0        108.8
  36. 36        win        13        135.7
  37. 37        win        12        135.8
  38. 38        win        9        161.6
  39. 39        win        9        186.2
  40. 40        win        13        232.2
  41. 41        win        12        232.3
  42. 42        win        8        301.1
  43. 43        win        9        301.2
  44. 44        win        7        375.7
  45. 45        win        16        455.7
  46. 46        win        9        526.3
  47. 47        win        8        526.4
  48. 48        win        15        666.5
  49. 49        win        12        709.3
  50. 50        win        9        893.5
  51. 51        win        9        1006.5
  52. 52        win        11        1290.6
  53. 53        win        10        1290.7
  54. 54        win        13        1709.7
  55. 55        win        2        1932.2
  56. 56        win        19        2390
  57. 57        win        19        2595
  58. 58        win        17        2921.6
  59. 59        win        16        2921.7
  60. 60        win        21        3676.4
  61. 61        win        20        3676.5
  62. 62        win        16        4329.5
  63. 63        win        1        5199.5
  64. 64        win        12        6249.9
  65. 65        win        1        6852.4
  66. 66        lose        0        8503.8
  67. 67        win        1        8503.9
  68. 68        win        21        10531.9
  69. 69        win        23        11410.5
  70. 70        win        11        15136.5
  71. 71        win        10        15136.6
  72. 72        win        2        19119.1
  73. 73        win        3        19119.2
  74. 74        lose        0        21973.8
  75. 75        win        19        26582.6
  76. 76        win        1        35078.5
  77. 77        win        25        38759.4
  78. 78        win        10        52828
  79. 79        win        11        52828.1
  80. 80        win        4        67955.6
  81. 81        win        20        78118.2
  82. 82        win        24        86476.8
  83. 83        win        25        86476.9
  84. 84        lose        0        108104.1
  85. 85        win        7        117381.9
  86. 86        win        4        134098.9
  87. 87        win        4        145333.1
  88. 88        win        10        176436.2
  89. 89        win        11        176436.3
  90. 90        win        31        217252.5
  91. 91        win        2        233998.8
  92. 92        win        18        292007.3
  93. 93        win        24        309056.7
  94. 94        win        28        351706.5
  95. 95        win        26        392502.9
  96. 96        win        9        484447.6
  97. 97        win        8        484447.7
  98. 98        win        3        608204.8
  99. 99        win        28        716643.7
  100. 100        win        4        891533.9
  101. 101        win        5        891534
  102. 102        win        5        1163701.9
  103. 103        win        4        1163702
  104. 104        win        13        1451144.5
  105. 105        win        1        1729338.2
  106. 106        win        2        1954464.8
  107. 107        win        3        1954464.9
  108. 108        win        25        2423816.9
  109. 109        win        24        2423817
  110. 110        win        33        3100514.5
  111. 111        win        27        3335844.3
  112. 112        win        7        4090798.4
  113. 113        win        6        4090798.5
  114. 114        win        6        5433328.4
  115. 115        win        9        5899338.8
  116. 116        lose        0
复制代码

最新发现：n=66、74、84、116为败局

这个数列【3 7 28 34 35 66 74 84 116】目前还没有被OEIS收录，很可能是楼主首创的
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-5-29 18:06 , Processed in 0.058659 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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