How to reach 1000 reputation?

Question

I wonder how many ways there are to reach 1000 reputation on Math SE in $N$ steps.

Each way is a unique combination of the following additions or deductions, e.g. $+10$ 89 times along with $(+5, +2,+2)$. This way has 92 steps.

One step is an addition or a deduction.

For additions, there are $$(+1, +2, +5, +10, +15)$$

For deductions, there are $$(-1, -2, -5, -15, -100)$$

With 1 base point and 100 points for trusting, this is equivalent to asking how many positive integer solutions there are for $$101+(a_1+2a_2+5a_3+10a_4+15a_5)-(b_1+2b_2+5b_3+15b_4+100b_5)=1000$$ with $$\sum a_n +\sum b_n\le N$$

Moreover, if $s(N)$ is the solution-counting function, what is the asymptotic behaviour for large $N$?

I have no idea of how this problem can be solved.

Any suggestions?

Thanks in advance.

Answer 1

Partial answer:

Let's first write down the ways to gain/lose reputation on MathSE respectively:

• $1$ rep: you undo your downvote/you downvote

• $2$ rep: you edit/someone downvotes your post

• $5$ rep: someone upvotes your question/someone undoes an upvote

• $10$ rep: someone upvotes your answer/someone undoes an upvote

• $50$, $100$, $150$, $\cdots$, $500$ rep: earn bounties/give bounties away

I am taking this from the point of view of a user who has already had the $1$ base rep and the $100$ association bonus.

If $\lambda$ denotes total number of losses and $\gamma$ denotes total number of gains, then for $x_r$ where $r$ is the reputation, $x_r=\gamma_r-\lambda_r$. Define $K$ to be \begin{align}&(1x_1+2x_2)+(5x_5+10x_{10})+(15x_{15}+50x_{50})+(100x_{100}+150x_{150})+(200x_{200}+250x_{250})\\&+(300x_{300}+350x_{350})+(400x_{400}+450x_{450})+500x_{500}\end{align} and we want to solve $K=1000$ for integer solutions.

Now take a step back and consider $K=1$. Notice that I have paired terms up in brackets, so that we may use the Euclidean Algorithm to solve. I use dots for multiplication. $$\gcd(1,2)=1=1.2-1.1\\\gcd(5,10)=5=1.10-1.5\\\gcd(15,50)=5=1.50-3.15\\\gcd(100,150)=50=1.150-1.100\\\gcd(200,250)=50=1.250-1.200\\\gcd(300,350)=50=1.350-1.300\\\gcd(400,450)=50=1.450-1.400\\\gcd(500,500)=500$$ Since $K=1=500-3.50-2.50-2.50-2.50-4.5-5.5-4.1$, we can substitute the above to get \begin{align}1&=1.4+2.(-4)+5.5+10.(-5)+15.12+50.(-4)+100.2+150.(-2)+200.2\\&+250.(-2)+300.2+350.(-2)+400.3+450.(-3)+500.1\end{align} Therefore the general solution for $K=1$ is $$\small x_1=4+2t_1+5t_2+10t_3+15t_4+50t_5+100t_6+150t_7+200t_8+250t_9+300t_{10}+350t_{11}+400t_{12}+450t_{13}+500t_{14}\\x_2=-4-t_1\\x_5=5-t_2\\x_{10}=-5-t_3\\x_{15}=12-t_4\\x_{50}=-4-t_5\\x_{100}=2-t_6\\x_{150}=-2-t_7\\x_{200}=2-t_8\\x_{250}=-2-t_9\\x_{300}=2-t_{10}\\x_{350}=-2-t_{11}\\x_{400}=3-t_{12}\\x_{450}=-3-t_{13}\\x_{500}=1-t_{14}$$ for integers $t_i$ with $i=\{1,2,\cdots,14\}$. For details, see this post.

What we actually want is $y_r=\gamma_r+\lambda_r$, and hence $$N=\sum_ry_r,$$ but we cannot form a direct equation in terms of the $1000$ reputation, as we are essentially making every loss positive. However, we could simplify this problem by writing $$N=\sum_r(x_r+2\lambda_r)=\sum_rx_r+2\sum_r\lambda_r$$ and the former sum is $$\small S=1000(9+t_1+4t_2+9t_3+14t_4+49t_5+99t_6+149t_7+199t_8+249t_9+299t_{10}+349t_{11}+399t_{12}\\\small+449t_{13}+499t_{14})$$

