search

pim-book / exercises

Solutions, discussions, and approaches to the exercises
https://pimbook.org
141 stars 7 forks source link

Chapter 4 - Number of games in double-elimination tournament #2

Open muggin opened 5 years ago

muggin commented 5 years ago

The author shows how to compute the number of games in a single-elimination tournament, using the following notation: X - set of games Y - set of players L - set of losers (players that lost games) f: X -> Y - function that given a game, returns its loser (injection - each game has unique loser)

Next, the author claims that in the case of a double-elimination tournament:

you won’t have an injection, but a so-called “double-cover” of the set of players. What I mean by double-cover is that every y ∈ Y has a preimage f^{−1}(y) = {x ∈ X : f(x) = y} of size exactly 2

However, isn't this statement false? If Y is the set of ALL players (losers and a single winner), then all, but one of the elements of Y will have a preimage of size exactly 2, while the winner will have an preimage of size 0 or 1. Am I missing something or did the author make a mistake or mean to write L instead of Y in the cited fragment?

j2kun commented 5 years ago

You are correct! If you'd like to submit an erratum for this, I'll credit you in the next edition. The submission form is at https://pimbook.org

j2kun commented 5 years ago

I do believe I clarify this in the next sentence, but the way it's worded is incorrect enough that I should fix it.

muggin commented 5 years ago

@j2kun , thanks for the response! I agree, that the next sentence aims at clarifying the idea, however, as you mentioned the wording could be better. I submitted an erratum for this yesterday.

Now another question about solving the counting problem in the double-elimination setting. I came up with an idea that loosely follows the solution of a single-elimination setting. I define a new set E and a new function g that will be bijective between X and E.

E - set of ordered pairs (loser, game), constructed as {(y, p_i) : y in Y, p_i in f^{-1}(y), where f^{-1}(y) is not empty} (it is a subset of Y x X) g: X -> E - function that given a game returns the ordered pair (loser, game) (is injective since the tuple uniquely identifies a loser per game)

The size of set E is 2*|L| (or 2*|L| + 1 giving us the bounds) since we will have |L| = |Y| - 1 losers and each of them must've lost 2 times, optionally the winner lost once. The newly defined function g is bijective, thus we can use the cardinality of set E to estimate the size of set X.

Could you comment whether there is a simpler way to approach this problem?

j2kun commented 5 years ago

This sounds like a good idea to me!