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....
-
Minden Corporations records show the following results for its first three years of operations: In year 4, Minden generated $2 million taxable income ($900,000 of which was foreign source) and paid...
-
The polar form of an equation of a curve is r = (sin ). Show that the form becomes (a) r = (-cos ) if the curve is rotated counterclockwise /2 radians about the pole. (b) r = (-sin ) if the curve is...
-
You are offered the opportunity to buy a note for \($12,800.\) The note is certain to pay \($2,000\) at the end of each of the next 10 years. If you buy the note, what rate of interest will you...
-
1. Draw an ERD for the Parrot Palace information system. 2. Indicate cardinality. 3. Identify all fields you plan to include in the birds and tricks tables. For example, in the bird table, you might...
-
4.35 Comprehensive problem of preparing a worksheet, statement of profit or loss and statement of financial position LO5 Rotterdam Financial Services Pty Ltd, managed by Saphira Browne, provides...
-
Mullet, Shark and Starfish operate a business which conducts deep sea fishing trips. Their partnership agreement states that all profits and losses are to be shared in the ratio of 3:2:1 after...
-
A semaphore is a shared integer variable __________.
-
Puget Sound Divers is a company that provides diving services such as underwater ship repairs to clients in the Puget Sound area. The company's planning budget for May appears below: Puget Sound...
-
Are you courageous enough to abandon a practice that has made you successful in the past? Great leaders dare to be different. They build the emotional stamina to withstand opposition.?
-
On March 1, 2017 Green Company purchased a new piece of equipment for 210,000 cash. On March 1 Green recorded the equipment purchase with a Debit to the Equipment account and a Credit to the Cash...
-
Read the following article: Goodbye Performance Reviews? written by Natalie Barker, Head of Transformation at Southern Cross Health Insurance and published in the HRNZ magazine (Vol 26, No. 24) in...
-
DanceByte Limited is a leading software development company located in Sandton, Johannesburg. The company's current reporting period ends on 31 December 2018. The following are some of the...
-
Lathe bed is made of _ _ _ _ ( A ) cast iron ( B ) cast steel ( C ) mild steel ( D ) pig iron
-
A Alkynes can be made by dehydrohalogenation of vinylic halides in a reaction that is essentially an E2 process. In studying the stereochemistry of this elimination, it was found that...
-
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...
-
You have agreed to text your friend every 3 hours while driving across the country. You began your trip at 8 AM. What time will it be when you text your friend the 15 th time?
-
If it is \(7: 00\) now, what time was it 34 hours ago?
-
What is the product of 4 and 19 modulo 12 ?
Study smarter with the SolutionInn App