|
|
|
Author
| Message |
|---|
|
|
I agree with the total for game permutations (3^12) but I'm not clear on how you determined the other number (1296). Wouldn't there be 9 outcomes for a player's three games as white. I'm not even certain you can drop off the black games as a duplication.
If you look at each pairing between any two players, there are 9 possible outcomes for the two games, however in terms of scoring, that simplifies to five (0, 1 ... 4). Those being dropped as Richerby pointed out would be the draw-loss mirror, the draw-win mirror, win-loss mirror and finally win-loss vs draw draw equivalency. This is what Kingdave indicated as the possible outcomes before duplicates are eliminated.
So there are six pairings in a round, that would make 5^6 or 15625 possible scoring permutations (a subset of the total game permutations). Now, this gets closer to my programmatic arrival at the total scoring permutations for the entire round but I don't know how to eliminate the duplications to arrive at the assumed correct value of 1289. There must be a formula for this but perhaps it requires a more complex treatment like a matrix. Does anyone know how to mathematically express the reduction of 9 outcomes between a pair, down to 5? That might help me figure out how to get from 15625 down to 1289.
Kingdave, I'm glad you arrived at the same answer. That makes it somewhat more likely to be correct unless we actually used a similar treatment. I just coded a four-deep nested loop to add all the possible combinations using a counter. Each loop goes from 0 to 12...the possible scores for any player. Then results that are not possible are eliminated using the constraints (the counter is not incremented). The only constraints that I could think of are, first that each player can not have more then 12 points (handled by the loops themselves). Another is that only results that add to 24 points for all scores are allowed. Finally that any two players scores can not exceed 20 because they must have played each other. When the loops complete, the value of the counter should hold the total number of valid permutations only if there are no other constraints that I've missed. If your method is significantly different to what I used, it lends strength to the answer but I would still like to know the formula that should arrive at the same answer. Here is the code:
for (a=0; a<13; a+=1) {
for (b=0; b<13 b+=1) {
for (c=0; c<13; c+=1) {
for (d=0; d<13; d+=1) {
if (a+b+c+d != 24) continue;
if ((a+b > 20) or (a+c > 20) or (a+d > 20) or (b+c > 20) or (b+d > 20) or (c+d > 20)) continue;
count += 1;
}}}}
JungJoe, we were just responding to Equus' question about how many distinct results are possible in the scores from one four-player round of a tourney. It seems like there should be an easy way to calculate this so I'm feeling pretty slow myself! 
|
|
|
Blutigeroo wrote:
| I agree with the total for game permutations (3^12) but I'm not clear on how you determined the other number (1296). Wouldn't there be 9 outcomes for a player's three games as white. I'm not even certain you can drop off the black games as a duplication. |
The argument was that an outcome is a score and there are seven possible scores that a player can get from their white games. But, as I demonstrated, you can't just treat that as determining the whole score.
By the way, your program would have run a little faster if you'd coded the loops as
for (a=0; a<13; a+=1) {
for (b=0; b<=24-a; b+=1) {
for (c=0; c<=24-a-b; c+=1) {
d=24-a-b-c;
...
}}}
Though, these days, looping 28,561 times and throwing most of them away is fast enough that there's no point optimizing it unless it's going to be run many times.
I have some ideas for setting up a recurrence relation for the number of score outcomes for an n-player round-robin but it needs more thinking than I can do in this little edit box so I'll let you know if it worked, later.
Dave.
|
|
|
Very interesting. Did you get the correct result? I tried it and didn't, but I added the extra constraint:
if ((a+b+c < 12) or (a+b+d < 12) or (a+c+d < 12) or (b+c+d < 12)) continue;
The answer then agreed and the code ran about 30% faster. Then I changed the b loop to: for (b=0; b<=20-a; b+=1) {
... and halved even that time!
Good luck coming up with a formula. Somebody must know how to do it!
|
|
|
Blutigeroo wrote:
| Very interesting. Did you get the correct result? I tried it and didn't, but I added the extra constraint: [...] |
*laugh* As you can see, I didn't test it, but you get the general idea: it's more efficient to set up the loops to try fewer invalid cases. As long as you get the right answer!
Moral: when you write code, keep it simple and make sure it gets the right answer. Then, if you need to make it go faster, you can check it's still correct.
I wrote:
| I have some ideas for setting up a recurrence relation for the number of score outcomes for an n-player round-robin but it needs more thinking than I can do in this little edit box so I'll let you know if it worked, later. |
It didn't work.  My idea was to imagine that an n-player tournament happens by players 1 up to n-1 playing an (n-1)-player tournament and then each playing a pair of games against player n. I was hoping that this would let me write T(n) for the number of score outcomes of an n-player tournament, obtain an equation for T(n) in terms of T(n-1) and use that, along with the fact that T(2)=5 to compute T(n) for any n and, in particular, T(4).
This doesn't work for the same reasons as before: different score outcomes in the (n-1)-player tournament can become the same when you add the extra player and this leads to double-counting. For example, for n=2, the outcomes are 4-0, 3-1, 2-2, 1-3, 0-4. When the third player is added, one possibility is that he scores four points from his games but, depending on how the other four points are distributed between players 1 and 2, it's possible for any of the five-outcomes of their 'mini-tournament' to turn into 4-4-4 in the full tournament. To compute T(n), it's not enough to know the number of outcomes T(n-1); you also need to know what those outcomes were.
My day job is actually researching this kind of combinatorial counting problem so this is an interesting thread for me. I'm going to stick my neck out and conjecture that there's no way of computing the answer that's substantially smarter than just trying all the combinations of game results and counting up the number of different outcomes that emerge.
Dave.
|
|
|
The approaches that Blutigeroo and I used are different enough to feel good about the confirmation. B's approach is to count the number of ways 4 numbers can add up to 24, and then eliminating as many as he could think of to eliminate. So that argument establishes an upper bound, rather than the actual total. My approach generated all combinations of results of the pairwise contests, calculated the final tournament result, and counted the number of distinct values. So my approach should get the answer, not just an upper bound.
Now with regard to richerby's attempt to solve the n case, the strategy is along the lines of my approach. I have also tried to go down that path and hit the same wall: "To compute T(n), it's not enough to know the number of outcomes T(n-1); you also need to know what those outcomes were."
Here is a another strategy to try. Define B(n) to be the Blutigeroo count, where his criteria for exclusion would have to be generalized to the n case. I suspect that finding a closed form for B(n) is doable. Then prove that T(n)=B(n). We've seen that this is true for n=4. My guess is that the two are the same - the only way they'd be different is if there were some combination of small numbers that sum to the correct total but is nevertheless impossible to realize.
BTW, I redid my calculations in matlab. Here's what I get for some other values of T:
T(2) = 5
T(3) = 61
T(4) = 1289
T(5) = 39801
|
| Previous 1 2 3 4 5 Next |
|
|
|
