1. (a) (2 points) In a round-robin tennis tournament with n players, every tenni
ID: 3168308 • 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 × 1 tiles, yellow 2 x 1 tiles, blue 2 × 1 tiles, purple 3 × 1 tiles, and green 3 × 1 tiles. Let C(n) be the number of different n × 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 (c) (2 points) Let M(n) be the number of entries in an n × n matrix. Find a recurrence for M(n) and explain in words why M(n) satisfies this recurrence. (d) (2 points) Any binary string can be broken into contiguous chunks of the same character, called runs. For example, 001110100000 has a run of Os of length 2 a run of 1s of length 3 . a run of Os of length 1 . a run of 1s of length 1 a run of Os of length 5 Let B(n) be the number of length n binary strings where each run of 1s has even length. Find a recurrence for B(n) and explain in words why B(n) satisfies this recurrence. (e) (2 points) Let S(n) be the number of subsets of 11,2,..., n} having the following property: there are no three elements in the subset that are consecutive integers. Find a recurrence for S(n) and explain in words why S(n) satisfies this recurrenceExplanation / Answer
(a) We can think of a tournament with n people as a tournament with n-1 people, each playing against each other, plus one additional person who plays against each of the other n-1 people. So the recurrence is
So T(n) = T(n-1) + (n-1) with T(2) = 1 or
T(n) = T(n-1) + (n-1) with T(1) = 0
(b)
Consider the rst colored tile in the row. If it is a red 1×1 tile, then the remainder of the row is just an (n-1)×1 row of colored tiles, and the number of those is C(n-1). If the rst cell is a yellow 2×1 tile, then the remainder of the row is an (n-2)×1 row of colored tiles, and the number of those is C(n-2). We can use the same logic for each of the possible rst tiles. Then the total number of ways to ll in the (n×1) row is the number of ways starting with a red tile plus the number of ways starting with a yellow tile, etc. Therefore, the recurrence is C(n) =C(n-1) +C(n-2) + C(n-2) +C(n-3) +C(n-3)
= C(n-1) + 2C(n-2) + 2C(n-3), with C(0) = 1, C(1) = 1 C(2) = 3 or equivalently,
= C(n) = C(n-1) +C(n-2) +C(n-2) +C(n-3) +C(n-3) = C(n-1) + 2C(n-2) + 2C(n-3) ,withC(1) = 1 C(2) = 3 C(3) = 7
(c)
We can think of each n×n matrix as containing an (n-1)×(n-1) matrix in the upper left corner. The larger n×n matrix contains all the entries of the (n-1)×(n-1) grid plus an additional row and additional column. The number of entries in the rightmost column or lowest row is n+n-1 = 2n-1 additional cells, since the lower right entry is in both the last row and the last column. Therefore, the recurrence is
M(n) =M(n-1) + 2n-1, with M(1) = 1 or equivalently,
M(n) =M(n-1) + 2n-1,with M(0) = 0.
(d)
Every binary string either starts with 0 or 1. Suppose we have a binary string whereeach run of 1s has even length, and the string starts with 0. Then the remainder of the string is a length n-1 binary string where each run of 1s has even length, and there are B(n-1) such strings. Now, suppose we have a binary string where each run of 1s has even length, and the string starts with 1. Then the second bit of the string must also be 1, otherwise the string would startwith a run of length one, which is odd. After these rst two 1s, the remainder of the string is a length n-2 binary string where each run of 1s has even length, and there are B(n-2) such strings. Therefore, the recurrence is
B(n) =B(n-1) +B(n-2), with B(0) = 1, B(1) = 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)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.