2008 iTest Problems/Problem 82

Problem

Tony’s favorite “sport” is a spectator event known as the Super Mega Ultra Galactic Thumbwrestling Championship (SMUG TWC). During the 2008 SMUG TWC, 2008 professional thumbwrestlers who have dedicated their lives to earning lithe, powerful thumbs, compete to earn the highest title of Thumbzilla. The SMUG TWC is designed so that, in the end, any set of three participants can share a banana split while telling FOXTM television reporters about a bout between some pair of the three contestants. Given that there are exactly two contestants in each bout, let m be the minimum number of bouts necessary to complete the SMUG TWC (so that the contestants can enjoy their banana splits and chat with reporters). Compute $m$ .

Solution

Lemma: The maximal number of edges of a bicolored graph of $n$ points without a monotonic triangle is $< \left \lfloor \frac{n^2}{4} \right \rfloor$ .

Proof: Template:Incomplete

It follows that the maximal number of non-bouts amongst any three people is $\frac{2008^2}{4} - 1$ , and so the minimal number of bouts to guaranteed a bout amongst any three people is ${2008 \choose 2} - \frac{2008^2}{4} = \boxed{1007012}$ . This is achieved if we partition the $2008$ thumbwrestlers into two groups of $1004$ , and have each member of a group play every other member of the group. That yields $2 {1004 \choose 2} = 1007012$ bouts.

Page

Toolbox

Search

2008 iTest Problems/Problem 82

Problem

Solution

See also