January 6th, 2007, 11:26 PM  #1 
Newbie Joined: Dec 2006 Posts: 9 Thanks: 0  Graph Theory
Four schools P, Q, R and S each has team A and team B in a tournament. The teams from the same school do not play against each other. At certain stage of the tournament, the numbers of games played by the teams, except team A of school P, are distinct. Determine the number of games played by team B of school P.[/i]

January 7th, 2007, 04:19 AM  #2 
Site Founder Joined: Nov 2006 From: France Posts: 824 Thanks: 7 
Since the numbers of the games played by the 7 remaining teams (D) are pairwise disjoint, and since those numbers must be elements of the set {0,1,...,6}, they are exactly 0,1,...,6, each of these numbers being represented exactly once. In order to understand the following, draw a graph with vertices the teams and edges the games played. Is it possible that team PB hasn't played yet ? No, because otherwise no team of D has played exactly 6 games. Without loss of generality, we can assume that team QA hasn't played yet. In this situation, team QB will be the one who has played 6 games at this point (why?). Note that we can now infer that RA played exactly once. Is it possible that team PB has played exactly once ? No, because otherwise no team of D has played exactly 5 games (why?). Without loss of generality, we can assume that team RA has played exactly 5 games. Has PB played exactly twice ? No. Otherwise no team of D will have played exactly 4 games (why?). Now you can assume SA played exactly 4 games; therefore, SB has played exactly twice and PB exactly 3 times. The answer to the problem is three. Note that there is just no way to solve this problem without a pencil and paper, but if you use those, this becomes easy. 
January 18th, 2007, 11:59 PM  #3 
Global Moderator Joined: Dec 2006 Posts: 19,722 Thanks: 1807 
No graph is needed. Your third paragraph (minus its last sentence, which didn't belong) can be reworded to show that some pair of teams other than PB played the lowest and highest numbers (of games) not yet allocated. Now you simply repeat that argument twice. Thus you've shown PB didn't play 0 or 6 games, 1 or 5 games, or 2 or 4 games. So it played 3 games. 

Tags 
graph, theory 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A graph problem in graph theory!  lubna_mira  Applied Math  0  January 12th, 2014 01:52 PM 
Graph theory: Linking graph characteristics and minimal cut  avnerg  Applied Math  0  September 18th, 2013 06:03 AM 
Graph theory and number theory  proglote  Number Theory  3  October 30th, 2011 04:20 PM 
graph theory  social networks and reverting the graph  johnyjj2  Applied Math  0  December 28th, 2010 02:49 PM 
Graph theory  4 stroke graph  kec11494  Applied Math  0  December 14th, 2010 06:01 PM 