Imagine there are N teams competing in a tournament, and that each team plays each of the other teams once. If a tournament were to take place, it should be demonstrated (using an example) that every team would lose to at least one other team in the tournament.

Imagine there are N teams competing in a tournament, and that each team plays each of the other teams once. If a tournament were to take place, it should be demonstrated (using an example) that every team would lose to at least one other team in the tournament.

Operations Research : Applications and Algorithms

4th Edition

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Wayne L. Winston

Chapter17: Markov Chains

Section: Chapter Questions

Problem 12RP

See similar textbooks

Similar questions

You will be given a square chess board with one queen and a number of obstacles placed on it. Determine how many squares the queen can attack. A queen is standing on an chessboard. The chess board's rows are numbered from to , going from bottom to top. Its columns are numbered from to , going from left to right. Each square is referenced by a tuple, , describing the row, , and column, , where the square is located. The queen is standing at position . In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from : There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. For example, an obstacle at location in the diagram above prevents the queen from attacking cells , , and : Given the queen's position and the locations of all the obstacles, find and print the number of…
There are four people who want to cross a rickety bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person's pace. Write the specification of an algorithm that solves the problem.
A hungry mouse wants to eat all four fruits in a maze such as the one below, in as few moves as possible.. At each turn the mouse can move any number of squares in one of the directions up, down, left or right, but it is not allowed to enter (or jump over) any walls (i.e., the black squares). Thus, the mouse moves just like a rook in chess. To eat a fruit, the mouse has to stop at that square. Assume that the maze has 4 fruits, and the size of b xh squares. 1. Give a suitable representatión of the states in this searching problem. 2. How many possible actions can the mouse perform at each move? (1.e., what is the branching factor?)
Dingyu is playing a game defined on an n X n board. Each cell (i, j) of the board (1 2, he may only go to (2, n).) The reward he earns for a move from cell C to cell D is |value of cell C – value of cell D|. The game ends when he reaches (n, n). The total reward - is the sum of the rewards for each move he makes. For example, if n = 1 2 and A = 3 the answer is 4 since he can visit (1, 1) → (1, 2) → (2, 2), and no other solution will get a higher reward. A. Write a recurrence relation to express the maximum possible reward Dingyu can achieve in traveling from cell (1, 1) to cell (n, n). Be sure to include any necessary base cases. B. State the asymptotic (big-O) running time, as a function of n, of a bottom-up dynamic programming algorithm based on your answer from the previous part. Briefly justify your answer. (You do not need to write down the algorithm itself.)
A typical roulette wheel used in a casino has 38 slots that are numbered 1,2,3,....,36,0,00, respectively. Half of the remaining slots are red and half are black. Also, half of the integers between 1 and 36 inclusive are odd, half are even, and 0 and 00 are defined to be neither odd nor even. A ball is rolled around the wheel and ends up in one of the slots; we assume each slot has equal probability of 1/38, and we are interested in the number of the slot into which the ball falls. (a)Define the Sample space S. (b)Let A = {0,00}. Give the value of P(A). (c) Let B = {14,15,17 18}. Give the value of P(B). (d) Let D = {x:x is odd}. Give the value of P(D).
Bowling involves 10 frames. Each frame starts with 10 pins. The bowler has two throws to knock all 10 pins down. The total score is the sum of pins knocked down, with some special rules. For the first 9 frames: If all 10 pins are knocked down on a frame's first throw (a "strike"), that frame's score is the previous frame plus 10 plus the next two throws. (No second throw is taken). If all 10 pins are knocked down after a frame's second throw (a "spare"), that frame's score is the previous frame plus 10 plus the next throw. In the 10th frame, if the bowler's first throw is a strike, or the first two throws yields a spare, the bowler gets a third throw. The 10th frame's score is the previous frame's score plus the pins knocked down in the 10th frame's two or three throws. Given integers represents all throws for a game, output on one line each frame's score followed by a space (and end with a newline). Note that the number of throws may be as few as 11 (strikes in first 9 frames,…
Bowling involves 10 frames. Each frame starts with 10 pins. The bowler has two throws to knock all 10 pins down. The total score is the sum of pins knocked down, with some special rules. For the first 9 frames: If all 10 pins are knocked down on a frame's first throw (a "strike"), that frame's score is the previous frame plus 10 plus the next two throws. (No second throw is taken). If all 10 pins are knocked down after a frame's second throw (a "spare"), that frame's score is the previous frame plus 10 plus the next throw. In the 10th frame, if the bowler's first throw is a strike, or the first two throws yields a spare, the bowler gets a third throw. The 10th frame's score is the previous frame's score plus the pins knocked down in the 10th frame's two or three throws. Given integers represents all throws for a game, output on one line each frame's score followed by a space (and end with a newline). Note that the number of throws may be as few as 11 (strikes in first 9 frames,…
Bowling involves 10 frames. Each frame starts with 10 pins. The bowler has two throws to knock all 10 pins down. The total score is the sum of pins knocked down, with some special rules. For the first 9 frames: If all 10 pins are knocked down on a frame's first throw (a "strike"), that frame's score is the previous frame plus 10 plus the next two throws. (No second throw is taken). If all 10 pins are knocked down after a frame's second throw (a "spare"), that frame's score is the previous frame plus 10 plus the next throw. In the 10th frame, if the bowler's first throw is a strike, or the first two throws yields a spare, the bowler gets a third throw. The 10th frame's score is the previous frame's score plus the pins knocked down in the 10th frame's two or three throws. Given integers represents all throws for a game, output on one line each frame's score followed by a space (and end with a newline). Note that the number of throws may be as few as 11 (strikes in first 9 frames,…
This problem is taken from the delightful book "Problems for Mathematicians, Young and Old" by Paul R. Halmos. Suppose that 931 tennis players want to play an elimination tournament. That means: they pair up, at random, for each round; if the number of players before the round begins is odd, one of them, chosen at random, sits out that round. The winners of each round, and the odd one who sat it out (if there was an odd one), play in the next round, till, finally, there is only one winner, the champion. What is the total number of matches to be played altogether, in all the rounds of the tournament? Your answer: Hint: This is much simpler than you think. When you see the answer you will say "of course".
We have n glasses which can hold a varying amount of liquid. We will say that glass1 is size q1 quarts and glass2 is size q2 quarts, etc. We now give you a size, say x quarts. You must give me a glass of exactly x quarts. You are allowed to fill any glass to exactly its size and to pour any liquid from one glass into another. When you pour, you either have to empty the glass you are pouring from or fill the glass you are pouring into. Can you do it?More concrete example: G1 has size 10 quarts. G2 has size 4 quarts. G3 has size 1 quart. You can get a 5 quart drink by filling G1, pouring 4 quarts from it into G2 and 1 quart of it into G1. After that, G1 has exactly 5 quarts. In the same problem, we could get 8 quarts by filling G2 twice and emptying it into G1 twice. Given This: Write an algorithm to do this and determine its complexity.
Conway's Game of Life: This is a zero person game with the following rules: (see Wikipedia for example) Any live cell with fewer than two live neighbours dies, as if by underpopulation. Any live cell with two or three live neighbours lives on to the next generation. Any live cell with more than three live neighbours dies, as if by overpopulation. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. Remember the oscillator or blinker of 3 cells. You can also find this blinker on Wikipedia. 1 21 1 2 1 21 3. 4 6 4. 6. 4 8. 9 8 9 #1 #2. #3 5. Consider now these 3 creatures at stage 1: Show how they look like in the next two stages: stage 2 and stage 3. Explain how you get the answers Creature 1 Creature 2 Creature 3 (here creature 1 is the blinker of 3 cells, horizontally; creature 2 consists of two adjacent cells, creature 3 consists of 4 adjacent cells horiztonally) ww (d) Creature 1 (10%), (e) Creature 2 (8%), (f) Creature 3 (20%)
In the game of 10-pin bowling the bowler has two attempts to knock down pins for every frame of 10-pins, and scores a point for each pin knocked down. If all the pins are knocked down with two attempts, the bowler gets a bonus - whatever score they obtain with their next bowl is doubled. If all the pins are knocked down on the 1st attempt, no 2nd attempt is allowed, and the bowler gets a bonus – whatever score they obtain on their next two bowls are doubled. A student attempts to capture this scoring system in VHDL code, a fragment of which is shown in Figure Q4. Q4 (a) Draw the state transition diagram described by the VHDL of Figure Q4. Discuss whether the VHDL of Figure Q4 correctly scores a game of 10-pin bowling. (b) elsif CLK='1' and CLK'event and UPD='1' then case present state is when throwl => frame := frame + 1; + resize (unsigned (N), 9) score := score if N = w1010" then present state score := score + resize (unsigned (N), 9) present state + resize (unsigned (N),9) if N =…