My Math Forum Graph Theory
 User Name Remember Me? Password

 Applied Math Applied Math Forum

 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post lubna_mira Applied Math 0 January 12th, 2014 01:52 PM avnerg Applied Math 0 September 18th, 2013 06:03 AM proglote Number Theory 3 October 30th, 2011 04:20 PM johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM kec11494 Applied Math 0 December 14th, 2010 06:01 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top