Alice and Bob are playing a game where they take turns drawing on a piece of...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Alice and Bob are playing a game where they take turns drawing on a piece of paper. Alice goes first and Bob goes second. The rules of the game are as follows: • We start off with n crosses, i.e. spots with four free ends. • During their turn, a player must connect any two free ends with a curve, provided the curve does not intersect any existing curves or crosses, and then add a stroke across the curve to create two more free ends. • If any player cannot move, they lose the game. Above, we have an example of states of a game with n=2 at the start, after one move, and after the game has concluded. (a) (6 pts) Note that the graph formed by the curves is always planar. Assume that the center of each cross is a vertex and any intersection of a curve with a stroke is also a vertex. The curves connecting two vertices are edges. Note that each move in the game therefore is adding two edges even though it is described as drawing a single curve. After m moves have been made, how many vertices, edges, and free ends are there on the paper? Recall that at m = 0, we start with v(0) =n vertices, e(0) =0 edges, and fe(0) = 4n free ends. v(m) = e(m) = %3D .(m) = 6. Graph Game (21 pts) Alice and Bob are playing a game where they take turns drawing on a piece of paper. Alice goes first and Bob goes second. The rules of the game are as follows: • We start off with n crosses, i.e. spots with four free ends. • During their turn, a player must connect any two free ends with a curve, provided the curve does not intersect any existing curves or crosses, and then add a stroke across the curve to create two more free ends. • If any player cannot move, they lose the game. Above, we have an example of states of a game with n= 2 at the start, after one move, and after the game has concluded. (a) (6 pts) Note that the graph formed by the curves is always planar. Assume that the center of each cross is a vertex and any intersection of a curve with a stroke is also a vertex. The curves connecting two vertices are edges. Note that each move in the game therefore is adding two edges even though it is described as drawing a single curve. After m moves have been made, how many vertices, edges, and free ends are there on the paper? Recall that at m = 0, we start with v(0) =n vertices, e(0) =0 edges, and f.(0) = 4n free ends. v(m) = e(m) = %3D F.(m) %3D (b) (3 pts) When the game concludes, the graph must be connected and planar. A planar graph subdivides the plane into faces. How many free ends can be in a face of this concluding planar graph? (c) (12 pts) Since Alice goes first and Bob and Alice alternate turns, Alice plays odd numbered moves and Bob plays even numbered ones. For which n does Alice win and for which n does Bob win? Justify your answer. Alice and Bob are playing a game where they take turns drawing on a piece of paper. Alice goes first and Bob goes second. The rules of the game are as follows: • We start off with n crosses, i.e. spots with four free ends. • During their turn, a player must connect any two free ends with a curve, provided the curve does not intersect any existing curves or crosses, and then add a stroke across the curve to create two more free ends. • If any player cannot move, they lose the game. Above, we have an example of states of a game with n=2 at the start, after one move, and after the game has concluded. (a) (6 pts) Note that the graph formed by the curves is always planar. Assume that the center of each cross is a vertex and any intersection of a curve with a stroke is also a vertex. The curves connecting two vertices are edges. Note that each move in the game therefore is adding two edges even though it is described as drawing a single curve. After m moves have been made, how many vertices, edges, and free ends are there on the paper? Recall that at m = 0, we start with v(0) =n vertices, e(0) =0 edges, and fe(0) = 4n free ends. v(m) = e(m) = %3D .(m) = 6. Graph Game (21 pts) Alice and Bob are playing a game where they take turns drawing on a piece of paper. Alice goes first and Bob goes second. The rules of the game are as follows: • We start off with n crosses, i.e. spots with four free ends. • During their turn, a player must connect any two free ends with a curve, provided the curve does not intersect any existing curves or crosses, and then add a stroke across the curve to create two more free ends. • If any player cannot move, they lose the game. Above, we have an example of states of a game with n= 2 at the start, after one move, and after the game has concluded. (a) (6 pts) Note that the graph formed by the curves is always planar. Assume that the center of each cross is a vertex and any intersection of a curve with a stroke is also a vertex. The curves connecting two vertices are edges. Note that each move in the game therefore is adding two edges even though it is described as drawing a single curve. After m moves have been made, how many vertices, edges, and free ends are there on the paper? Recall that at m = 0, we start with v(0) =n vertices, e(0) =0 edges, and f.(0) = 4n free ends. v(m) = e(m) = %3D F.(m) %3D (b) (3 pts) When the game concludes, the graph must be connected and planar. A planar graph subdivides the plane into faces. How many free ends can be in a face of this concluding planar graph? (c) (12 pts) Since Alice goes first and Bob and Alice alternate turns, Alice plays odd numbered moves and Bob plays even numbered ones. For which n does Alice win and for which n does Bob win? Justify your answer.
Expert Answer:
Answer rating: 100% (QA)
Solution 6 a The graph vm nm grows by one vertex with each step The graph em 2m ... View the full answer
Related Book For
Fundamentals of Physics
ISBN: 978-0471758013
8th Extended edition
Authors: Jearl Walker, Halliday Resnick
Posted Date:
Students also viewed these mathematics questions
-
Two children are playing a game in which they try to hit a small box on the floor with a marble fired from a spring-loaded gun that is mounted on a table. The target box is horizontal distance D =...
-
Some friends are playing a game in which two six-sided dice are rolled (craps, Settlers of Catan, etc.). One of them exclaims, Since the sum of the dice is between 2 and 12, there is a one in eleven...
-
A and B plays a game in which As probability of winning is 23 In a series of 8 games what is the probability that A will win (i)exactly 4 games, (ii) at least 4 games, (iii) 6 or more games and (iv)...
-
Why should every credit application be signed by the applicant or an authorized officer of the applicant? There are several factors that influence the setting of the terms and conditions of a sale....
-
Thermodynamics of a solid-state reaction. The following electrochemical cell is reversible at 1 000 K in an atmosphere of flowing O2(g):19 (a) Write a Nernst equation for each half-cell. Write the...
-
The flowers in a garden at a resort need to be replaced. The choices for the flowers are Geraniums (G), Impatiens (I), Petunias (P), and Zinnias (Z). The head gardener holds an election in which all...
-
World Series Champs As of this writing, the New York Yankees were the last team to win the World Series, and the numbers of the starting lineup are 2, 18, 25, 13, 20, 55, 24, 33, and 53. The average...
-
Refer to Cornerstone Exercise 8.13. In March, Nashler Company produced 163,200 units and had the following actual costs: Direct materials..... $1,170,000 Direct labor ........ 258,000 Supplies...
-
7. (4 pts) Review the following entity-relationship diagram and then map the diagram to the appropriate tables. Be sure to include all required attributes for each table. SALESPERSON *Salesperson...
-
(a) A disk of mass M and radius R is held up by a massless string, as shown in Fig. The surface of the disk is frictionless. What is the tension in the string? What is the normal force per unit...
-
Analyze the financial strength and trends of the two ompanies. Complete the provided template A for BOTH companies. Write a one-page summary which should include; o Comments on the trends for EACH...
-
On April 1, 2023, Arnold, Bryan and Mathieu form a limited liability partnership to start a small public accounting firm. Arnold, Bryan and Mathieu have invested $97,000, $47,000 and $54,000...
-
Once Tesla determines that it plans to manufacture 100 vehicles each week for the next 3 years, they will procure the tires for the vehicles through a contract. Provide one reason that they would not...
-
President Biden has announced that he will end the Covid-19 public health emergency on May 11. What would be the Moral Hazard implications in the short term or the long term as Tests, vaccines and...
-
Instacart allows an individual who needs groceries (the principal) to hire a personal shopper (the agent) to go to the store and buy their groceries for them. The principal makes a list of grocery...
-
1)What is project portfolio management and why is it becoming so important for organizations? 2) You have a sports store in Toronto that has been closed since the beginning of the pandemic. Recently...
-
What type of technology performs real-time SOC (Security Operations Center) functions such as identifying, monitoring, recording, auditing, and analyzing security incidents? explain
-
The outer loop controls the number of students. Note that the inner loop of this program is always executed exactly three times, once for each day of the long weekend. Modify the code so that the...
-
The inductor arrangement of Figure with L1 = 30.0 mH, L2 = 50.0 mH, L3 = 20.0 mH, and L4 = 15.0 mH, is to be connected to a varying current source. What is the equivalent inductance of the...
-
During a compression at a constant pressure of 250 Pa, the volume of an ideal gas decreases from 0.80 m3 to 0.20 m3. The initial temperature is 360 K, and the gas loses 210 J as heat. What are (a)...
-
A ton is a measure of volume frequently used in shipping, but that use requires some care because there are at least three types of tons: A displacement ton is equal to 7 barrels bulk, a freight ton...
-
Renaldo borrows $8,000 from his aunt today to help pay for college expenses. He agrees to repay the loan according to the following schedule, at a rate of 6 percent/year compounded annually. a. Draw...
-
Ken loans his grandson Rex $20,000 at 5.5 percent per year to help pay for executive chef schooling in Florida. Rex requires 3 years of schooling before beginning to earn a salary. He agrees to pay...
-
An investment has the following cash flow series where interest is 5 percent: a. Determine the present worth of the series. b. Determine the future worth of the series at the end of year 8. c. Find...
Study smarter with the SolutionInn App