IPSJ SIG Technical Report Vol.2016-GI-35 No /3/8 Corner the Queen problem 1,a) 2,b) 1,c) 1,d) 1,e) Queen 2 Queen 1 Corner the Queen problem Wyth

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2016-GI-35 No /3/8 Corner the Queen problem 1,a) 2,b) 1,c) 1,d) 1,e) Queen 2 Queen 1 Corner the Queen problem Wyth"

ゆきみのしま
4 years ago
Views:

1 Corner the Queen problem 1,a) 2,b) 1,c) 1,d) 1,e) Queen 2 Queen 1 Corner the Queen problem Wythoff s game Queen ( ) ( ) Grundy Grundy Grundy Wythoff Corner the Queen Grundy (i) N-position (ii) P -position Grundy move mex 1.2. p move(p) 1.3. (i) mex S 1 Kwansei Gakuin High School 2 EM Software a) runners@kwansei.ac.jp b) masanori.dev@gmail.com c) 0731inoue@gmail.com d) math271k@gmail.com e) helpcut.1092@gmail.com (ii) Grundy 0 Grundy Grundy Grundy G G(p) =mex{g(h) :h move(p)} 1.1. mex mex{0, 1, 2, 3} =4, mex{1, 1, 2, 3} =0, mex{0, 2, 3, 5} =1, mex{0, 0, 0, 1} = G Grundy h P-position G(h) =0 [2] 2. Corner the Queen Problem 2.1. Queen Queen 2 Queen 1 Queen 2 2 Queen Wythoff ( [2] ) Queen move(x, y) (1) 1

2 1 2 Queen 5 (1, 1) 6 (2, 0) move(x, y) ={(u, y) :u<x} {(x, v) :v<y} {(x t, y t) :0<t min(x, y)} (1) Queen Grundy (0, 0) Grundy 0 ( 3) Grundy Grundy Grundy Grundy 7 (2, 1) 8 Queen Grundy 3 (0, 0) Grundy 4 (0, 1) 4 ( (0, 1)) Grundy Queen 4 (0, 1) (0, 0) (0, 0) Grundy 0 (0, 1) Grundy Grundy {0} 1 (1, 0) Grundy 1 (1, 1) Grundy 5 (0, 0), (1, 0), (0, 1) Grundy {0, 1, 1} 2 (1, 1) Grundy 2 (2, 0) Grundy 6 (2, 0) (1, 0), (0, 0) Grundy {1, 0} Grundy 2 (2, 1) Grundy 7 (2, 1) (1, 0), (2, 0), (0, 1), (1, 1) Grundy {1, 2, 1, 2} (2, 1) Grundy 0 Grundy Grundy 8 3. Corner the Queen Problem Queen Queen (0, 0) move(x, y) (2) 2

3 move(x, y) ={(u, y) :u<x} {(x, v) :v<y} (2) ( ) 3.2. () 2 (0, 0) move (3) Grundy 11 move(x, y) ={(x t, y t) :0<t min(x, y)} {(x, y 1)} {(x 1,y)} (3) (1.3.1) x G(x, y) =y 1. (1.3.2) x G(x, y) =y 2 (1.4) y =3(mod 4) (1.4.1) x G(x, y) =y 1. (1.4.2) x G(x, y) =y (2) x y (2.1) x =0(mod 4) (2.1.1) y G(x, y) =x. (2.1.2) y G(x, y) =x +1 (2.2) x =1(mod 4) (2.2.1) y G(x, y) =x + 2. (2.2.2) y G(x, y) =x +1 (2.3) x =2(mod 4) (2.3.1) y G(x, y) =x 1. (2.3.2) y G(x, y) =x 2 (2.4) x =3(mod 4) (2.4.1) y G(x, y) =x 1. (2.4.2) y G(x, y) =x ( ) 3.3. ( ) 2 (0, 0) Grundy Grundy 3.1. Grundy (1) y x (1.1) y =0(mod 4) (1.1.1) x G(x, y) =y. (1.1.2) x G(x, y) =y +1 (1.2) y =1(mod 4) (1.2.1) x G(x, y) =y + 2. (1.2.2) x G(x, y) =y +1 (1.3) y =2(mod 4) 12 move (4) Grundy 13 move(x, y) ={(u, y) :u<x} {(x, v) :v<y} {(x 1,y 1)} (4) Grundy 3

