Out of all "possible" final scores (0<R<3*n) for a team, participating in N games, how many final results cannot be achieved?
| See The Solution | Submitted by Ady TZIDON |
| Rating: 4.0000 (1 votes) |
Solution a different way
|
 | Comment 4 of 5 |  |
I arrived at the same answer as others who posted earlier, but by a different route.
Certainly a team can get the maximum score (3*n) if it wins all its games. Now consider whether a team that scored some number of points P can also reach a score of P-1.
If a team had a draw while reaching P points, converting that draw to a loss reaches P-1. If a team had both a win and a loss, converting that pair to two draws also converts the total to P-1. No other transformations resulting in a net loss of a point.
A score is not reachable from the next higher score, then, if both of these routes are blocked. That in turn requires both that the higher score have no draws (to block the first path) AND that it not have both a win and a loss (to block the second path.) The only configurations that match these requirements are when a team has all wins or it has all losses. All others have either a draw or they have both a win and a loss. The case of all losses is of course the minimum score, so the fact that a lower one can't be derived is good. The other case yields the solution that a score of 3*n-1 can't be reached -- the only such score.
To be fair, I've been a bit glib in imagining the scores counting down all the way to zero as if each score can be derived from its predecessor. That's not strictly true unless you add in one more piece -- that you can always turn a win and a pair of losses into a trio of draws (or vice versa). Without such exchanges, a specific collection of wins, losses, and draws might not be convertable to one with one fewer total points, although it would still be true that there will always be SOME set of results with score P (>0, != 3*n) that can be tranformed into one with score P-1, which is enough to show that the P-1 score is possible.
Personally, I think Jer's solution is cleaner, but it's sometimes nice to see the cat skinned several ways.
Certainly a team can get the maximum score (3*n) if it wins all its games. Now consider whether a team that scored some number of points P can also reach a score of P-1.
If a team had a draw while reaching P points, converting that draw to a loss reaches P-1. If a team had both a win and a loss, converting that pair to two draws also converts the total to P-1. No other transformations resulting in a net loss of a point.
A score is not reachable from the next higher score, then, if both of these routes are blocked. That in turn requires both that the higher score have no draws (to block the first path) AND that it not have both a win and a loss (to block the second path.) The only configurations that match these requirements are when a team has all wins or it has all losses. All others have either a draw or they have both a win and a loss. The case of all losses is of course the minimum score, so the fact that a lower one can't be derived is good. The other case yields the solution that a score of 3*n-1 can't be reached -- the only such score.
To be fair, I've been a bit glib in imagining the scores counting down all the way to zero as if each score can be derived from its predecessor. That's not strictly true unless you add in one more piece -- that you can always turn a win and a pair of losses into a trio of draws (or vice versa). Without such exchanges, a specific collection of wins, losses, and draws might not be convertable to one with one fewer total points, although it would still be true that there will always be SOME set of results with score P (>0, != 3*n) that can be tranformed into one with score P-1, which is enough to show that the P-1 score is possible.
Personally, I think Jer's solution is cleaner, but it's sometimes nice to see the cat skinned several ways.
| Posted by Paul on 2013-04-03 19:31:05 |
