Set d(x)=f(x)-f(x+1), with f(1) taken to be 1. The sum over all x is 1, because f(1)=1 and f tends to zero. Each d(x) is positive by the assumption that f is monotone strictly decreasing, so d satisfies the condition of full support.
The value of the sum of d(kA) cannot be greater than the sum of d(x) over all x≥A, so 1-d(1)-d(2)-...-d(A-1)=1-(f(1)-f(2))-(f(2)-f(3))-...-(f(A-1)-f(A))=f(A).
In defining d(x), we'll consider two cases.
In the first case, there exists a k>0 such that k!=x. In this case, we'll define d(x)=2-x(1-g(1))+g(k)-g(k+1).
In all other cases, we'll define d(x)=2-x(1-g(1)).
First, let us show that this is a distribution. To prove this, consider that the sum of all 2-x(1-g(1)) equals 1-g(1) while the sum of all g(k)-g(k+1) is g(1), so together they sum up to 1. Second, both 2-x(1-g(1)) and g(k)-g(k+1) are always positive by the fact that g(1) is smaller than 1 and g is strictly monotone decreasing. So, this is a distribution with full support, as desired.
To see that this distribution meets our criteria, consider only the g(k)-g(k+1) part. For any A, all k! values with k≥A divide by A, so p(A) is at least the sum of all g(k)-g(k+1), which is to say at least g(A), as desired.
Let us name the prime numbers sequence: P0=2, P1=3, P2=5, etc..
Consider, now, p(A)=1/A for some constant A. This is a sum of d(x) over all x that are multiples of A.
Let us calculate how much the sum of d(x) is over x values that divide by A but not by P0A,...,PkA for some k.
If k=0, we can do this simply by p(A)-p(2A). However, if we want to increase k to 1, simply subtracting p(3A) will cause the contribution due to values dividing by 6A to be discounted twice. In order to calculate this properly, we will need to add this value back.
In general, the result is the inclusion-exclusion formula: the total probability assigned to multiples of A not dividing any of P0A,...,PkA equals
p(A)-Σi=0k p(PiA) + Σi=0k Σj=i+1k p(PiPjA) - ... =1/A-Σi=0k 1/(PiA) + Σi=0k Σj=i+1k 1/(PiPjA) - ... =1/A Πi=0k (1-1/Pi)
This product is well known to tend to zero as k tends to infinity, so the probability that e equals A exactly, d(A), must be zero. This not only contradicts our assumption of full support, but also the assumption that this is a distribution, as its sum over all A values will be zero, not 1.
Back to riddle
Back to main page