# How to reach 1000 reputation?

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.

• Not related to the actual maths of the problem, but how do you get $-100$ rep?? Also, I am not sure how to solve the problem mathematically since new way would emerge discontinuously as $N$ increases. I feel it should be doable asymptotically though. – John Doe May 7 '18 at 9:58
• As you can have an upvote followed by five downvotes, then there will be infinitely ways. – Lord Shark the Unknown May 7 '18 at 10:02
• OP asked for how many ways to reach 1000rep in N steps, clearly for any finite N there is finite many ways. – Macrophage May 7 '18 at 10:04
• Looks like a job for generating functions. – Chappers May 7 '18 at 10:37
• To clarify: this is NOT a meta question, this is a combinatorics question, right? I'm not sure it counts as "recreational math." – Robert Soupe May 8 '18 at 2:38

## 2 Answers

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$$.

• It is a great delight to me that my long unanswered question suddenly got two detailed answers. I will need time to understand them. Thank you and please be patient. – Szeto Oct 17 '18 at 22:48

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) 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 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 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$$.

• It is a great delight to me that a long unanswered question suddenly got two detailed answers. I will need time to understand them. Thank you and please be patient. – Szeto Oct 17 '18 at 22:50