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....
-
Use the solubility rules (Table 4.1) to decide which of the following compounds are expected to be soluble and which insoluble. a. Ca(NO3)2 b. AgBr c. MgI2 d. PbSO4
-
Identify the issue considered in developing corporate strategies. The current business(es) that the organization is in The direction in which the organization is moving The resources utilized for...
-
An axle is subjected to (a) axial load (b) bending load (c) torsional load (d) bending and torsion
-
Hickey Corporation is a manufacturer that produces a single product. The following information has been taken from the companys production, sales, and cost records for the just completed year:...
-
Discuss the role of mass transfer coefficients and the impact of interfacial phenomena in gas-liquid absorption processes. How do hydrodynamic conditions influence the efficiency of mass transfer ?
-
Translate each of the following arguments into symbolic form using the variables given below. D= The drought will continue. S=We get an early storm. M= Managers of the ski areas will be happy. F =...
-
Complete Form 1120 for Alvins Music Inc., using the information provided below. You need not complete Form 4797 for the sale of the equipment. Include the tax gain as other income on page one of Form...
-
Consider a vote for four candidates with the following results: Use this information for Problems 9-11. If there is a tie, break the tie by having a runoff of the tied candidates. Who wins by the...
-
Use this information to answer the questions in Problems 12-17. a. If a person ranks \(A\) as her first choice, \(B\) as her second choice, and \(C\) last, how would this be written? b. How many...
-
Consider the following voting situation: Notice that there is no winner using the majority or plurality rules. a. Who would win in a runoff election by dropping the choice with the fewest first-place...
-
Chemistry is taught at five high schools in the Santa Rosa Unified School District. The district has just received a grant of 100 microscopes which are to be apportioned to the five high schools...
-
Modified quotas are given in Problems 7-14. Round your answers to two decimal places. a. Find the lower and upper quotas. b. Find the arithmetic mean of the lower and upper quotas. c. Find the...
-
Suppose some colleagues are having lunch together, and the only White colleague in the group is handed the check at the end of the meal. What does this represent?
-
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...
-
Where does the management accounting function fit into an organizations structure?
-
What are the ethical responsibilities of management accountants?
-
Diana Corporation provides the following information for 2017: Calculate (a) Cost of goods manufactured in 2017 and (b) Cost of goods sold in 2017 Beginning work-in-process inventory, 1/1/2017 Total...
Study smarter with the SolutionInn App