My Math Forum  

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

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
January 6th, 2007, 11:26 PM   #1
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, 04: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 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.
skipjack is offline  

  My Math Forum > College Math Forum > Applied Math

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

Copyright © 2018 My Math Forum. All rights reserved.