1. (a) (2 points) In a round-robin tennis tournament with n players, every tenni
ID: 3123530 • Letter: 1
Question
1. (a) (2 points) In a round-robin tennis tournament with n players, every tennis player plays against every other player. Let T(n) be the total number of tennis matches taking place among the n players. Find a recurrence for T(n) and explain in words why T(n) satisfies this recurrence. (b) (2 points In a board game, players must place colored tiles in a single row. There are red 1 x 1 tiles, yellow 2 x 1 tiles, blue 2 x 1 tiles, purple 3 x 1 tiles, and green 3 x 1 tiles. Let C(n) be the number of different n x 1 colored rows that can be created using these tiles. Find a recurrence for C(n) and explain in words why C(n) satisfies this recurrence.Explanation / Answer
(According to Chegg policy only four questions will be answered. Please post the remaining in a separate question)
(a) Among the n players, let us choose one player.
This player plays all other players in n-1 games.
Not counting his games, the remaining n-1 players play among themselves which is another round robin tournament with n-1 players.
Similarly, if we select next player, he plays n-2 games with the remaining playing a round robin tournament of n-2 players and so on.
So T(n) = T(n-1) + n-1
(c) The matrix has n rows and n columns.
Suppose we fix the first column and first row.
There are n elements in the first row and in the first column.
However, the first element is both in the first row and first column.
So there are a total of n + n -1 = 2n-1 elements in the first row and first column.
The remaining elements form an n-1xn-1 matrix. The procedure can be used recursively.
So M(n) = M(n-1) + 2n -1
(e) If we remove n from the set {1,2,3........n}, we will have the set {1,2,3.......n-1}
This will have the same number of subsets with no three consecutive integers as n except for those that have both n-1 and n-2 in them as n,n-1,n-2 form three consecutive integers.So only one of them can be in.
The number of subsets having both n-1 and n-2 with the conditions = S(n-3).
Futher we can construct new subsets by appending n to each n-1 element subset. There will be 2S(n-1) such subsets.
Thus S(n) = 2S(n-1) - S(n-3)
(b) Notice that the gcd of 1,2,3 is 6.
We can thus break down each process as
Form a row of (n-6)x1 tiles first
Join a row of 6x1 tiles to this row
So C(n) = C(n-6) * C(6)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.