Part One: Curling. Suppose 10 teams compete in a curling competition where each team plays every...

Transcribed Image Text:

Part One: Curling. Suppose 10 teams compete in a curling competition where each team plays every other team and no ties are allowed. Officials decide that there will be two elimination rounds the first of which will eliminate all teams except for those which beat at least 7 other teams. The second elimination round will eliminate all teams which do not beat a majority of the other teams. The final competition will be among the teams which remain after the second elimination round. (A) Determine with proof the maximum number of teams which may remain after the first elimination round. (B) Determine with proof the maximum number of teams which may remain after the second elimination round. Part Two: Strong Tournaments. Recall that a directed D graph is strong if between any pair of vertices x and y, there is an x, y-path, and a y, x-path. (A) Prove that in any strong tournament T on at least 4 vertices, there exist two distinct vertices x and y such that T-x and T-y are strong. Prove or disprove whether the conclusion "T-x-y is strong" holds as well. (B-1) Let T be a tournament on n ≥ 3 vertices and let s be a vertex of T. Please prove the following statement: T is strong if and only if for every vertex t = V(T) \ {s} there is an s, t-path and a t, s-path. Is this statement true if T is a digraph (not necessarily a tournament). (B-2) Suppose you have an algorithm A that determines whether there is a path from x to y, where x and y are vertices in a digraph. Suppose A, when given a pair of vertices and a digraph D, performs this calculation with M operations in the worst case. How many operations, in the worst case, are needed to use A to determine whether D is strong using the standard definition of 'strong'? How many operation, in the worst case, are needed if the alternative definition of 'strong' proved in B-1? Part One: Curling. Suppose 10 teams compete in a curling competition where each team plays every other team and no ties are allowed. Officials decide that there will be two elimination rounds the first of which will eliminate all teams except for those which beat at least 7 other teams. The second elimination round will eliminate all teams which do not beat a majority of the other teams. The final competition will be among the teams which remain after the second elimination round. (A) Determine with proof the maximum number of teams which may remain after the first elimination round. (B) Determine with proof the maximum number of teams which may remain after the second elimination round. Part Two: Strong Tournaments. Recall that a directed D graph is strong if between any pair of vertices x and y, there is an x, y-path, and a y, x-path. (A) Prove that in any strong tournament T on at least 4 vertices, there exist two distinct vertices x and y such that T-x and T-y are strong. Prove or disprove whether the conclusion "T-x-y is strong" holds as well. (B-1) Let T be a tournament on n ≥ 3 vertices and let s be a vertex of T. Please prove the following statement: T is strong if and only if for every vertex t = V(T) \ {s} there is an s, t-path and a t, s-path. Is this statement true if T is a digraph (not necessarily a tournament). (B-2) Suppose you have an algorithm A that determines whether there is a path from x to y, where x and y are vertices in a digraph. Suppose A, when given a pair of vertices and a digraph D, performs this calculation with M operations in the worst case. How many operations, in the worst case, are needed to use A to determine whether D is strong using the standard definition of 'strong'? How many operation, in the worst case, are needed if the alternative definition of 'strong' proved in B-1?

Answer rating: 100% (QA)

Answer Part one A In first round total number of matches played will be 98765432145 So maximum 6 teams can qualify in first round such that each teams beats at least 7 teams B in second round total nu... View the full answer