4 s =3t + u {3((k t) h)+u : t =1, 2,...,k} {3(k (h 1)) + u : t =1, 2,...,h} (11) mex 3.2. ( Grundy ) 13 Grundy G(x, y) =mod(x + y, 3) + 3( x 3 y ) (12) 3 mod(x + y, 3) x + y k h = mex({(k t) h : t =1, 2,...,k} {k (h t) :t =1, 2,...,h}). (5) (k h) =mex( {3((k t) h)+u : t =1, 2,...,k} {3(k (h t)) + u : t =1, 2,...,h}). (6). (u, v) u <x v<y (12) (x, y) =(3k, 3h) move((x, y)) = {(3k t, 3h) :t =1, 2,...,3k} {(3k, 3h t) :t =1, 2,...3h} {(3k 1, 3h 1)} (13) Grundy G((x, y)) = mex({g((3k t, 3h)) : t =1, 2,...,3k} {G((3k, 3h t)) : t =1, 2,...,3h} {G((3k 1, 3h 1))}) (14). 3.1 mex k h/ {(k t) h : t =1, 2,...,k} {k (h t) :t =1, 2,...,h} (7) (14) mex({3((k 1) h)+2, 3((k 1) h)+1,..., 3(0 h)+2, 3(0 h)+1, 3(0 h)} 3(k h) / {3((k t) h) :t =1, 2,...,k} {3(k (h t)) : t =1, 2,...,h}. (8) 3(k h) 3 3(k h) / {3((k t) h)+u : t =1, 2,...,k} {3(k (h t)) + u : t =1, 2,...,h} (9) 3(k h) >s 0 s s =3t + u t, u ( u =0, 1, 2) k h>t mex t {(k t) h : t =1, 2,...,k} {k (h t) :t =1, 2,...,h} (10) {3(k (h 1)) + 2, 3(k (h 1)) + 1, 3(k (h 1)),...,3(k 0) + 2, 3(k 0) + 1, 3(k 0)} {3((k 1) (h 1)) + 2}) = mex( {3((k t) h)+u : t =1, 2,...,k} {3(k (h t)) + u : t =1, 2,...,h} {3(k h)+2}). (15) 3(k h)+2 3(k h) 3.2 (15) 3(k h) (x, y) =(3k +1, 3h), (3k +2, 3h),

2 (Nim) Nim 15 G(y, z) =y z z 1 Grundy [4] 5.1. 18 19 14 15 14 16 16 17 6. Grundy y z 5 Grundy Grundy 20 Grundy 16 17 20 z 1 1 4.1. G, H G + H 2 G H 16 Grundy 5.

17 y, z 18 19 Grundy 6.1. 20 Grundy G({y, z}) p, q, r G(2p, 2q) =2q + p (16) G(2p +1, 2q) =2q p 1 max(0, 2p q + 1) (17) G(2p, 2q + 1) = 2q p +1 max(0, 2p

5 2 (Nim) Nim 15 G(y, z) =y z z 1 Grundy [4] Grundy y z 5 Grundy Grundy 20 Grundy z G, H G + H 2 G H 16 Grundy 5. Grundy G(y, z) =y z Grundy G(y, z) =y z y, z Grundy Grundy G({y, z}) p, q, r G(2p, 2q) =2q + p (16) G(2p +1, 2q) =2q p 1 max(0, 2p q + 1) (17) G(2p, 2q + 1) = 2q p +1 max(0, 2p q) (18) G(2p +1, 2q + 1) = 2q + p +2 (19) G(2p, 2(p + r)) = 3p +2r (20) G(2p +1, 2(p + r)) = p +2r 1 max(0,p r + 1) (21) G(2p, 2(p + r) + 1) = p +2r +1 max(0,p r) (22) G(2p +1, 2(p + r) + 1) = 3p +2r +2 (23) Grundy Grundy G({6, 16}) 5

6 Z Y Y Z Grundy 23 ({5,12}) move Y Z ({6,16}) move {G({y, z}); {y, z} move({6, 16})} = {G({5, 16}),G({4, 16}),...,G({0, 16})} (24) {G({6, 15}),G({6, 14}),...,G({6, 7})} (25) {G({6, 6}),G({5, 5}),...,G({0, 0})}. (26) (24) (25) (26) Grundy {13, 18, 14, 17, 15, 16} {12, 17, 10, 15, 7, 13, 4, 11, 1} {9, 8, 6, 5, 3, 2, 0} 22 {6, 16} Grundy G({6, 16}) 19 G({6, 16}) = Grundy G({5, 12}) {G({y, z}); {y, z} move({5, 12})} 23 {5, 12} {6, 16} Grundy G({5, 12}) 9 G({5, 12}) =9 6.1 z 3 1 [1] M. H. Albert, --,, (M. H. Albert, R. J. Nowakowski and D. Wolfe, Lessons In Play, A K Peters.) [2], - -,, [3],,, Vol.1955, pp.81-90, [4] R.Miyadera and S.Nakamura,IMPARTIAL CHOCO- LATE BAR GAMES, INTEGERS -electronic journal of combinatorial number theory-,15,2015. [5],,,,,,,, 9, pp.4-10, [6],,,, (GI),2015-GI-33(15),1-5. = {G({4, 12}),G({3, 12}),...,G({0, 12})} (27) {G({5, 11}),G({5, 10}),...,G({5, 6})} (28) {G({5, 5}),G({4, 4}),...,G({0, 0})}. (29) (27) (28) (29) Grundy {14, 10, 13, 16, 11, 12} {14, 7, 12, 4, 10, 1} {8, 6, 5, 3, 2, 0} 6

[4] 1.1. x,y 2 x = n i=0 x i2 i,y = n i=0 y i2 i (x i, y i {0, 1}) x y x y = w i 2 i, (1.1) w i = x i + y i (mod 2) (a) (N -Position)

[4] 1.1. x,y 2 x = n i=0 x i2 i,y = n i=0 y i2 i (x i, y i {0, 1}) x y x y = w i 2 i, (1.1) w i = x i + y i (mod 2) (a) (N -Position) () 2 1 2 2 1.1 3,3,2 3 3 3 2 {3, 3, 2} 1.2 1.4 3 1.1 {x, y, z} 3 {x, y, z} 3 x y z [1] x y z x y z 1.5 1.6 x y z [1] Z 0 x i {0, 1} x i 0 1 1.1. {x, y, z} (x, y, z Z 0 ) 1.1 {3, 3, 2} 1.2 {4, 4, 9} 1.3