Using your Head is Permitted

September 2016 riddle

Serge Gautier posed me the following question:

Various autopilot software (subways, cars, planes...) use error detecting systems, to avoid being fooled by accidental data corruption.

For example, an integer X can be coded with two fields (x, r), with r = kx mod A for some integers k and A. X is valid if (kx - r) mod A = 0.

Suppose x is altered by an error (but not r) and becomes (x + e): this error won't be detected if k(x + e) - r mod A = ke mod A = 0, which amounts to e mod A = 0 if we wisely take k co-prime with A. So the general assumption is that such systems have probability 1/A of not detecting a random error.

Serge is wondering what this means regarding the distribution of e, the "random errors", over the naturals, if such assumptions were to hold regarding all possible choices of A>1. Let p(A) be the probability that e is not detected in modulo A, given that it is polled from a specific distribution, D, over the naturals. What distributions will satisfy p(A)=1/A exactly? Can an adversary design a distribution that will always satisfy p(A)≪1/A? Can an adversary design a distribution that will always satisfy p(A)≫1/A?

To make these questions more concrete, let f(x) and g(x) be two monotone strictly decreasing functions over the naturals such that for all x, 0<f(x)<1 and 0<g(x)<1, and when x tends to infinity f and g both tend to zero.

Answer all of the following questions with proof.

  1. For which f(x) can you design a distribution for e such that for all A>1, p(A)≤f(A)?
  2. For which g(x) can you design a distribution for e such that for all A>1, p(A)≥g(A)?
  3. Can you design a distribution for e such that for all A, p(A)=1/A?
To be admissible, your distributions must all have full support, which is to say that for every natural e, the probability for e must be positive.

List of solvers:

Gaoyuan Chen (2 September 17:21)
JJ Rabeyrin (9 September 15:59)
Radu-Alexandru Todor (12 September 08:08)
Luke Pebody (14 September 16:26)
Oscar Volpatti (30 September 04:15)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!

To solution

Back to main page