My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
January 7th, 2007, 12:26 AM   #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]
tuzzi-i is offline  
 
January 7th, 2007, 05:19 AM   #2
Site Founder
 
julien's Avatar
 
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.
julien is offline  
January 19th, 2007, 12:59 AM   #3
Global Moderator
 
Joined: Dec 2006

Posts: 18,142
Thanks: 1417

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.
skipjack is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 02:52 PM
Graph theory: Linking graph characteristics and minimal cut avnerg Applied Math 0 September 18th, 2013 07:03 AM
Graph theory and number theory proglote Number Theory 3 October 30th, 2011 05:20 PM
graph theory - social networks and reverting the graph johnyjj2 Applied Math 0 December 28th, 2010 03:49 PM
Graph theory - 4 stroke graph kec11494 Applied Math 0 December 14th, 2010 07:01 PM





Copyright © 2017 My Math Forum. All rights reserved.