h******e
发帖数: 9616 | 1 【 以下文字转载自 NextGeneration 讨论区 】
发信人: ananpig (●○ 围棋数学一把抓的安安猪), 信区: NextGeneration
标 题: 围棋数学题……棋盘上一串棋子最多能有多少气？
发信站: BBS 未名空间站 (Tue Mar 3 15:54:07 2015, 美东)
刚刚设计了一道围棋数学题，用在教材中，评估学生掌握“串”和“气”的概念情况
串：通过横线和竖线紧密相连的所有棋子叫一“串”
气：和一串棋子通过横线和竖线紧密相连的空的交叉点（的数量）
考虑在 5x5 棋盘上，
１，一串棋子最多能有多少气？
２，达到这个状态的串所包含的棋子最少是多少？
把棋盘扩展到 6x6，似乎容易了很多……
再扩展到 7x7，又复杂起来了……，
8x8好像也不容易，
9x9似乎容易点
一定要摆出这个形状，而且有个探索的数学步骤……
我感觉里面有很深奥的数学，但是我还没仔细琢磨…… |
h******e
发帖数: 9616 | |
k***r
发帖数: 13724 | |
H********g
发帖数: 43926 | |
d****o
发帖数: 32610 | 5 贪吃蛇
【在 h******e 的大作中提到】
: 看着灰常学术啊。。。
|
H********g
发帖数: 43926 | 6 是的
【在 d****o 的大作中提到】
: 贪吃蛇
|
S***a
发帖数: 934 | 7 对于奇数n路棋盘，最少所用棋子数似乎是(n-1)^2/2，气数公式太麻烦还没归纳
这样5x5棋盘用8棋子14气 还有更多的摆法吗? |
a*****g
发帖数: 19398 | 8 我开始设计的时候也觉得很简单很容易
就想给个答案
结果是越做越发现有难度有趣味
你试一试就知道了……
【在 k***r 的大作中提到】
: 答案难道不是沿着棋盘最边缘的一串棋子么？
|
a*****g
发帖数: 19398 | 9 是滴
所以要发到学术版请教大家啊
【在 h******e 的大作中提到】
: 看着灰常学术啊。。。
|
R***a
发帖数: 41892 | 10 难道不是摆出一个贪吃蛇造型么？
【在 a*****g 的大作中提到】
: 我开始设计的时候也觉得很简单很容易
: 就想给个答案
: 结果是越做越发现有难度有趣味
: 你试一试就知道了……
|
|
|
k***r
发帖数: 13724 | 11 他们加了个棋盘大小几x几的限制，正宗围棋盘就是在边缘摆一圈完事儿，很小的可能
有变化。
【在 R***a 的大作中提到】
: 难道不是摆出一个贪吃蛇造型么？
|
a*****g
发帖数: 19398 | 12 贪吃蛇是串不能碰上，相互要避开，所以２路基本上就可以
气是串两边的点，简单说，如果要多气，要相互避开，需要３路
所以３的倍数比较容易，但是实际上还有些细微的地方要调整。
不是３的倍数，就麻烦了
【在 R***a 的大作中提到】
: 难道不是摆出一个贪吃蛇造型么？
|
R***a
发帖数: 41892 | 13 边缘摆一圈显然不如贪吃蛇螺旋到中心气多啊
【在 k***r 的大作中提到】
: 他们加了个棋盘大小几x几的限制，正宗围棋盘就是在边缘摆一圈完事儿，很小的可能
: 有变化。
|
a*****g
发帖数: 19398 | 14 这个不是限制，而是看看从简单的出发，能不能找出规律
要是能直接给出 19 路棋盘的答案数字（以及图案），那就厉害了
【在 k***r 的大作中提到】
: 他们加了个棋盘大小几x几的限制，正宗围棋盘就是在边缘摆一圈完事儿，很小的可能
: 有变化。
|
k***r
发帖数: 13724 | 15 螺旋要用子浪费了气数。
【在 R***a 的大作中提到】
: 边缘摆一圈显然不如贪吃蛇螺旋到中心气多啊
|
a*****g
发帖数: 19398 | 16 你这个倒是提示了我，
也许从中心做斐波那契数列（或者类似的），也许能构造出任何大小的棋盘的答案
可能
【在 R***a 的大作中提到】
: 边缘摆一圈显然不如贪吃蛇螺旋到中心气多啊
|
R***a
发帖数: 41892 | 17 一串棋子不算头尾，一个子就两个气，
19x19棋盘摆一圈，中间16x16那么大一块就浪费了。
牺牲几个棋子进入16x16区域肯定值得啊
【在 k***r 的大作中提到】
: 螺旋要用子浪费了气数。
|
a*****g
发帖数: 19398 | 18 对，中间不能浪费。
我摆过了一些小的棋盘的情况，目前 9x9 的是这个样的
（我也还不知道答案，也没有想好数学模型）
【在 R***a 的大作中提到】
: 一串棋子不算头尾，一个子就两个气，
: 19x19棋盘摆一圈，中间16x16那么大一块就浪费了。
: 牺牲几个棋子进入16x16区域肯定值得啊
|
K*****2
发帖数: 9308 | 19 中间那么大，肯定不能空着，大的棋盘上肯定得用某种办法绕道中间去，我猜某种贪吃
蛇螺旋就是最大解
【在 k***r 的大作中提到】
: 螺旋要用子浪费了气数。
|
a*****g
发帖数: 19398 | 20 我试验了 5x5的棋盘，摆出来的结果是最多 14气，棋子是9个
但是我不知道对不对，也没想好这里面的数学模型
【在 S***a 的大作中提到】
: 对于奇数n路棋盘，最少所用棋子数似乎是(n-1)^2/2，气数公式太麻烦还没归纳
: 这样5x5棋盘用8棋子14气 还有更多的摆法吗?
|
|
|
a*****g
发帖数: 19398 | 21 我觉得你这个可能有缺陷，因为棋盘的 5x5 总计25个交叉点
用了8个棋子，14气，那么还剩下 25-8-14 ＝ 3 个点
这3个点放在哪里？放中间，放角上？
如果放角上，似乎很不对称
【在 S***a 的大作中提到】
: 对于奇数n路棋盘，最少所用棋子数似乎是(n-1)^2/2，气数公式太麻烦还没归纳
: 这样5x5棋盘用8棋子14气 还有更多的摆法吗?
|
z*****n
发帖数: 7639 | 22 肯定不是。
【在 k***r 的大作中提到】
: 答案难道不是沿着棋盘最边缘的一串棋子么？
|
S***a
发帖数: 934 | 23 嗯，如图三个点都在角上。看起来确实不太对称，但对于5x5我还没看到更好的方法
【在 a*****g 的大作中提到】
: 我觉得你这个可能有缺陷，因为棋盘的 5x5 总计25个交叉点
: 用了8个棋子，14气，那么还剩下 25-8-14 ＝ 3 个点
: 这3个点放在哪里？放中间，放角上？
: 如果放角上，似乎很不对称
|
H********g
发帖数: 43926 | 24 3nx3n:
不靠顶的梳子形状似乎是最优的。用掉 3n^2 + n-2子(o)，共6n^2-n个气（.），2个点
完全浪费掉（*）。
===========6x6 n=2
不靠顶的梳子（=吃蛇）
12 O 22 . 2*
*....*
.OOOO.
.O..O.
.O..O.
.O..O.
.O..O.
靠顶的梳子
14 O 22. 0*
.OOOO.
.O..O.
.O..O.
.O..O.
.O..O.
.O..O.
=============9x9
不靠顶的梳子
28o 51. 2*
*.......*
.ooooooo.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
靠顶的梳子
31o 50 . 0*
.ooooooo.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
吞吃蛇
27o 50. 4*
*.......*
.ooooooo.
.o.....o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..oooo.
.o.*....* |
a*****g
发帖数: 19398 | 25 我摆的 5x5 是这样的
【在 S***a 的大作中提到】
: 嗯，如图三个点都在角上。看起来确实不太对称，但对于5x5我还没看到更好的方法
|
H********g
发帖数: 43926 | 26 （3n-1）x（3n-1）的情况，似乎就是对3nx3n做cropping，切掉梳子齿（损失2n）一边
和一侧（损失3n-1）。
【在 H********g 的大作中提到】
: 3nx3n:
: 不靠顶的梳子形状似乎是最优的。用掉 3n^2 + n-2子(o)，共6n^2-n个气（.），2个点
: 完全浪费掉（*）。
: ===========6x6 n=2
: 不靠顶的梳子（=吃蛇）
: 12 O 22 . 2*
: *....*
: .OOOO.
: .O..O.
: .O..O.
|
a*****g
发帖数: 19398 | 27 现在感觉模型可能是——
３倍数就摆不靠边的梳子
其他的，考虑从中心，或者是中心旁边，然后开始绕螺线
【在 S***a 的大作中提到】
: 嗯，如图三个点都在角上。看起来确实不太对称，但对于5x5我还没看到更好的方法
|
H********g
发帖数: 43926 | 28 (3n-2)x(3n-2)，切顶上和下边，然后中间取两列气切掉，损失(3n-2)+3(3n-3)
【在 H********g 的大作中提到】
: （3n-1）x（3n-1）的情况，似乎就是对3nx3n做cropping，切掉梳子齿（损失2n）一边
: 和一侧（损失3n-1）。
|
d****o
发帖数: 32610 | 29 他那个是理论最好情况了
【在 a*****g 的大作中提到】
: 我摆的 5x5 是这样的
|
H********g
发帖数: 43926 | 30 3nx3n 共6n^2-n个气 (9x9: 51)
（3n-1）x（3n-1） 共6n^2-6n+1个气 (8x8: 37)
（3n-2）x（3n-2） 共6n^2-13n+11个气 (7x7: 26) |
|
|
a*****g
发帖数: 19398 | 31 有趣。
一边
【在 H********g 的大作中提到】
: (3n-2)x(3n-2)，切顶上和下边，然后中间取两列气切掉，损失(3n-2)+3(3n-3)
|
d****o
发帖数: 32610 | 32 不对
5x5已经做出来14气了
【在 H********g 的大作中提到】
: 3nx3n 共6n^2-n个气 (9x9: 51)
: （3n-1）x（3n-1） 共6n^2-6n+1个气 (8x8: 37)
: （3n-2）x（3n-2） 共6n^2-13n+11个气 (7x7: 26)
|
H********g
发帖数: 43926 | 33 修正：（3n-1）x(3n-1)应该是损失2n和(3n-2).
【在 H********g 的大作中提到】
: （3n-1）x（3n-1）的情况，似乎就是对3nx3n做cropping，切掉梳子齿（损失2n）一边
: 和一侧（损失3n-1）。
|
H********g
发帖数: 43926 | 34 修正，(3n-2)x(3n-2)应该是横切两排梳子齿，竖切两列气
损失2(3n-n)+2(3n-3)=10n-6
11
【在 H********g 的大作中提到】
: (3n-2)x(3n-2)，切顶上和下边，然后中间取两列气切掉，损失(3n-2)+3(3n-3)
|
H********g
发帖数: 43926 | 35 修正
3nx3n 共6n^2-n个气 (9x9: 51)
（3n-1）x（3n-1） 共6n^2-6n+2个气 (8x8: 38)
（3n-2）x（3n-2） 共6n^2-11n+6个气 (7x7: 27)
【在 H********g 的大作中提到】
: 修正，(3n-2)x(3n-2)应该是横切两排梳子齿，竖切两列气
: 损失2(3n-n)+2(3n-3)=10n-6
:
: 11
|
H********g
发帖数: 43926 | 36 n=2的时候
6x6： 22
5x5: 14
4x4: 8
6x6
*....*
.OOOO.
.O..O.
.O..O.
.O..O.
.O..O.
5x5(有些特殊，可以省一个子)
*...*
.OOO.
.O.O.
.O.O.
.O..*
4x4 (有些特殊，可以省两个子)
*..*
.OO.
.OO.
*..*
【在 H********g 的大作中提到】
: 修正
: 3nx3n 共6n^2-n个气 (9x9: 51)
: （3n-1）x（3n-1） 共6n^2-6n+2个气 (8x8: 38)
: （3n-2）x（3n-2） 共6n^2-11n+6个气 (7x7: 27)
|
d****o
发帖数: 32610 | 37 还是有问题
3x3，可以做
.o.
.o.
.o.
六个气
【在 H********g 的大作中提到】
: 修正
: 3nx3n 共6n^2-n个气 (9x9: 51)
: （3n-1）x（3n-1） 共6n^2-6n+2个气 (8x8: 38)
: （3n-2）x（3n-2） 共6n^2-11n+6个气 (7x7: 27)
|
H********g
发帖数: 43926 | 38 n=<2的时候出现特殊情况。
n=2的时候最少子数公式失效。
n=1的时候最大气公式失效。
【在 d****o 的大作中提到】
: 还是有问题
: 3x3，可以做
: .o.
: .o.
: .o.
: 六个气
|
x******s
发帖数: 398 | 39 这个四角没有算成气, 确定最优解?
话说这个题目挺有意思的, 值得做一下.
【在 a*****g 的大作中提到】
: 对，中间不能浪费。
: 我摆过了一些小的棋盘的情况，目前 9x9 的是这个样的
: （我也还不知道答案，也没有想好数学模型）
|
d****o
发帖数: 32610 | 40 梳子应该是对的
固定子数n，
理论最大气数是2n＋2，
贴边一个子减一气，
一个拐角减一气，
一个分叉减两气（算两个拐角）
另外不是3的倍数的时候一间跳也减一个气
棋盘边长增大k，
梳子增加k/3个分叉，
消耗2k/3个气
螺旋贪吃蛇增加4k/3个拐角
消耗4k/3个气
——
不对
贪吃蛇也是增加2k/3的拐角
不好说
【在 H********g 的大作中提到】
: n=<2的时候出现特殊情况。
: n=2的时候最少子数公式失效。
: n=1的时候最大气公式失效。
|
|
|
H********g
发帖数: 43926 | 41 4 x4: 8
5 x5: 14
6 x6: 22
7 x7: 27
8 x8: 38
9 x9: 51
10x10: 58
11x11: 74
12x12: 92
13x13: 101
14x14: 122
15x15: 145
16x16: 156
17x17: 182
18x18: 210 |
H********g
发帖数: 43926 | 42 因为目标是最大化气，所以蛇头尾总是顶边的，所以假如不拐弯，不固定子数，一个大
蛇的最大气数是2n。
【在 d****o 的大作中提到】
: 梳子应该是对的
: 固定子数n，
: 理论最大气数是2n＋2，
: 贴边一个子减一气，
: 一个拐角减一气，
: 一个分叉减两气（算两个拐角）
: 另外不是3的倍数的时候一间跳也减一个气
: 棋盘边长增大k，
: 梳子增加k/3个分叉，
: 消耗2k/3个气
|
d****o
发帖数: 32610 | 43 也有贴边不赚的情况
比如5x5
【在 H********g 的大作中提到】
: 因为目标是最大化气，所以蛇头尾总是顶边的，所以假如不拐弯，不固定子数，一个大
: 蛇的最大气数是2n。
|
d****o
发帖数: 32610 | 44 我想错了 贪吃蛇拐角增加速度是2k/3
消耗气的速度一样
不一定梳子最优
【在 H********g 的大作中提到】
: 因为目标是最大化气，所以蛇头尾总是顶边的，所以假如不拐弯，不固定子数，一个大
: 蛇的最大气数是2n。
|
H********g
发帖数: 43926 | 45 吃蛇的问题是每次拐弯的时候会多一个空格，如果要用临近的子来占领这个空格，又会
消耗气。梳子的好处是只用在顶上两个角损失两个空格。
12x12吃蛇 91气 48子 5空格 【修改过】
*.........o.
.ooooooo..o.
.o.....o..o.
.o..o..o..o. 【修改过，现在对了】
.o..o..o..o.
.o..o..o..o.
.o..o..o..o.
.o..oooo..o.
.o.*....*.o.
.o........o.
.oooooooooo.
*..........*
【在 d****o 的大作中提到】
: 我想错了 贪吃蛇拐角增加速度是2k/3
: 消耗气的速度一样
: 不一定梳子最优
|
H********g
发帖数: 43926 | 46 跟梳子比气数相同，但是吃蛇省了3个子，的确是最优。【错误，吃蛇91气，梳子92气】
梳子 92气 50子 2空
【在 H********g 的大作中提到】
: 吃蛇的问题是每次拐弯的时候会多一个空格，如果要用临近的子来占领这个空格，又会
: 消耗气。梳子的好处是只用在顶上两个角损失两个空格。
: 12x12吃蛇 91气 48子 5空格 【修改过】
: *.........o.
: .ooooooo..o.
: .o.....o..o.
: .o..o..o..o. 【修改过，现在对了】
: .o..o..o..o.
: .o..o..o..o.
: .o..o..o..o.
|
H********g
发帖数: 43926 | 47 前面搞错了，12x12吃蛇是91气，48子，5空，梳子是92气 50子 2空，还是梳子厉害。
11x11 吃蛇是71气，梳子74气。
【在 H********g 的大作中提到】
: 跟梳子比气数相同，但是吃蛇省了3个子，的确是最优。【错误，吃蛇91气，梳子92气】
: 梳子 92气 50子 2空
|
H********g
发帖数: 43926 | 48 所以目前我的结论还是跟35楼和41楼相同 （适用除了1x1 2x2 3x3的棋盘）：
最大气数，对于n>1:
3nx3n 共6n^2-n个气
（3n-1）x（3n-1） 共6n^2-6n+2个气
（3n-2）x（3n-2） 共6n^2-11n+6个气
最少子数：
当n>2的时候，棋盘上总是有2个点是空的（既不是子，也不是气）。
n=2的时候 图形在36楼。 |
w**********r
发帖数: 986 | 49 结论比你的好一点儿
问的是一串子有多少起气，并没有要求用最少的子，那当一个棋盘上还有没用到的点（
不是子，不是气）的时候，总可以增加一个子，总气数不亏（加一子损失一气，至少把
一个没用的点转变成气）。
于是题目就简化成一个棋盘上或是连起来的子，或是气，最多能有多少气。
比了一下，梳子气多一点
3k*3k, 子 2*3k+(k-2)*(3k-1)+(k-1)*2=3k^2+k，气9k^2- (3k^2+k)=6k^2-k
(3k-1)*(3k-1), 子 (3k-1)+(k-1)*(3k-2)+(k-1)*2=3k^2-1，气(3k-1)^2- (3k^2-1)=
6k^2-6k+2
(3k-2)*(3k-2), 子 (3k-2)+(k-2)*(3k-3)+(k-2)*2+1+3k-4=3k^2-k-3，气(3k-2)^2- (
3k^2-k-3)=6k^2-11k+7
【在 H********g 的大作中提到】
: 所以目前我的结论还是跟35楼和41楼相同 （适用除了1x1 2x2 3x3的棋盘）：
: 最大气数，对于n>1:
: 3nx3n 共6n^2-n个气
: （3n-1）x（3n-1） 共6n^2-6n+2个气
: （3n-2）x（3n-2） 共6n^2-11n+6个气
: 最少子数：
: 当n>2的时候，棋盘上总是有2个点是空的（既不是子，也不是气）。
: n=2的时候 图形在36楼。
|
H********g
发帖数: 43926 | 50 哦，我（3n-2）x（3n-2）多用了子。应该是切掉左边两竖条留下的气最多，而且省很
多子：
9x9
*.......*
.ooooooo.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
.o..o..o.
7x7
......*
oooooo.
..o..o.
*.o..o.
*.o..o.
*.o..o.
*.o..o.
(
【在 w**********r 的大作中提到】
: 结论比你的好一点儿
: 问的是一串子有多少起气，并没有要求用最少的子，那当一个棋盘上还有没用到的点（
: 不是子，不是气）的时候，总可以增加一个子，总气数不亏（加一子损失一气，至少把
: 一个没用的点转变成气）。
: 于是题目就简化成一个棋盘上或是连起来的子，或是气，最多能有多少气。
: 比了一下，梳子气多一点
: 3k*3k, 子 2*3k+(k-2)*(3k-1)+(k-1)*2=3k^2+k，气9k^2- (3k^2+k)=6k^2-k
: (3k-1)*(3k-1), 子 (3k-1)+(k-1)*(3k-2)+(k-1)*2=3k^2-1，气(3k-1)^2- (3k^2-1)=
: 6k^2-6k+2
: (3k-2)*(3k-2), 子 (3k-2)+(k-2)*(3k-3)+(k-2)*2+1+3k-4=3k^2-k-3，气(3k-2)^2- (
|
|
|
H********g
发帖数: 43926 | 51 n>2的时候（3n-2）x（3n-2）应该是右上角开始的二叉树最优。
7x7 ： 29气
......*
oooooo.
..o..o.
..o..o.
ooo..o.
..o..o.
*.o..o.
10x10 61气
.........*
ooooooooo.
.....o..o.
.....o..o.
oooooo..o.
..o..o..o.
..o..o..o.
ooo..o..o.
..o..o..o.
*.o..o..o.
【在 H********g 的大作中提到】
: 哦，我（3n-2）x（3n-2）多用了子。应该是切掉左边两竖条留下的气最多，而且省很
: 多子：
: 9x9
: *.......*
: .ooooooo.
: .o..o..o.
: .o..o..o.
: .o..o..o.
: .o..o..o.
: .o..o..o.
|
H********g
发帖数: 43926 | 52 二叉树实际是梳子在左边加了一排小齿
用子3n^2-2n-3
气 6n^2-10n+5
空 2
【在 H********g 的大作中提到】
: n>2的时候（3n-2）x（3n-2）应该是右上角开始的二叉树最优。
: 7x7 ： 29气
: ......*
: oooooo.
: ..o..o.
: ..o..o.
: ooo..o.
: ..o..o.
: *.o..o.
: 10x10 61气
|
H********g
发帖数: 43926 | 53
【在 H********g 的大作中提到】
: 二叉树实际是梳子在左边加了一排小齿
: 用子3n^2-2n-3
: 气 6n^2-10n+5
: 空 2
|
g*****o
发帖数: 5955 | |
w**********r
发帖数: 986 | 55 有道理
【在 H********g 的大作中提到】
: 哦，我（3n-2）x（3n-2）多用了子。应该是切掉左边两竖条留下的气最多，而且省很
: 多子：
: 9x9
: *.......*
: .ooooooo.
: .o..o..o.
: .o..o..o.
: .o..o..o.
: .o..o..o.
: .o..o..o.
|
w**********r
发帖数: 986 | 56 发现螺旋转进去是一样的，如果想少用棋子可能还好一点，比如10×10，可以省4个点
【在 H********g 的大作中提到】
|
H********g
发帖数: 43926 | 57 有道理，这是目前10x10最省子的办法。102里内部两个拐弯处的突起也可以去掉，多两
个空，省两个子，气不变。33子61气6空。
【在 w**********r 的大作中提到】
: 发现螺旋转进去是一样的，如果想少用棋子可能还好一点，比如10×10，可以省4个点
|
