Difference between revisions of "2008 iTest Problems/Problem 82"
m |
|||
| Line 15: | Line 15: | ||
Proof: | Proof: | ||
| − | + | This can be obtained directly from Turan's theorem in graph theory | |
<!-- Use extremal, one point has at least <math>n/2</math> edges, etc --> | <!-- Use extremal, one point has at least <math>n/2</math> edges, etc --> | ||
Revision as of 04:30, 14 November 2024
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 
.
Solution
Lemma: The maximal number of edges of a bicolored graph of 
points without a monotonic triangle is 
.
Proof:
This can be obtained directly from Turan's theorem in graph theory
It follows that the maximal number of non-bouts amongst any three people is 
, and so the minimal number of bouts to guaranteed a bout amongst any three people is 
. This is achieved if we partition the 
thumbwrestlers into two groups of 
, and have each member of a group play every other member of the group. That yields 
bouts.
