homework作业 | assignment – 算法

2022-10-30

算法

homework作业 | assignment | 算法代写 – 这个项目是assignment代写的代写题目

ass代做 assignment代写 代写assignment

game theories 22 homework 4 (typo J fixed) answer on eclass

Each student submits their own assignment. Discuss this assignment only within your group. You can post questions asking for question clarification on the eclass discussion forum, but do not post answers or hints or solution suggestions there or anywhere else.

  1. List all members of your discussion group, including yourself. Acknowledge that you understand that discussion of this assignment with anyone outside your group is considered plagiarism. Acknowledge any resources (except for class notes or text) you accessed when working on this assignment.
  2. Chapter 4 Exercise 4 (p 83)
  3. Chapter 4 Exercise 5

hackenbush string formulas Below, drawn on its side, is a hackenbush stringH. From the ground, its edges are respectively L, R, R, L, R. We can represent this string with binary vector(1 0 0 1 0): each 1 is an L-edge, each 0 is an R-edge.

Theas Lemma.Define binary vectorsb= (b 1 ,… , bt 1 , bt) andb= (b 1 ,… , bt 1 ) with b 1 = 1,b 2 = 0, andt2. Case 0. Ifbt= 0 then hack(b)hack(b) 1 / 2 t^1. Case 1. ifbt= 1 then hack(b)hack(b) + 1 / 2 t^1.

Example. We proved in a lecture that hack(1 0) 1 /2, so by the lemma hack(1 0 0) 1 / 2 1 / 4 1 /4, and hack(1 0 0 1) 1 /4 + 1 / 8 3 /8, and hack(1 0 0 1 0) 3 / 8 1 / 16 5 /16.

  1. Using the lemma, for each hackenbush string below, find an equivalent dyadic rational. Show your work.
  2. Using the lemma, answer Chapter 4 Exercise 11 (p 85). Show your work. You do not need to prove your answer.

Elwyns Lemma. Define binary vectorb= (b 1 ,… , bt 1 , bt) as before:b 1 = 1,b 2 = 0, andt2. Then hack(b) x, wherexis the binary fraction (0.b 3.. .bt1). Examples. hack(1 0) 0 .1 = 1 /2. hack(1 0 0) 0 .01 = 1 /4, and hack(1 0 0 1) 0 .011 = 3 /8, and hack(1 0 0 1 0) 0 .0101 = 5 /16.

  1. Use Elwyns lemma to answer question 4 again. Show your work.

proving the hackenbush string formulas The two lemmas give us the formulas. We now sketch of proof by induction ontof the lemmas. In the sketch, we use the hackenbush stringKbelow.

ForK,b= (1 0 0 1 1 0),t= 6, andb= (1 0 0 1 1). Assume both lemmas hold for all shorter hackenbush strings. By induction on Es lemma, hack(b) 0 .0111 = 7 /16. We want to show (WTS) that both lemmas hold forK. For this example, we only care about case 0 of Theas lemma, since the last edge ofKis an R-edge. For Ts lemma, we want to show that hack(b)hack(b) 1 / 2 t^1 = hack(b) 1 /32. For Es lemma, we want to show that hack(b) 0 .01101. This will follow once we have proved Ts lemma forK, since 0.01101 + 1/32 = 0.01101 + 0.00001 = 0.0111. So lets show that Ts lemma holds forK. Adding 1 /32 to both sides of the equiv- alence, WTS hack(b) + 1 / 32 hack(b). It suffices to show that the game (shown below) J= 1 /32 +hack(b) + hack(b) is a P-position.

  1. Explain in your own words why it suffices to show this.

Now lets prove thatJ is a P-position. Assume L plays first. We want to show that R wins. There are three cases: L plays first on 1 /32, onhack(b), or on hack(b).

Case 2: L plays first onhack(b). By induction,hack(b) 0 .0111. L can play on the lower L-edge, replacinghack(b) with hack((0)) 1, leaving the game

  • 1 /32 + 1 + hack(b); or on the upper L-edge, replacinghack(b) with hack(( 1)) 1 /2, leaving the game 1 /32 + 1 /2 + hack(b). L prefers to leave larger numbers, so of these two options L prefers the latter. But then R can play on the last edge of hack(b), leaving Z = 1 /32 + 1 /2 + hack(b). By induction, hack(b) (0.0111) = 7 /16. so now it is Ls turn and the game is equivalent to 1 /32 + 1 /2 + 7 / 16 1 / 32 1 /2 + 7/ 16 1 /32, so L loses.
    1. Give the argument for Case 1 (easy) and Case 3 (a bit more work). That concludes the sketch of the proof!
    2. Now that we believe that the lemmas hold, go back to gameJ. When L plays, a best move for L leaves the largest possible dyadic rationalnumber. When R plays, a best move for R leaves the smallest possibly dyadic rational. Using either of the lemmas, give all best moves for L, and all best moves forR. Explain briefly.
  1. Chapter 4 Exercise 16