The only thing we need to figure out now is what to do with $\lambda_r$.

Answer 2

This is an attempt. I am very well aware that you cannot get arbitrarily large negative total reputations, but let us assume for the sake of simplicity that this can happen. However, I have a strong hope that the correct asymptotic form (with the lower bound $1$ is taken into account) should be close to what I have obtained.

As for the asymptotic behavior, one can use a probabilistic argument as follows. Let $R\subseteq \mathbb{Z}_{>0}$ be the set of all possible absolute reputation points one can gain or lose. Suppose that $m:=|R|$. Let $\mathbb{P}$ be the discrete uniform probability measure on $\Omega:=R\cup (-R)$.

Let $X_n$ be the random variable of the reputation change at step $n\in\mathbb{Z}_{>0}$ ($X_n$ takes value in $\Omega$, and is negative for reputation losses). Assume that the random variables $X_n$'s are independent and identically distributed with the uniform discrete distribution on $\Omega$. Thus, the expected value of each $X_n$ is $\mathbb{E}[X_n]=0$, whereas the standard deviation $\text{stdev}(X_n)$ is $$\sigma:=\sqrt{\frac{1}{m}\,\sum_{r\in R}\,r^2}\,.$$

Write $S_n:=X_1+X_2+\ldots+X_n$ for every $n=1,2,3,\ldots$. By the Central Limit Theorem (CLT), the random variables $Y_n:=\dfrac{S_n}{\sigma\,\sqrt{n}}$ for $n\in\mathbb{Z}_{>0}$ converge in distribution to the standard normal variable. That is, for each $x\in \mathbb{R}$, $$\lim_{n\to\infty}\,\mathbb{P}[Y_n\leq x]=\frac{1}{2}\,\Biggl(1+\text{erf}\left(\frac{x}{\sqrt{2}}\right)\Biggr)\,.$$ Hence, $$\lim_{n\to\infty}\,\mathbb{P}\left[S_n\leq \sigma\,\sqrt{n}\,x\right]= \frac{1}{2}\,\Biggl(1+\text{erf}\left(\frac{x}{\sqrt{2}}\right)\Biggr)\,.$$ Thus, we get $$\mathbb{P}\left[\sigma\,\sqrt{n}\,(x-\epsilon)<S_n\leq \sigma\,\sqrt{n}\,x\right]\approx \frac{1}{\sqrt{2\pi}}\,\exp\left(-\frac{x^2}{2}\right)\,\epsilon\,,\tag{*}$$ where $\epsilon>0$ is small and $n$ is a large positive integer.

Now, for a target score $t\in\mathbb{Z}$, we have by setting $x:=\dfrac{t}{\sigma\,\sqrt{n}}$ and $\epsilon:=\dfrac{1}{\sigma\,\sqrt{n}}$ in (*) that $$\mathbb{P}\left[t-1<S_n\leq t\right]\approx \frac{1}{\sqrt{2\pi\,\sigma^2\,n}}\,\exp\left(-\frac{t^2}{2n\sigma^2}\right)\,.$$ In other words, the number of ways to get $S_n=t$ for a fixed integer $t$ and for a large integer $n>0$ is $$f(n,t):=|\Omega|^n\,\mathbb{P}\left[t-1<S_n\leq t\right]\approx \frac{(2m)^n}{\sqrt{2\pi\,\sigma^2\,n}}\,\exp\left(-\frac{t^2}{2n\sigma^2}\right)\,.$$ If $|t|\ll \sigma\,\sqrt{n}$, then we may further say that $$f(n,t)\approx \frac{(2m)^n}{\sqrt{2\pi\,\sigma^2\,n}}\in \Theta\left(\frac{(2m)^n}{\sigma\,\sqrt{n}}\right)\,,$$ which is independent of $t$ (well, in the approximating sense).

Note that I also assume that the starting point is $0$. If you start from $1$ and your final score is $1000$, then you should set $t:=1000-1$. If you start from $101$ with the same final score $1000$, then set $t:=1000-101$.