17
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – John Doe May 7 '18 at 9:58
  • 1
    $\begingroup$ As you can have an upvote followed by five downvotes, then there will be infinitely ways. $\endgroup$ – Lord Shark the Unknown May 7 '18 at 10:02
  • 7
    $\begingroup$ OP asked for how many ways to reach 1000rep in N steps, clearly for any finite N there is finite many ways. $\endgroup$ – Macrophage May 7 '18 at 10:04
  • 3
    $\begingroup$ Looks like a job for generating functions. $\endgroup$ – Chappers May 7 '18 at 10:37
  • 2
    $\begingroup$ To clarify: this is NOT a meta question, this is a combinatorics question, right? I'm not sure it counts as "recreational math." $\endgroup$ – Robert Soupe May 8 '18 at 2:38
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Szeto Oct 17 '18 at 22:48
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Szeto Oct 17 '18 at 22:50

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.