Two players play a game where they start with a row of n piles of varied...

Two players play a game where they start with a row of n piles of varied amounts of money. The players take turns and in each turn a player can pocket either the money in the first pile or the last pile in the row of piles that remains. Design an efficient algorithm (using dynamic programming), which on any given sequence of amounts, determines the maximum amount of money that player 1 can win.

If n is even, prove that player 1 wins at least half the money available. If n is odd, player 1 actually gets one more pile than player 2. In spite of that, show with a simple example that player 1 can be left with far less than half the total amount.

Note: you can write the algorithm either in plain English or in pseudocode.

Solutions

Expert Solution

PLEASE GIVE THUMBS UP.

venereology answered 1 month ago

Next > < Previous

Related Solutions

1. Consider the following game. There are two piles of matches and two players. The game...

1. Consider the following game. There are two piles of matches and two players. The game starts with Player 1 and thereafter the players take turns. When it is a player's turn, she can remove any number of matches from either pile. Each player is required to remove some number of matches if either pile has matches remaining, and can only remove matches from one pile at a time. Whichever player removes the last match wins the game. Winning gives...

Consider the Stage Game below, and consider the repeated game where players play twice (T =...

Consider the Stage Game below, and consider the repeated game where players play twice (T = 2). Payoﬀs for each agent are simply period one plus period two payoﬀs. L C R T 6,6 0,7 1,2 M 7,0 1,1 2,0 B 2,1 0,1 3,3 (a) Do any strategies dominate any other? (b) What are the two NE of the Stage Game? What is the diﬀerence between the two? (c) Call the TL strategy proﬁle (1 plays T, 2 plays L)...

Two players A and B play a game of dice . They roll a pair of...

Two players A and B play a game of dice . They roll a pair of dice alternately . The player who rolls 7 first wins . If A starts then find the probability of B winning the game ?

Design and implement a Python program which will allow two players to play the game of...

Design and implement a Python program which will allow two players to play the game of Tic-Tac-Toe in a 4x4 grid! X | O | X | O -------------- O | O | X | O -------------- X | X | O | X -------------- X | X | O | X The rules for this game is the same as the classic, 3x3, game – Each cell can hold one of the following three strings: "X", "O", or "...

Einstein and Lorentz, being avid tennis players, play a fast-paced game on a court where they...

Einstein and Lorentz, being avid tennis players, play a fast-paced game on a court where they stand 20.0 m from each other. Being very skilled players, they play without a net. The tennis ball has mass 0.0580 kg. You can ignore gravity and assume that the ball travels parallel to the ground as it travels between the two players. Unless otherwise specified, all measurements are made by the two men. Lorentz serves the ball at 80m/s. Einstein slams a return...

Consider the situation below where two players are engaged in a game of chicken. In this...

Consider the situation below where two players are engaged in a game of chicken. In this game, both players drive their cars at each other and each player can choose to either drive straight, or swerve. If both cars drive straight, they will crash in to one another, causing damage to both vehicles. If one car goes straight, while the other swerves, the player that swerves is a "chicken" while the other player is respected for their bravery. If both...

Two players A and B play a dice game with a 6-face fair dice. Player A...

Two players A and B play a dice game with a 6-face fair dice. Player A is only allowed to roll the dice once. Player B is allowed to roll the dice maximally twice (that is, Player B can decide whether or not she or he would roll the dice again after seeing the value of the first roll). If the player with the larger final value of the dice wins, what is the maximal probability for Player B to...

I am using C++ Write a program that allows two players to play a game of...

I am using C++ Write a program that allows two players to play a game of tic-tac-toe. Use a two-dimensional char array with three rows and three columns as the game board. Each element of the array should be initialized with an asterisk (*). The program should run a loop that does the following: Displays the contents of the board array. Allows player 1 to select a location on the board for an X. The program should ask the user...

Write a program that allows two players to play a game of tic-tac-toe. Use a two-dimensional...

Write a program that allows two players to play a game of tic-tac-toe. Use a two-dimensional char array with three rows and three columns as the game board. Each element of the array should be initialized with an asterisk (*). The program should run a loop that does the following: Displays the contents of the board array. Allows player 1 to select a location on the board for an X. The program should ask the user to enter the row...

PYTHON: Write the code to play a card game called Battle. Two players each have a...

PYTHON: Write the code to play a card game called Battle. Two players each have a card deck consisting of the following cards: two, three, four, … jack, queen, king, ace, in increasing order. One card deck could be represented by a list such as: cardsPlayer1 = ["two", "three", "four"..."jack", "queen", "king", "ace"] Both players have a card randomly selected. When a card is selected, remove it from the player’s deck. The player that plays the higher of the two...

Subjects