> Help26 := proc() print(`SGnim(L), FindPer(L), NimSum(a,b)  `); end proc;
> SGnim := proc(L) local k, i, j, C, c; option remember; k := nops(L); C := {seq(seq([op(1 .. i - 1, L), j, op(i + 1 .. k, L)], j = 0 .. L[i] - 1), i = 1 .. k)}; mex({seq(SGnim(c), c in C)}); end proc;
> IsPer1 := proc(L, p) local i; for i to nops(L) - p do if L[i] <> L[i + p] then RETURN(false); end if; end do; true; end proc;
> FindPer := proc(L) local p; for p to trunc(1/2*nops(L)) do if IsPer1(L, p) then RETURN([op(1 .. p, L)]); end if; end do; FAIL; end proc;
> NimSum := proc(a, b) option remember; if a = 0 and b = 0 then RETURN(0); end if; if a mod 2 = 0 and b mod 2 = 0 then RETURN(2*NimSum(1/2*a, 1/2*b)); elif a mod 2 = 1 and b mod 2 = 0 then 2*NimSum(1/2*a - 1/2, 1/2*b) + 1; elif a mod 2 = 0 and b mod 2 = 1 then 2*NimSum(1/2*a, 1/2*b - 1/2) + 1; else 2*NimSum(1/2*a - 1/2, 1/2*b - 1/2); end if; end proc;
> Help25 := proc() print(` CP(G1,G2) , SG(G) `); end proc;
> CP := proc(G1, G2) local n1, n2, i1, i2, S1, S2, s1, s2, V, T, ID, s, G, S, i; n1 := nops(G1); n2 := nops(G2); for i1 to n1 do for i2 to n2 do S1 := G1[i1]; S2 := G2[i2]; T[i1, i2] := {seq([i1, s2], s2 in S2)} union {seq([s1, i2], s1 in S1)}; end do; end do; V := [seq(seq([i1, i2], i2 = 1 .. n2), i1 = 1 .. n1)]; for i1 to nops(V) do ID[V[i1]] := i1; end do; G := []; for i to nops(V) do S := T[op(V[i])]; G := [op(G), {seq(ID[s], s in S)}]; end do; G; end proc;
> SG := proc(G) local n, L, T, i, j, s; n := nops(G); L := GenS(G); for i in L[1] do T[i] := 0; end do; for j from 2 to nops(L) do for i in L[j] do T[i] := mex({seq(T[s], s in G[i])}); end do; end do; [seq(T[i], i = 1 .. n)]; end proc;
> Help24 := proc() print(`GenSn(G), WikiCent(n), LaC(G,R), WikiCent1(n)  `); print(`LabelP(L), Sparta(), Sandy() `); end proc;
> Sandy := proc() [{2, 3}, {3}, {}], [Sandy, Dicky, Lucy]; end proc;
> Sparta := proc() [{2, 3}, {5}, {4}, {5}, {}], [Anaxandridas, Leonidas, Cleomenes, Gorgo, Pleistarchus]; end proc;
> LabelP := proc(L) local i; i := max[index]([seq(L[i][2], i = 1 .. nops(L))]); [L[i][2], L[i][1]]; end proc;
> LaC := proc(G, R) local n, L, T, i, j, r, k; n := nops(G); L := GenS(G); if {seq(r[1], r in R)} <> L[1] then RETURN(FAIL); end if; for r in R do T[r[1]] := r[2]; end do; for j from 2 to nops(L) do for i in L[j] do T[i] := LabelP([seq(T[k], k in G[i])]); end do; end do; [seq(T[i], i = 1 .. n)]; end proc;
> WikiCent := proc(n) local i, G, P; G := [seq({i + 1, i + 2*n + 1}, i = 1 .. 2*n), seq({}, i = 1 .. 2*n + 1)]; P := {seq([2*n + 3 + i, [i, i + 2]], i = 0 .. 2*n - 2), [2*n + 1, [2*n - 0.9, 2*n - 0.9]], [2*n + 2, [0, 1]]}; G, P; end proc;
> WikiCent1 := proc(n) local i, G, P; G := [seq({i + 1, i + 2*n + 1}, i = 1 .. 2*n - 1), {2*n + 1}, seq({}, i = 1 .. 2*n + 1)]; P := {seq([2*n + 3 + i, [i, i + 2]], i = 0 .. 2*n - 2), [2*n + 1, [2*n - 0.9, 2*n - 0.9]], [2*n + 2, [0, 1]]}; G, P; end proc;
> GenSn := proc(G) local n, T, i, j, NYD, AD, j1, ma, AP; AP := {seq(op(G[i]), i = 1 .. nops(G))}; ma := max(AP); if nops(G) < ma then RETURN(FAIL); end if; n := nops(G); NYD := {seq(i, i = 1 .. n)}; T[1] := {}; for i to n do if G[i] = {} then T[1] := T[1] union {i}; end if; end do; NYD := NYD minus T[1]; AD := T[1]; for j from 2 while NYD <> {} do T[j] := {}; for i in NYD do if G[i] minus AD = {} then T[j] := T[j] union {i}; end if; end do; AD := AD union T[j]; NYD := NYD minus T[j]; end do; [seq(T[j1], j1 = 1 .. j - 1)]; end proc;
> Help23 := proc() print(` GenS(G), Els() `); end proc;
> GenS := proc(G) local n, T, i, j, NYD, AD, j1; n := nops(G); NYD := {seq(i, i = 1 .. n)}; T[1] := {}; for i to n do if G[i] = {} then T[1] := T[1] union {i}; end if; end do; NYD := NYD minus T[1]; AD := T[1]; for j from 2 while NYD <> {} do T[j] := {}; for i in NYD do if G[i] minus AD = {} then T[j] := T[j] union {i}; end if; end do; AD := AD union T[j]; NYD := NYD minus T[j]; end do; [seq(T[j1], j1 = 1 .. j - 1)]; end proc;
> LaGn := proc(G) local n, L, T, i, j, s; n := nops(G); L := GenS(G); for i in L[1] do T[i] := 0; end do; for j from 2 to nops(L) do for i in L[j] do if member(0, {seq(T[s], s in G[i])}) then T[i] := 1; else T[i] := 0; end if; end do; end do; [seq(T[i], i = 1 .. n)]; end proc;
> Els := proc() [{2, 6}, {3, 7}, {4, 8}, {5, 9}, {}, {}, {}, {}, {}], {[5, [3, 4]], [6, [-1, 2]], [7, [1, 2]], [8, [1, 4]], [9, [6, 3]]}; end proc;
> Els1 := proc() [{2, 6}, {3, 7}, {4, 8}, {9}, {}, {}, {}, {}, {}], {[5, [3, 4]], [6, [-1, 2]], [7, [1, 2]], [8, [1, 4]], [9, [6, 3]]}; end proc;
> Help22 := proc() print(`mex(S), ai(i), aiC(i), RDG(n,p), Parents(G), OneStep0(G,AL,T)  , OneStep1(G,AL,T), OneStep(G,AL,T), LaG(G)    `); end proc;
> mex := proc(S) local i; for i from 0 while member(i, S) do ; end do; i; end proc;
> ai := proc(i) local j; option remember; if i = 0 then RETURN(0); else mex({seq(ai(j) + j, j = 0 .. i - 1), seq(ai(j), j = 0 .. i - 1)}); end if; end proc;
> aiC := proc(i) trunc(1/2*(1 + sqrt(5))*i); end proc;
> RDG := proc(n, p) local a, b, L, i, j, S, ra; a := numer(p); b := denom(p); ra := rand(1 .. b); L := []; for i to n do S := {}; for j from i + 1 to n do if ra() <= a then S := S union {j}; end if; end do; L := [op(L), S]; end do; L; end proc;
> Parents := proc(G) local n, i, j, P; option remember; n := nops(G); for j to n do P[j] := {}; end do; for i to n do for j in G[i] do P[j] := P[j] union {i}; end do; end do; [seq(P[j], j = 1 .. n)]; end proc;
> OneStep0 := proc(G, AL, T) local AL1, n, T1, i, j, P; AL1 := AL; n := nops(G); P := Parents(G); T1 := T; for i in AL do if T1[i] = 0 then for j in P[i] do T1 := [op(1 .. j - 1, T1), 1, op(j + 1 .. n, T1)]; AL1 := AL1 union {j}; end do; end if; end do; RETURN(G, AL1, T1); end proc;
> OneStep1 := proc(G, AL, T) local n, T1, i, j; n := nops(G); T1 := T; for i to n do if not member(i, AL) then if G[i] minus AL = {} and {seq(T1[j], j in G[i])} = {1} then T1 := [op(1 .. i - 1, T1), 0, op(i + 1 .. n, T1)]; RETURN(G, AL union {i}, T1); end if; end if; end do; G, AL, T1; end proc;
> OneStep := proc(G, AL, T) local n, Hope; n := nops(G); if nops(AL) = n then RETURN(G, AL, op(T)); end if; Hope := OneStep0(G, AL, T); if nops(AL) < nops(Hope[2]) then RETURN(Hope); end if; Hope := OneStep1(G, AL, T); if nops(AL) < nops(Hope[2]) then RETURN(Hope); end if; FAIL; end proc;
> LaG := proc(G) local n, i, AL, T, Hope; n := nops(G); T := [(-1) $ n]; AL := {}; for i to n do if G[i] = {} then T := [op(1 .. i - 1, T), 0, op(i + 1 .. n, T)]; AL := AL union {i}; end if; end do; Hope := G, AL, T; while nops(Hope[2]) < n do Hope := OneStep(Hope); end do; [seq(Hope[3][i], i = 1 .. n)]; end proc;
> Help25hw := proc() print(`BestPrune(G,R), RandCent(n,p,K), FindParadox(n,p,K,K1), ExC()`); end proc;
> BestPrune := proc(G, R) local n, i, j, curBest, Gtry, bestEdge, updated, current; n := nops(G); curBest := LaC(G, R)[1]; updated := false; for i to n do for j in G[i] do Gtry := G; Gtry[i] := Gtry[i] minus {j}; current := LaC(Gtry, R); if current <> FAIL then current := current[1]; if curBest[1] < current[1] and curBest[2] < current[2] then curBest := current; bestEdge := [i, j]; updated := true; end if; end if; end do; end do; if updated then return bestEdge; end if; FAIL; end proc;
> BestPrune(Els());
> BestPrune(WikiCent(20));
> RandCent := proc(n, p, K) local G, R, k, i; G := RDG(n, p); R := {}; k := rand(K + 1); for i to n do if G[i] = {} then R := R union {[i, [k(), k()]]}; end if; end do; G, R; end proc;
> FindParadox := proc(n, p, K, K1) local i, game, pruned; for i to K1 do game := RandCent(n, p, K); pruned := BestPrune(game); if pruned <> FAIL then return game, pruned; end if; end do; FAIL; end proc;
> ExC := proc() [{4, 5, 7, 10, 11, 14, 15, 16, 18, 22, 24, 25, 26, 27, 28, 29, 30}, {4, 5, 8, 10, 16, 17, 19, 20, 21, 22, 25, 30}, {5, 8, 9, 10, 15, 18, 21, 24, 27, 28, 30}, {8, 10, 11, 14, 15, 17, 18, 19, 21, 23, 24, 25, 26, 28, 29}, {7, 9, 10, 11, 15, 17, 18, 20, 21, 22, 23, 24, 29}, {8, 14, 17, 18, 19, 23, 25, 27, 29}, {8, 9, 10, 15, 16, 17, 20, 21, 22, 24, 25, 27, 28, 30}, {9, 11, 12, 14, 15, 17, 21, 22, 23, 25, 26, 27, 30}, {11, 14, 15, 18, 19, 20, 22, 25, 26, 27}, {11, 12, 13, 14, 16, 17, 25, 27, 29, 30}, {17, 18, 19, 20, 21, 22, 23, 24, 27, 28, 30}, {13, 14, 19, 20, 21, 22, 23, 24, 25, 30}, {14, 19, 23, 24, 25, 26, 27, 30}, {15, 17, 20, 21, 25, 26, 28, 29, 30}, {17, 18, 22, 25, 26, 30}, {17, 18, 21, 23, 24, 26, 27, 30}, {21, 23, 24, 25, 27, 28}, {22, 23, 25, 27, 29}, {23, 24, 28, 29, 30}, {21, 23, 24, 26, 29, 30}, {25, 27, 29}, {23, 25, 27, 28}, {26, 27, 28, 30}, {25, 26, 27, 28, 29, 30}, {27, 29, 30}, {27, 28}, {28, 29}, {29}, {}, {}], {[29, [2, 46]], [30, [47, 46]]}; end proc;
> FindUP := proc(L) local i, j; for i to 1/2*nops(L) do if FAIL <> FindPer([seq(L[j], j = i .. nops(L))]) then return [seq(L[j], j = 1 .. i - 1)], FindPer([seq(L[j], j = i .. nops(L))]); end if; end do; FAIL; end proc;
> SGwyt := proc(a, b) local k, i, j, C, c, L, t; option remember; L := [a, b]; k := 2; C := {seq([a - i, b - i], i = 0 .. min(a, b) - 1), seq([i, b], i = 0 .. a - 1), seq([a, i], i = 0 .. b - 1)}; mex({seq(SGnim(c), c in C)}); end proc;
> seq(FindUP([seq(SGwyt(i, b) - b, b = 0 .. 10*i)]), i = 1 .. 20);
[1], [1, 2], [2], [3, -1, 1, 3], [3], [3, 2, 1, 4], [4], 



  [5, 5, 5, -3, -3, -3, 1, 5], [5], [5, 6, 5, -2, -3, 2, 1, 6], 



  [6], [7, 3, 5, -1, 3, -5, 1, 7], [7], [7, 6, 5, 4, 3, 2, 1, 8], 



  [8], [9, 9, 9, 9, 9, 9, 9, -7, -7, -7, -7, -7, -7, -7, 1, 9], 



  [9], 



  [9, 10, 9, 10, 9, 10, 9, -6, -7, -6, -7, -6, -7, 2, 1, 10], 



  [10], 



  [11, 7, 9, 11, 11, 7, 9, -5, -5, -9, -7, -5, 3, -9, 1, 11], 



  [11], 



  [11, 10, 9, 12, 11, 10, 9, -4, -5, -6, -7, 4, 3, 2, 1, 12], 



  [12], 



  [13, 13, 13, 5, 5, 5, 9, -3, -3, -3, 5, -11, -11, -11, 1, 13], 



  [13], 



  [13, 14, 13, 6, 5, 10, 9, -2, -3, 6, 5, -10, -11, 2, 1, 14], 



  [14], 



  [15, 11, 13, 7, 11, 3, 9, -1, 7, -5, 5, -9, 3, -13, 1, 15], 



  [15], [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 16], 



  [16], [17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 



  17, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, -15, 



  -15, -15, -15, 1, 17], [17], [17, 18, 17, 18, 17, 18, 17, 18, 



  17, 18, 17, 18, 17, 18, 17, -14, -15, -14, -15, -14, -15, -14, 



  -15, -14, -15, -14, -15, -14, -15, 2, 1, 18], [18], [19, 15, 



  17, 19, 19, 15, 17, 19, 19, 15, 17, 19, 19, 15, 17, -13, -13, 



  -17, -15, -13, -13, -17, -15, -13, -13, -17, -15, -13, 3, -17, 



  1, 19], [19], [19, 18, 17, 20, 19, 18, 17, 20, 19, 18, 17, 20, 



  19, 18, 17, -12, -13, -14, -15, -12, -13, -14, -15, -12, -13, 



  -14, -15, 4, 3, 2, 1, 20], [20], [21, 21, 21, 13, 13, 13, 17, 



  21, 21, 21, 21, 13, 13, 13, 17, -11, -11, -11, -11, -19, -19, 



  -19, -15, -11, -11, -11, 5, -19, -19, -19, 1, 21]




;
> seq(SGwyt(3, b) - b, b = 0 .. 100);
3, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 



  2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 



  1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 



  4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 



  3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4




;
> SGwyt(5, 10100);
> NULL;