Using your Head is Permitted

September 2016 solution

Let d(x) be the probability that e=x. p(A) is the probability that e is a multiple of A, so the sum over all k of d(kA).

Part 1:

Any f(x) works. Here's one distribution that works.

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 xA, 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).


Part 2:

Any g(x) works. Here's one distribution that works.

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


Part 3:

No, it is not possible to construct a distribution such that p(A)=1/A for all A.

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/Ai=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