0
$\begingroup$

So I asked a question here, which asks how many ways there are to score 7 points in 7 chess tournament games using the system on lichess.org, outlined both here and in the original question.

That was solved fairly quickly, so I thought that I would "up the ante" a little bit with a harder question:


For tournament games played $n$, how many ways are there to score $n$ tournaments points? Order does not matter. A win and a loss in two games is the same as a loss and a win.The accepted answer should (if possible) give a rule that is correct as $n$ approaches infinity, and also explain the exceptions that likely occur at "low" values of $n$ (I'm guessing around five or lower). There are two ways to get the number 2 - a win-streak draw or a normal win. These may be treated as the same thing in permutations.

$\endgroup$
  • $\begingroup$ What if anything is missing from my answer? (E.g., would you like me to edit into it some ugly Python code that verifies that its formulae get the same results as a more brute-force calculation does?) $\endgroup$ – Gareth McCaughan Mar 10 at 2:55
3
$\begingroup$

I assume we're using the same convention as in the earlier question, and ignoring order. So we're looking for partitions of $n$ into numbers from {1,2,3,4,5} with the restriction that we can't have a 4 or 5 unless we also have at least two from {2,3}.

[EDITED to add:] In what follows I assume that we care about the patterns of scores rather than how they were obtained. This matters only in one way: a 2 can be either a win when you aren't on a winning streak, or a draw when you are (which necessarily ends that streak). I neglected that because I forgot about it, but if I'd remembered I would probably still have neglected it, because I think dealing with it "properly" is going to make what's already a messy calculation with a messy answer downright intolerable. [EDITED again to add:] OP has now very obligingly edited the question to make this explicitly permitted.

It's probably best to think of this as the number of partitions of $n$ into numbers from {1,2,3,4,5} unrestrictedly, minus the number of partitions that use at most one 2 or 3 and at least one 4 or 5. Then split that correction term up as follows: no 2 or 3, but at least one 4 or 5 (= partitions into {1,4,5} minus partitions into {1}); just one 2, but at least one 4 or 5 (= same thing but for $n-2$ instead of $n$); just one 3, but at least one 4 or 5 (= same thing but for $n-3$).

In other words, we want (with what I hope is obvious notation) $p_{12345}(n)-(p_{145}(n)-p_1(n))-(p_{145}(n-2)-p_1(n-2))-(p_{145}(n-3)-p_1(n-3))$. Obviously $p_1(n)=1$ provided $n\geq0$, and $p_{\textrm{anything}}(\textrm{negative})=0$, so we can write this as $p_{12345}(n)-p_{145}(n)-p_{145}(n-2)-p_{145}(n-3)+[n\geq0]+[n\geq2]+[n\geq3]$ where $[P]$ means 1 if $P$ and 0 if not-$P$.

Now, this stuff is not trivial. It turns out, at least according to one book on the subject, that $p_{12345}(n)$ is the nearest integer to ...

$\frac{(n+8)\left(n^3+22n^2+44n+180\left\lfloor\frac{n}2\right\rfloor+248\right)}{2880}$

which doesn't entirely inspire me with optimism about there being a very nice formula for $p_{145}(n)$, but let's see. $p_{145}(n)$ is the number of ways to make $n$ out of 1s, 4s, and 5s. The generating function $\sum p_{145}(n)q^n$ equals $\frac1{(1-q)(1-q^4)(1-q^5)}$. We can turn that into partial fractions and play around a bit, and if I haven't messed it up -- you really don't want to see the details -- it turns out that $p_{145}(n)$ is usually the nearest integer to $\frac{(n+5)^2}{40}$, except that if the remainder on dividing $n$ by 20 is one of {3,5,7} we need to add {-1,+1,-1} respectively.

OK. So, putting all this together, if I haven't messed up my calculations, then to find the number of ways to score $n$ in $n$ games you do this:

First of all, find the nearest integer to $\frac{(n+8)\left(n^3+22n^2+44n+180\left\lfloor\frac{n}2\right\rfloor+248\right)}{2880}$. If $n$ is {0,1,2,more} then add {1,1,2,3}. Then subtract $f(n)+f(n-2)+f(n-3)$ where $f(m)$ is zero if $m<0$ and otherwise is the nearest integer to $\frac{(m+5)^2}{40}$ plus a correction that if $m$ mod 20 is {3,5,7,other} is {-1,+1,-1,0}.

There's maybe a 20% chance that I haven't made any errors in working all that out.

[EDITED to add:] It looks like I got lucky! Here's some Python code implementing (1) the formula above and (2) a brute-force enumeration. First, brute force:

def enumerate_limited_partitions(n,k):
  # enumerate k-tuples (#1, #2, ..., #k)
  if n<0: return
  if n==0:
    yield k*(0,)
    return
  if k==1:
    yield (n,)
    return
  for m in range(n//k+1):
    for p in enumerate_limited_partitions(n-k*m,k-1): yield p+(m,)

def allowed(p):
  streaky = (p[1]+p[2] >= 2)
  return streaky or (p[3]==0 and p[4]==0)

def count(n):
  return sum(allowed(p) for p in enumerate_limited_partitions(n,5))

Second, the formula above:

def p12345(n):
  if n<0: return 0
  return int(round((n+8)*(n**3+22*n**2+44*n+180*(n//2)+248)/2880))

def p145(n):
  if n<0: return 0
  m = n%20
  if m==3 or m==7: delta=-1
  elif m==5: delta=+1
  else: delta=0
  return round((n+5)**2/40) + delta

def gareth(n):
  if n<0: return 0
  t = p12345(n)
  if n<=1: t+=1
  elif n==2: t+=2
  else: t+=3
  return t - p145(n) - p145(n-2) - p145(n-3)

For n from 1 to 40, these both give the following results:

1, 2, 3, 4, 5, 7, 8, 11, 15, 20,
25, 32, 40, 51, 62, 76, 91, 110, 130, 154,
180, 210, 242, 280, 320, 366, 414, 469, 528, 594,
663, 740, 822, 913, 1008, 1113, 1223, 1344, 1471, 1609

$\endgroup$
  • $\begingroup$ My gosh! That's going to take a long time to read through/validate....you put a ton of effort into that. $\endgroup$ – Brandon_J Mar 2 at 20:24
  • $\begingroup$ I don't think this solution accounts for draws being able to be a 2. So that 222000 is actually different from 220200 even though it looks like a permutation. I've been working on this too, and I just came up with a lot of nested sums... $\endgroup$ – Amorydai Mar 2 at 20:55
  • $\begingroup$ I did indeed treat all 2s as equivalent, and if that's not what's wanted then indeed my answer is also not what's wanted. $\endgroup$ – Gareth McCaughan Mar 2 at 20:59
  • $\begingroup$ Unfortunately the main place where treating 2s specially becomes important is in that first term, which is the ugly complicated one that I just looked up. Also unfortunately, if I'm understanding the rules correctly then the right way of dealing with 2s is rather complicated (you can have half as many 2s-as-draws as you have 4s, or something like that). I think the prospects for an elegant formula that handles this stuff are remote. $\endgroup$ – Gareth McCaughan Mar 2 at 21:08
  • $\begingroup$ Edited my question. $\endgroup$ – Brandon_J Mar 4 at 21:02
1
$\begingroup$

I will post my calculations here, someone may find them useful. First thing to note is that differentiating between a win and a draw after a winning streak seems impossible. I tried to come up with strategies that would count the number of wins, but that doesn't really work, especially if you have three berserked wins, where a draw cannot happen, vs. three regular wins, where one draw can occur. So I'll just calculate the different number of ways not taking 2 point draws into account.

So this just comes down to partitioning a number. Since there is no closed-form expression for partition function, I came up with an iterated solution, that just uses a lot of nested sums. Let's say $p_2(x)$ represents the number of ways to partition number x into sums that do not exceed 2. The formula for this is quite easy. $p_2(x)=\lfloor{x/2}\rfloor + 1$. This can be seen when we consider x to be 5, partitions with maximum value of 2 are: 11111; 2111; and 221.

Now comes the iteration. To find $p_3(10)$ for example, you'll start with 3331. Now you'll add all the number of partitions with three 3s, two 3s, one 3 and no 3s: $p_3(10) = p_2(1) + p_2(4) + p_2(7) + p_2(10)$. So the formula becomes $p_3(x) = \sum_{i=0}^{\lfloor{x/3}\rfloor}p_2(x-3*i)$.

By the same reasoning $p_4(x) = \sum_{i=0}^{\lfloor{x/4}\rfloor}p_3(x-4*i)$ and $p_5(x) = \sum_{i=0}^{\lfloor{x/5}\rfloor}p_4(x-5*i)$

Note also, that $p_2(0)=1$, which is correct as $p_3(3)=p_2(3)+p_2(0)=2+1=3$. Here are the partitions: 21, 111, 3.

Now that the formulas are discovered we just need to come up with the grand sum of what we need. First, none of our partitions can be greater than 5. Then, we can only have a 4 or a 5 if we have a 2,2 or a 2,3 or a 3,3. We'll have to take each case separately.

If we have a 2,2 the number of partitions with at least one 5 is $p_5(n-5-4)$. This is because we subtract 4 for the 2,2 and subtract 5 for the one guaranteed 5, everything else is extra. Notice this number will include 4s as well. The number of partitions with at least one 4 and no 5s is $p_4(n-4-4)$. Again, subtracting 4 for the 2,2 and another 4 for the one guaranteed 4.

Moving on to the next cases:
2,3: $p_5(n-5-5)$ and $p_4(n-4-5)$
3,3: $p_5(n-5-6)$ and $p_4(n-4-6)$

Now that we've accounted for all the partitions that include 5s and 4s, we just have to count the number of partitions that only include 3 as the highest number: $p_3(n)$. Simple!

The final answer is:
$p_5(n-11)+p_4(n-10)+p_5(n-10)+p_4(n-9)+p_5(n-9)+p_4(n-8)+p_3(n)$

Now we just define p(negative) as 0 and we have a solution that actually works for all n. The first 20 I get is: 1, 2, 3, 4, 5, 7, 8, 11, 15, 20, 26, 35, 45, 59, 75, 95, 118, 147, 179, 218

I didn't check all of these against @Gareth McCaughan's formula, but, unfortunately, the ones I did check didn't agree...

$\endgroup$
  • $\begingroup$ I would be 100% not surprised if there were mistakes in my calculations. $\endgroup$ – Gareth McCaughan Mar 4 at 21:04
  • $\begingroup$ I just attempted an independent implementation via brute force and got an answer which agrees with ... neither of us :-). The correct numbers, if my brute force calculation is right, go 1, 2, 3, 4, 5, 7, 8, 11, 15, 20, 25, 32, 40, 51, 62, 76, 91, 110, 130, 154, ...; "mine" match those right up to the last one, and then go astray by claiming f(20)=169 instead of 154. $\endgroup$ – Gareth McCaughan Mar 4 at 21:28
  • $\begingroup$ I think your answer double-counts some possibilities. For instance, consider 223355. You will count that under p5(n-5-4) because it has two 2s and a 5, and under p5(n-5-5) because it has a 2, a 3, and a 5, and under p5(n-5-6) because it has two 3s and a 5. $\endgroup$ – Gareth McCaughan Mar 4 at 21:30
  • $\begingroup$ Ah, no, I found a bug in my Python implementation of "my" calculation. It now agrees with brute force. $\endgroup$ – Gareth McCaughan Mar 4 at 21:37
  • $\begingroup$ Yes, I believe you're right. $\endgroup$ – Amorydai Mar 4 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.