These Ceilings Can Hold You (In Frustration)

Let's first deal with the inside sum first: $\sum_{j=1}^i\left\lceil x+\dfrac{j}{i}\right\rceil$ letting $i$ be a constant. Let's call that sum $g(x)$ .

Expanding, we see that we want to find $g(x)=\left\lceil x+\dfrac{1}{i}\right\rceil+\left\lceil x+\dfrac{2}{i}\right\rceil+\cdots +\left\lceil x+\dfrac{i-1}{i}\right\rceil+\left\lceil x+1\right\rceil$

This looks a lot like Hermite's Identity. Too bad that it's ceilings, not floors. But what if we could derive a similar formula for ceilings? Let's try it.

First, note that when $x\in \left(0,\dfrac{1}{i}\right]$ , then $g(x)=i+1$ . When $x\in \left(\dfrac{1}{i},\dfrac{2}{i}\right]$ , then $g(x)=i+2$ . We see that when $x\in \left(\dfrac{k}{i},\dfrac{k+1}{i}\right]$ , then $g(x)=i+k+1$ (the proof is simple). Thus, when $ix\in (k,k+1]$ , or equivalently when $\lceil ix\rceil =k+1$ then $g(x)=i+k+1$ . Thus, $g(x)=\lceil ix\rceil +i$ The proof will be left as an exercise to the reader (it's not that different than proving Hermite's Identity).

---

Thus, we have reduced the problem to $f(x)=\sum_{i=1}^{20}(\lceil ix\rceil +i)$

First off, note that $f(x+1)-21=f(x)$ , so we just need to consider the parts where $f(x)=1\to 210$ (since the pattern repeats for $x > 210$ and $x < 0$ ), or when $x\in (0,1]$ .

Now note that whenever $ix$ turns into an integer, $f(x)$ increases by one. Thus, the parts where $f(x)$ changes value is when $x=\dfrac{a}{b}$ , where $a\le b$ and $b\le 20$ (these bounds come from $x\in (0,1]$ ). But how can $f^{-1}(n)$ not exist then? The reason is that sometimes, there exists two or more $i_1,i_2,\ldots i_k\in \{1,2,\ldots 19,20\}$ such that $i_mx$ is an integer for all $m=1\to k$ . This happens when $\dfrac{a}{b}$ is not in its simplest form, or $\gcd (a,b)\ne 1$ .

Thus, to count the number of possible values of $f(x)$ , we just need to count the number of times where $\gcd(a,b)=1$ . Letting $b=1\to 20$ , we see that this happens $\phi(1)+\phi(2)+\cdots +\phi(20)$ times.

Thus, our probability is $\dfrac{\sum\limits_{i=1}^{20}\phi(i)}{210}$ . Unfortunately, there is no easy way to calculate the numerator, so we just have to bash. Bashing all the values, we see that our probability is $\dfrac{128}{210}=\dfrac{64}{105}$ , and our answer is $64+15=\boxed{169}$ .