Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 06 Jun '07 14:10
    In a chess tournamet, every participant played with each other exactly once.
    Prove: It is not possible that for every player P, the sum of points of the players who beat P is greater then the sum of points of the players who were beaten by P.
  2. Standard member EinsteinMind
    Seeker
    06 Jun '07 14:33 / 1 edit
    Originally posted by David113
    In a chess tournamet, every participant played with each other exactly once.
    Prove: It is not possible that for every player P, the sum of points of the players who beat P is greater then the sum of points of the players who were beaten by P.
    is P one player?

    of course. that's easy to prove. just don't know how to explain it.
  3. Standard member PBE6
    Bananarama
    07 Jun '07 15:34
    Originally posted by David113
    In a chess tournamet, every participant played with each other exactly once.
    Prove: It is not possible that for every player P, the sum of points of the players who beat P is greater then the sum of points of the players who were beaten by P.
    What if one of the players is undefeated? Does that count as 0 for the sum of the points of the players who "beat" P?
  4. 07 Jun '07 19:06
    What if there are only 2 participants?
  5. Standard member EinsteinMind
    Seeker
    08 Jun '07 06:01
    Originally posted by David113
    In a chess tournamet, every participant played with each other exactly once.
    Prove: It is not possible that for every player P, the sum of points of the players who beat P is greater then the sum of points of the players who were beaten by P.
    You are correct.

    And I can prove it too!!!

    Say that you have 4 players in a tourney; P,Q, R, and S.

    It stands to reason that, since everyone plays everyone else,

    P vs. Q 1-0
    Q vs. R 0-1
    R vs. S 0-1
    P vs. R 0-1
    P vs. S 0-1
    Q vs. S 1-0

    correct?

    P can win one and lose two, giving one loss to Q and a win to R and S.
    Q can win 1 and lose two, giving two more wins, one to R and one to S.
    Then R and S must have each lost one, which are the wins of P and the match of the two winners R and S (one of them had to lose right?)


    ...........P Q R S
    wins.....1.1..2.2
    losses..2.2..1.1

    From these results of an edxample 4-player tourney, only half the players were able to lose more than win. As it is with most other examples will show you as well.

    This is my example to prove David113's theory, which is valid.

    Thank you. Thank you very much.
  6. Standard member EinsteinMind
    Seeker
    09 Jun '07 03:46
    Originally posted by EinsteinMind
    You are correct.

    And I can prove it too!!!

    Say that you have 4 players in a tourney; P,Q, R, and S.

    It stands to reason that, since everyone plays everyone else,

    P vs. Q 1-0
    Q vs. R 0-1
    R vs. S 0-1
    P vs. R 0-1
    P vs. S 0-1
    Q vs. S 1-0

    correct?

    P can win one and lose two, giving one loss to Q and a win to R and S.
    Q can win 1 and l ...[text shortened]... is is my example to prove David113's theory, which is valid.

    Thank you. Thank you very much.
    sorry for the double post guys. need to give a more detailed explanation of proving his theory.

    you see, in any tournament, the points won has to equal the points lost.

    From this we can derive a simple equation: w=l (win points equals loss points.)

    Now he wants me to prove that It is impossible that losses are greater than wins, or this equation: w < l

    since, in the equation w < l that we can assume that w =/= l correct?

    And, since w =/= l in his proof, and since w = l is basically a law of chess tournaments, every player cannot lose more than they can win, only some.
  7. 18 Jun '07 14:16 / 1 edit
    Originally posted by EinsteinMind
    sorry for the double post guys. need to give a more detailed explanation of proving his theory.

    you see, in any tournament, the points won has to equal the points lost.

    From this we can derive a simple equation: w=l (win points equals loss points.)

    Now he wants me to prove that It is impossible that losses are greater than wins, or this equatio ...[text shortened]... asically a law of chess tournaments, every player cannot lose more than they can win, only some.
    I don't think you are being asked to prove that losses are greater than wins, well at least I can't understand your logic which doesn't surprise me if you check out the hat thread. You are being asked to prove that in a round robin tournament (X) with a certain number (n) of players there exists a clear winner (A) and that the maximum cumulative points total of those players who defeated (A) is less than the minimum number of the cumulative points total of those players who lost to (A).

    If there is 1 player in the tourney then it's absurd. If 2 players then the winner can't lose a game and still win, if 3 players each player plays two games so yet again you can't lose a game and be a clear winner so we are only being asked to prove this when n > 3.

    Example: 8 player round robin.

    It's an all-play-all so the number of games shall be 7+6+5+4 etc which can be written as n(n-1)/2 (Like the triangular number series only the n value isn't counted: we start from n-1, and hence n(n-1)/2 and not n(n+1)/2.) So in an eight player tourney there will be 28 games and a total of 28 points available. If we take the minimum number of points needed by A (in order to maximise the number of players that beat A, and their cumulative total) we find that A needs 4 points to be outright winner (we don't count draws because they will merely take a player out of the loop.)

    If A wins 4 games (n/2) then A had 3 losses therefore there are three players in the group of players who beat A (n/2-1). The maximum that each member of this group can score and still be a runner-up is a half point less than the score by the winner, therefore 3.5 (n/2-0.5).

    The total points that are available is 28 so if we subtract the winner's points we have 24. The maximum that the group of players who beat A can muster is 3.5*3 ([n/2-1][n/2-0.5]) =10.5. If we subtract 10.5 from the 24 we are left with 13.5 therefore the group of players that lost to A have a higher cumulative total than those who won against A.

    A tourney with n players:

    For a tourney with n players there are n(n-1)/2 games available and n(n-1)/2 total points. If we subtract the wins of player A we get:

    n[2]/2-n/2-n/2 [n[2] means n squared]
    = n[2]/2 - n

    The maximum amount of points won by the group of players who beat A is:

    (n/2-1)(n/2-1/2)
    =n[2]/4 - 3/4n + 1/2

    We must prove that n[2]/2-n is more than double n[2]/4-3/4n+1/2

    We know that n[2]/2 is double n[2]/4 so we only need to show that n is greater than 3/4n +1/2.

    But we said at the start that we are proving this for values of n>3 and it's clear that even substituting for the lowest value of n (that is 4) we get 4 > 3+ 1/2.

    I am crap at maths so excuse the laboured explanation I am probably missing something mundane in the earlier explanations. I am not sure if this explanation is exactly the same for odd numbers of participants.
  8. 18 Jun '07 15:10
    OK, an example of the sort of thing the problem is looking at.

    I set up a seven player round robin (1 game each).

    The scores are as follows (W-L-D):

    5-1-0 - 5 points
    3-2-1 - 3.5 points
    3-3-0 - 3 points
    3-3-0 - 3 points
    2-2-2 - 3 points
    2-3-1 - 2.5 points
    1-5-0 - 1 point

    So let's examine the sum of the points each gave to winners, and the sum they give to losers.

    5-1-0 +25.0 vs losers, + 5.0 vs winners
    3-2-1 +10.5 vs losers, + 7.0 vs winners
    3-3-0 + 9.0 vs losers, + 9.0 vs winners
    3-3-0 + 9.0 vs losers, + 9.0 vs winners
    2-2-2 + 6.0 vs losers, + 6.0 vs winners
    2-3-1 + 5.0 vs losers, + 7.5 vs winners
    1-5-0 + 1.0 vs losers, + 5.0 vs winners

    Now, if you were to look at all the non-drawn games (19 in this case), and sum up the end points of the winners and sum up the end points of the losers, you would find 65.5 points on the winners side, and 48.5 points on the loser's side.

    Now the proposition is as follows: Suppose we look at the number of points of the people who won against a player, and compare it to the number of points of those that lost to them. For at least one person, the points won against is equal to or higher than the points lost against.

    I think the above poster has the right idea (have to look at it closer later) in thinking that this person would most likely be the winner of the tournament.
  9. Standard member EinsteinMind
    Seeker
    23 Jun '07 05:36
    Originally posted by geepamoogle
    OK, an example of the sort of thing the problem is looking at.

    I set up a seven player round robin (1 game each).

    The scores are as follows (W-L-D):

    5-1-0 - 5 points
    3-2-1 - 3.5 points
    3-3-0 - 3 points
    3-3-0 - 3 points
    2-2-2 - 3 points
    2-3-1 - 2.5 points
    1-5-0 - 1 point

    So let's examine the sum of the points each gave to winners, and th ...[text shortened]... closer later) in thinking that this person would most likely be the winner of the tournament.
    I dont think that's what David113 was asking. I think he specifically said (and I quote)

    "In a chess tournament, every participant played with each other exactly once.
    Prove: It is not possible that for every player P, the sum of points of the players who beat P is greater then the sum of points of the players who were beaten by P."

    This refers to every player in the tournament, not just to the people who could possibly do it. Every player cannot win more points than they can lose. For at least one person, yes, it can happen, but not EVERY person or so quoted "Every player defined as P" can get more points won than lost.
  10. Standard member EinsteinMind
    Seeker
    23 Jun '07 07:16 / 2 edits
    Originally posted by demonseed
    I don't think you are being asked to prove that losses are greater than wins, well at least I can't understand your logic which doesn't surprise me if you check out the hat thread. You are being asked to prove that in a round robin tournament (X) with a certain number (n) of players there exists a clear winner (A) and that the maximum cumulative poi am not sure if this explanation is exactly the same for odd numbers of participants.
    good point actually. my logic fell apart in the face of that second post.

    But the first post makes sense...

    It was what he was asking for. The fact that every person in a chess tourney cannot win more points than they lost. There must be at least one person who loses more than wins. even if there are only 2 participants, one must lose.

    Edit: FOUND IT!!! THE ONE EXCEPTION TO DAVID113'S THEORY!!!!!

    A two participant match has a draw. now wins for both parties are equal and losses do not exceed wins.

    This kind of exception scenario can only happen when everyone in a chess tournament facing everyone else has a draw with everyone else. then wins and losses of all players are all equal; therefore losses do not exceed wins.


    But how often is everyone at a chess tourney going to draw?? and when did chess tournaments have only two participants? This is how improbable the exception is.
  11. 23 Jun '07 13:36
    Originally posted by EinsteinMind
    good point actually. my logic fell apart in the face of that second post.

    But the first post makes sense...

    It was what he was asking for. The fact that every person in a chess tourney cannot win more points than they lost. There must be at least one person who loses more than wins. even if there are only 2 participants, one must lose.

    Edit: F ...[text shortened]... when did chess tournaments have only two participants? This is how improbable the exception is.
    This is not an exception. I cover it in my post.

    In a two player tourney the winner cannot be an outright winner and lose a game, nor can the winner do so in a three player tourney so David's problem only relates to 4 player tourneys and beyond.
  12. Standard member EinsteinMind
    Seeker
    23 Jun '07 17:15
    Originally posted by demonseed
    This is not an exception. I cover it in my post.

    In a two player tourney the winner cannot be an outright winner and lose a game, nor can the winner do so in a three player tourney so David's problem only relates to 4 player tourneys and beyond.
    exactly. and most chess tournaments will have more than four participants.

    (non-rhetorical question)
    How often have you seen chess tourneys with two or three participants???

    I've never seen it happen.