棒取りゲーム
小中学生の頃
||| ||||| |||||||
のように並んだ縦棒を取っていき、最後に取った人が負けと言うゲームが流行っていた。
続けて横に並んでいる棒は何本でも取れるが、複数の段の棒を同時に取ったり、既に取られた棒をまたいで取ったりはできない。(google:棒取りゲーム で検索すると分かりやすい説明が読めるだろう。)
棒が 3,5,7 本でやる事が多かったのだけど、この場合先手必勝と後手必勝のどちらだろう。
(3,5,6) 本は後手必勝? だとしたら (3,5,7) 本は先手必勝になるんだが。
追記:手順を graphviz の dot 形式で書いてみる。
終盤カタマリ(リンク先ネタバレ注意)が 1 個になった時以外、N山崩しゲームの必勝手と同じっぽい。
はてなブックマークで smoking186 さんに 石とりゲームの数理 POD版 (数学ライブラリー 教養篇) という本がある事を教えて頂きました。ありがとうございます。
数字は例えば 224 だったら、2 本並んだ棒が 2 組、4 本並んだ棒が 1 組という状態を表している。
先手はその状況で必勝となる手、後手はその状況で可能な全ての手をリストしたつもり。
digraph botori {
graph [rankdir=LR];
subgraph lose{
node [shape="box", style="filled", fillcolor="green"];
1; 111; 11111; 11123; 1122; 1133; 1144; 1155; 123; 145; 22; 2222; 2233; 246; 33; 356; 44; 55;
}
/* 先手 */
edge [color="blue"];
357 -> 356;
1156 -> 1155;
256 -> 246;
346 -> 246;
1244 -> 1144;
1145 -> 145;
1345 -> 145;
146 -> 145;
156 -> 145;
245 -> 145;
345 -> 145;
2234 -> 2233;
2235 -> 2233;
2236 -> 2233;
2335 -> 2233;
155 -> 55;
355 -> 55;
56 -> 55;
11124 -> 11123;
11125 -> 11123;
11135 -> 11123;
1134 -> 1133;
1135 -> 1133;
1136 -> 1133;
1233 -> 1133; // 123 も可
1335 -> 1133;
1336 -> 1133;
2223 -> 2222;
2224 -> 2222;
144 -> 44;
244 -> 44;
45 -> 44;
46 -> 44;
11122 -> 1122;
11223 -> 1122;
11225 -> 1122;
1124 -> 1122;
1125 -> 1122;
1126 -> 1122;
1222 -> 1122;
1224 -> 1122;
1226 -> 1122;
1123 -> 123; // 1122 でも可
1223 -> 123; // 1122 でも可
1234 -> 123;
1235 -> 123;
1236 -> 123;
124 -> 123;
125 -> 123;
126 -> 123;
134 -> 123;
135 -> 123;
136 -> 123;
234 -> 123;
235 -> 123;
236 -> 123;
133 -> 33;
233 -> 33;
335 -> 33;
336 -> 33;
35 -> 33;
36 -> 33;
34 -> 33;
111112 -> 11111;
11112 -> 11111;
11113 -> 11111;
11114 -> 11111;
11115 -> 11111;
122 -> 22;
222 -> 22;
223 -> 22;
224 -> 22;
225 -> 22;
226 -> 22;
23 -> 22;
24 -> 22;
25 -> 22;
26 -> 22;
1111 -> 111;
1112 -> 111;
1113 -> 111;
1114 -> 111;
1115 -> 111;
112 -> 111;
113 -> 111;
114 -> 111;
115 -> 111;
11 -> 1;
12 -> 1;
13 -> 1;
14 -> 1;
15 -> 1;
2 -> 1;
3 -> 1;
4 -> 1;
5 -> 1;
/* 後手 */
edge [color="red"];
356 -> 1135;
356 -> 1136;
356 -> 1156;
356 -> 1235;
356 -> 1236;
356 -> 1335;
356 -> 1336;
356 -> 1345;
356 -> 135;
356 -> 136;
356 -> 156;
356 -> 2235;
356 -> 2236;
356 -> 2335;
356 -> 235;
356 -> 236;
356 -> 256;
356 -> 335;
356 -> 336;
356 -> 345;
356 -> 346;
356 -> 35;
356 -> 355;
356 -> 36;
356 -> 56;
1155 -> 11115;
1155 -> 11125;
1155 -> 11135;
1155 -> 1115;
1155 -> 11225;
1155 -> 1125;
1155 -> 1135;
1155 -> 1145;
1155 -> 115;
1155 -> 155;
246 -> 1124;
246 -> 1126;
246 -> 1224;
246 -> 1226;
246 -> 1234;
246 -> 1244;
246 -> 124;
246 -> 126;
246 -> 146;
246 -> 2224;
246 -> 2234;
246 -> 224;
246 -> 226;
246 -> 234;
246 -> 236;
246 -> 24;
246 -> 244;
246 -> 245;
246 -> 26;
246 -> 46;
1144 -> 11114;
1144 -> 11124;
1144 -> 1114;
1144 -> 1124;
1144 -> 1134;
1144 -> 114;
1144 -> 144;
145 -> 1114;
145 -> 1115;
145 -> 1124;
145 -> 1125;
145 -> 1134;
145 -> 114;
145 -> 115;
145 -> 1224;
145 -> 124;
145 -> 125;
145 -> 134;
145 -> 135;
145 -> 14;
145 -> 144;
145 -> 15;
145 -> 45;
2233 -> 11223;
2233 -> 1223;
2233 -> 1233;
2233 -> 2223;
2233 -> 223;
2233 -> 233;
55 -> 115;
55 -> 125;
55 -> 135;
55 -> 15;
55 -> 225;
55 -> 25;
55 -> 35;
55 -> 45;
55 -> 5;
11123 -> 111112;
11123 -> 11112;
11123 -> 11113;
11123 -> 1112;
11123 -> 11122;
11123 -> 1113;
11123 -> 1123;
1133 -> 11113;
1133 -> 1113;
1133 -> 1123;
1133 -> 113;
1133 -> 133;
2222 -> 1222;
2222 -> 222;
44 -> 114;
44 -> 124;
44 -> 14;
44 -> 24;
44 -> 34;
44 -> 4;
1122 -> 1112;
1122 -> 112;
1122 -> 122;
123 -> 1112;
123 -> 112;
123 -> 113;
123 -> 12;
123 -> 122;
123 -> 13;
123 -> 23;
33 -> 113;
33 -> 13;
33 -> 23;
33 -> 3;
11111 -> 1111;
22 -> 12;
22 -> 2;
111 -> 11;
1 -> 0;
}
dot で画像にしたものが 
にあります。
