wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> soccer tournament
        
(Message started by: black_death on May 6^th, 2008, 12:06am)

Title: soccer tournament
Post by black_death on May 6^th, 2008, 12:06am

In a soccer tournament n teams play against one another exactly once. The win fetches 3 points, draw 1 each and loss 0. After all the matches were played, it was noticed that the top team had unique number of maximum points and unique least number of wins (that is all other teams win more matches than the top team). What can be the minimum possible value of n ? (n>1)

Title: Re: soccer tournament
Post by rmsgrey on May 6^th, 2008, 9:45am

on 05/06/08 at 00:06:14, black_death wrote:

Title: Re: soccer tournament
Post by ThudanBlunder on May 6^th, 2008, 11:33am

on 05/06/08 at 09:45:43, rmsgrey wrote:

How do they play 'exactly once'? :P

Title: Re: soccer tournament
Post by Qaster Qof Qeverything Q42 on May 6^th, 2008, 1:05pm

[hide] 2 [/hide]

Title: Re: soccer tournament
Post by black_death on May 6^th, 2008, 6:57pm

i think the question should be clarified further .... minimum number of wins mean that all the team win more matches than the top team

Title: Re: soccer tournament
Post by rmsgrey on May 7^th, 2008, 5:10am

on 05/06/08 at 11:33:51, ThudanBlunder wrote:

How do they play 'exactly once'? :P

They play each and every other team exactly once each

Title: Re: soccer tournament
Post by FiBsTeR on May 7^th, 2008, 2:40pm

Why not zero teams?

I say that each team plays each other exactly once, for, if not, there would exist some team that played another team less than or greater than once, which contradicts the fact that there are no teams.

I say that the top team has the maximum number of points and the least number of wins, for, if not, there would exist either a team with more points or a team with less wins, which contradicts the fact that there are no teams.

Thus having zero teams fulfills all the requirements, and there clearly can't be a negative number of teams, so zero is the minimum. :)

Title: Re: soccer tournament
Post by ThudanBlunder on May 7^th, 2008, 2:53pm

on 05/07/08 at 14:40:09, FiBsTeR wrote:

...and there clearly can't be a negative number of teams.

Why not? I don't think, and I'm sure rmsgrey will back me up here, this has been ruled out in the problem statement. ::)

And who said the number of teams must be real?
For example, there might be i teams. In which case we would have http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/frakcu.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/frakn.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/frakr.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/frake.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/fraka.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/frakcl.gif Tournament.

Title: Re: soccer tournament
Post by black_death on May 7^th, 2008, 6:47pm

he he guys ..... ok the number of teams are greater than 1 ;D

Title: Re: soccer tournament
Post by Qaster Qof Qeverything Q42 on May 8^th, 2008, 4:10am

on 05/06/08 at 13:05:50, Qaster Qof Qeverything Q42 wrote:

[hide] 2 [/hide]

ahem

Title: Re: soccer tournament
Post by rmsgrey on May 8^th, 2008, 5:28am

2 teams is impossible.

With 1 match, either it's a draw, in which case there's no unique winning team, or one team wins, in which case the unique winning team has more wins than some other team...

Title: Re: soccer tournament
Post by ThudanBlunder on May 9^th, 2008, 9:47am

But getting real,
let top team win w times.
Then top team has (n-1) - w draws.

Now if top team has k wins less than another team then
top team must have at least 3k+1 more draws than the other team in order to end up with more points.
More draws requires more matches, which require more teams in the tournament.
So assume minimum is achieved when top team has just one less win than every other team.
Then top team must draw at least 4 more games than every other team, in order to end up with more points.
And some other teams have drawn at least one game (eg. with top team).
So
n - 1 - w > 4
n > w + 5 .........................................(1)

And if all except top team score w+1 wins
then total number of wins
= total number of losses
= n(w+1) - 1

And top team has n - 1 - w draws.
So considering total number of games we get
2n(w+1) - 2 + 2(n-1-w) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n(n-1)
or
n² - (2w+5)n + 2w + 4 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/geqslant.gif 0
(n - 1)(n - 2w - 4) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/geqslant.gif 0
And n = 1 gives us rsmgrey's deep observation. :)

Otherwise n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/geqslant.gif 2w + 4
Putting w = 1 gives n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/geqslant.gif 6
But n > 6 by (1)

Finally, putting w = 2 gives n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/geqslant.gif 8

Team 1: W - W - D - D - D - D - D (11 points)
Team 2: W - W - W - D - L - L - L (10 points)
Team 3: W - W - W - D - L - L - L (10 points)
Team 4: W - W - W - D - L - L - L (10 points)
Team 5: W - W - W - D - L - L - L (10 points)
Team 6: W - W - W - D - L - L - L (10 points)
Team 7: W - W - W - L - L - L - L ( 9 points)
Team 8: W - W - W - L - L - L - L ( 9 points)

It's nice to get one all to myself. And I'm glad I managed to finish it before Hippo arrived. :)

Title: Re: soccer tournament
Post by black_death on May 9^th, 2008, 11:57am

Perfect TB :D

Title: Re: soccer tournament
Post by Hippo on May 9^th, 2008, 12:10pm

on 05/09/08 at 09:47:16, ThudanBlunder wrote:

Team 1: W - W - D - D - D - D - D (11 points)
Team 2: W - W - W - D - L - L - L (10 points)
Team 3: W - W - W - D - L - L - L (10 points)
Team 4: W - W - W - D - L - L - L (10 points)
Team 5: W - W - W - D - L - L - L (10 points)
Team 6: W - W - W - D - L - L - L (10 points)
Team 7: W - W - W - L - L - L - L (10 points)
Team 8: W - W - W - L - L - L - L (10 points)

Except the number of points of last two teams

on 05/09/08 at 09:47:16, ThudanBlunder wrote:

It's nice to get one all to myself. And I'm glad I managed to finish it before Hippo arrived. :)

:) I have resign to write answers (and even to solve) such an amount of riddles ... at least few first days

Title: Re: soccer tournament
Post by ThudanBlunder on May 9^th, 2008, 12:37pm

on 05/09/08 at 12:10:56, Hippo wrote:

Except the number of points of last two teams

Thanks. Now corrected.

on 05/09/08 at 11:57:03, black_death wrote:

Perfect TB :D

There is a small step missing.
I haven't yet proved that n=7, w=1 is not possible (and it doesn't seem to be - it leaves too many draws).

Title: Re: soccer tournament
Post by ThudanBlunder on May 10^th, 2008, 6:38pm

on 05/09/08 at 12:37:40, ThudanBlunder wrote:

There is a small step missing.
I haven't yet proved that n=7, w=1 is not possible (and it doesn't seem to be - it leaves too many draws).

OK, I think I have it.

The top team draws n - 1 - w games
and they draw at least 4 more games than every other team.
So no other team can draw more than n - 5 - w games.
So the total number of draws (times 2) must be less than or equal to
(n - 1)(n - 5 - w) + (n - 1 - w)
= n(n - 5 - w) + 4

And total number of draws (times 2) = total number of games (times 2) - total number of wins - total number of losses

So we have
n(n - 1) - 2n(w + 1) + 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leqslant.gif n(n - 5 - w) + 4
And this simplifies to
(2 - w)n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/leqslant.gif 2
And we know that n > w + 5 or n = 1
When n = 1, w = 0, trivially.
And n > w + 5 leads to
(2 - w)(w + 5) < 2
and so w http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/geqslant.gif 2
QED