AMS 303 TEST 1 Fall 2022 Prof. Tucker
1. Give the cycle structure representation for a 135 degree rotation of the corners of a 8-gon.
ANS: 1/8th of the way around the circle is 45º. So 135º is 3/8ths around the circle. x8
2. (12 pts) a) Construct the matching network and make a flow corresponding to the partial matching
b-g,d-i, e-h, f-j.
b) Apply the Augmenting Flow Algorithm (show ALL labels) and from it give a complete matching.
New: b-h, c-g, d-i, e-k, f-j or b-g, c-j, d-k, e-h, f-i
3. (17 pts) Consider Nim on the right. 7 | | | | | | | 111 111 101(-2) 11 (move to 00)
a) What is its Grundy number? 5 | | | | | 101 101 101 01 remove 5
b) Move into a kernel position using 3rd pile. 3 | | | 011 000 (-3) 011 01
c) Move to position with Gr. number of 1 2 | | 010 010 010 00
3=011 000 001 11
d) Suppose that 1 or 5 or 6 sticks can be removed at a time, determine the Grundy number of the initial condition and then make a move into the kernel. 0 1 2 3 4 5 6 7
g(x) = 0 1 0 1 0 1 2 3
4.Give an expression for the pattern inventory of EDGE 2-colorings of the
unoriented figure below (rotations and flips allowed).
The 12 edges partition into subgroups of 4 edges. Same symmetries as a square
Rotations 0º (x1)^12, 90º and 270º 2(x4)^3, 180º (x2)^6
Flips at 45º and -45º diagonals 2(x2)^6, flips on vertical and horizontal axis 2(x1)^6*(x2)^5
Cycle index (1/8){(x1)^12 + 2(x4)^3 + 3(x2)^6 + 2(x1)^6*(x2)^5}, now set xi = (b^i + w^i).
5. In the following table of remaining games, is it possible for the Bears to be champions (NOT co-champions) if they win all remaining games? Build the appropriate network model. Answer the question with an appropriate flow in the network you created or with an explanation of why one is not possible.
Champ Wins Games with with with with
Team to date to play Bears Lions Tigers Vampires When Bears win all games- 27 wins-
Bears 21 6 — 1 2 3 other teams can have at most 26 wins
Lions 25 5 1 — 3 1 Lions and Tigers 1 more, V’s 3 more
Tigers 25 6 2 3 — 1 Not Possible. Lion and Tigers do not
Vampires 23 6 3 1 1 — have enough wins for their 3 games
against each other
L (L,T)
a T (L,V) z
V (T,V)
1 2 3 Supplies
6. a) Find a Northwest corner solution to this Trans. Problem. Warehouse 1 4 4 2 50
b) Find a set of prices based on this initial solution. 2 8 6 7 20
c) Find an entry, currently unused, whose use would 3 5 5 5 60
lower the cost of the solution Demands 20 70 40
d) Find a new spanning-tree solution using the edge found in c)
New solution is x11 = 20, , x13 = 30
x32 = 50 , x33 = 10
7a) Sketch an explanation of why we set xi = (bi+wi) in the cycle index to obtain the pattern inventory.
ANS: to get an inventory of the colorings left fixed by a symmetry, the corners in a cycle of
the symmetry must be all black or all white.
b) If a network has sources B,C,D with supplies of 40 each and factories W,X,Y with demands of 30,30,40, how do you convert this problem into a standard single source-single sink (each unlimited) problem?
ANS: add a new unlimited source with edges of capacity 40 to B,C,D; similarly for edges to new sink.
c) If position x has Grundy value g(x) = 5, for which of the following values 0, 4, 7 must there be successors of x with these Grundy values.
ANS: g(x) must be the smallest integer not used by x’s successors. If g(x) =5, then all smaller Grundy values must appear among x’s successors. Thus 0 and 4 must appear among x’s successors.
AMS 303 TEST 1 Spring 2022 Prof. Tucker
1. Give the cycle structure representation for a 240 degree rotation of the corners of a 9-gon.
ANS: (x3)^3 (240º = -120º)
2. a) Construct the matching network and make a flow corresponding to the partial matching b-g, c-h, e-j, f-k.
b) Apply the Augmenting Flow Algorithm (show ALL labels) and from it obtain a complete matching.
New matching b-i, c-g,d-h,e-j,f-k or b-g, c-h, d-j, e-k, f-i
3. a) Consider the game of Nim . | | | | | 5 101 a)101 b) 101 c) 11 -> 01 (move from 5 to 1)
One can remove any no. of objects| | 2 010 –>001 (-1) 010 00
from one of the 4. Find the Gr. | | | 3 011 011 010 (-1) 01
no. for this position & give move | | | | | | |7 111 111 111 00
into the kernel with move in pile 2. 011 000 010 10
b) Make a move, starting from the original game to a position with Grundy number 2 using pile 3.
c) Repeat part a) now with the constraint that a player must remove exactly 1 or 3 or 4 objects from a pile. Now you can remove sticks from any pile Pile size 0 1 2 3 4 5 6 7
g(x) 0 1 0 1 2 3 2 0
4.Give an expression for the pattern inventory of EDGE 2-colorings of the
unoriented regular figure below (rotations and flips allowed).
0º x1^11 180 rotation x1x2^5 vertical axis flip x1x2^5 horizontal axis flip x1^3×2^4
Cycle index (1/4)[x1^11 + 2x1x2^5 + x1^3×2^4] . Now set xi = (b^i + w^i).
5. In the following table of remaining games, it is possible for the Bears to be champions (NOT co-champions) if they win all remaining games? Build the appropriate network model. Answer the question with an appropriate flow in the network you created or with an explanation of why one is not possible.
Champ Wins Games with with with with
Team to date to play Bears Lions Tigers Vampires
Bears 21 6 — 1 2 3 other teams can win at most 26 games
Lions 25 5 1 — 2 2 Lions 1 more win
Tigers 25 6 2 2 — 1 Tiger 1 more win
Vampires 23 6 3 2 1 — Vampires 3 more wins
L (L,T) Is possible.
a T (L,V) z
V (T,V)
1 2 3 Supplies
6. a) Find a Northwest corner solution to this Trans. Problem. Warehouse 1 4 5 4 20
b) Find a set of prices based on this initial solution. 2 7 7 4 40
c) Find an entry, currently unused, whose use would 3 2 5 3 30
lower the cost of the solution Demands 30 20 40
d) Find a new spanning tree solution using entry in c)
New solution: x11=20 (unchanged), x21 (decreased to 0), x22 = 20 (unchanged), x23 = 20 (increased to 10),
x31 = 10 (new entry), x33 = 20 (decreased by 10)
7. a) What information is in a symmetry’s cycle structure representation?
ANS: The number of cycles of different lengths.
b) When the Augmenting Flow Algorithm terminates, consider the set P of vertices that could be labeled. Why is a minimum cut?
ANS: All edges from P to Pbar are saturated or else the Algorithm would have labeled more vertices, and for the same reason there is no flow in edges from Pbar to P.
c) If you know the kernel positions in levels k-1 and lower, how do you determine which positions at level k are in the kernel?
ANS: a vertex x at level k is in the kernel if none of its successors at lower levels are in the kernel.
AMS 303 TEST 1 Fall 2021 Prof. Tucker
1. (2 pts) Give the cycle structure representation for a 60 degree rotation of the corners of a 12-gon.
AN:S (x6)^2
2. (12 pts) a) Construct the matching network and make a flow corresponding to the partial matching
b-g,d-i, e-h, f-j.
b) Apply the Augmenting Flow Algorithm (show ALL labels) and from it give a complete matching.
New: b-h, c-g, d-i, e-k, f-j or b-g, c-j, d-k, e-h, f-i
a) b) c) d
3. (17 pts a) In given Nim game, | 001 001 001 01
find the Grundy no. of position. | | | | 100 -> 011(-1) 100 10
b) Give move in kernel using pile 2 | | | | | 101 101 -> 001(-4) 11
c) Move from original position | | | | | | | 111 111 111 11 00 (remove 5)
to a position with Grundy no. 3 using pile 3 111 000 011 11
d) repeat from original position, now with the constraint that a player must remove exactly 1 or 4 or 5 objects from a pile. Move to the kernel in pile 4.
0 1 2 3 4 5 6 7
g(x) = 0 1 0 1 2 3 2 3
4. (12 pts) Give an expression for the pattern inventory of EDGE 2-colorings of the
unoriented regular figure below (rotations and flips allowed).
18 edges; 12 symmetries: rotations 0º (x1)^18, +/-60º 2(x6)^3, +/-120º 2(x3)^6, 180º (x2)^9
flips: middle of opposite edges 3(x1)^4*(x2)^7 , of opposite vertices 3(x1)^2*(x2)^8
Cycle index (1/12){(x1)^18 + 2(x6)^3 + 2(x3)^6 + (x2)^9 +3(x1)^4*(x2)^7 + 3(x1)^2*(x2)^8}, set xi =(b^I + w^i)
5. (7 pts) In the following table of remaining games, it is possible for the Bears to be champions or co-champions if they win all remaining games? Build the appropriate network model. Answer the question with an appropriate flow in the network you created or with an explanation of why one is not possible.
Wins Games with with with with
Team to date to play Bears Lions Tigers Vampires When Bears wins all games, they
Bears 19 5 — 1 3 1 have 24 wins. So other teams can have
Lions 22 7 1 — 4 2 at most 24 wins.
Tigers 22 9 3 4 — 2 Lions and Tigers 2 more, Vampires 4
Vampires 20 5 1 2 2 — POSSIBLE
L (L,T)
a T (L,V) z
V (T,V)
1 2 3 Supplies
6. (10 pts) a) Find a Northwest corner solution to Trans. Probl. Warehouse 1 4 4 2 50
b) Find a set of prices based on this initial solution. 2 8 6 7 20
c) Find an entry, currently unused, whose use would 3 5 5 5 60
lower the cost of the solution Demands 20 70 40
d) Find a new spanning-tree solution using the edge found in c)
New solution is x11 = 20, , x13 = 30
x32 = 50 , x33 = 10
7.(15pts) a) Why is the sum of the number of symmetries that leave each coloring fixed (summed over all colorings) equal the sum of the number of colorings left fixed by each symmetry (summed over all symmetries)?
ANS: Both sums count all instances of some symmetry leaving some coloring fixed.
b) How does the Augmenting Flow Algorithm find a minimum a-z cut?
ANS: In the final iteration when the Algorithm cannot label z, the labeled vertices form the P side of a minimum a-z (P,Pbar) cut.
c) Why is it important in progressively finite games that the game must end after a finite number of moves?
ANS: Level numbers (used to find kernel and Grundy no.’s) can only be defined if the longest path from each vertex is finite; or there will be no winner if the game does not end.