Using your Head is Permitted

March 2009 riddle

UPDATE (1 April): So far, there have been no complete solutions for the March riddle. The riddle will therefore run one extra month, but with several modifications and extra hints, as described below. A new April riddle will be posted, as usual, in parallel to this one.

Modification: Instead of asking only for complete solutions for the entire riddle, we will accept certain partial solutions as well. Here is the list of partial solutions accepted, for which special solvers' lists will be kept:

  • Part 1, Part 2 and Part 3 for k=n
  • Parts 1+2
  • Part 3
  • Part 1 + Part 2 for the case k=1
  • Part 1 + Part 2 for the case k=2
  • Part 1 + Part 3 for the case k=1
  • Part 3, but only Z1 and Z2 are required to be uniformly distributed in [0,1] and independent of each other.
  • Part 3, but only Z1 through Zk are required to be uniformly distributed in [0,1] and independent of each other, for the maximum possible k (with proof of impossibility for higher k)

Hint for Part 2: Consider what the sum of all these variables is.

Hint for Part 3: Consider the strategy used in the solution to the May 2007 riddle.

Credit for the invention of this month's riddle goes to Terry Soo, Ander Holroyd, Oded Schramm, Jim Propp and Omer Angel. They refer to it as "fun with uniform distributions".

Answer all parts to appear on the solvers' list.

Part 1:

X,Y and Z are independent random variables, all uniformly distributed between a and b. However, a and b are not known. Suggest how to calculate from these a new random variable, uniformly distributed between 0 and 1.

Part 2:

X1, ..., Xn are n random variables uniformly distributed between 0 and 1, satisfying that their sum is a constant.

For which values of n do such variables exist?

As a function of n, what is the maximum possible value of k, if it is known that any k of the n Xi variables are independent of each other? Describe an algorithm that produces such a set of random variables for each possible (k,n) combination. Prove impossibility for all other cases.

Part 3:

Suppose that X1, ..., Xn are n independent random variables uniformly distributed between 0 and 1. Further, suppose that Y1, ..., Yn are random variables with the same values as the Xi variables, only sorted from smallest to largest. Not only has the original order been lost here, the variables Yi are now neither uniformly distributed nor independent. (For example, despite the fact that both Y1 and Yn share the same range, Y1 ≤ Yn always holds, so the two variables have a dependency and their expectations are different, not both equal 0.5.)

Let f be a function (Z1, ..., Zn) = f(Y1, ..., Yn) that, once again, reorders the random variables, satisfying the condition that the new random variables that it produces, Zi, are -- like the Xi variables but unlike the Yi variables -- all uniformly distributed between 0 and 1. (Simply picking a random order for the Yi variables would have worked, but f is a deterministic function, so it cannot pick a "random" order.)

For which values of n does such a function exist?

As a function of n, what is the maximum possible value of k, if it is known that any k of the n Zi variables are independent of each other? Describe a function, f, that produces such a set of random variables for each possible (k,n) combination. Prove impossibility for all other cases.

Note that (Z1, ..., Zn) is merely a reordering of the existing random variables X1, ..., Xn and that f only receives (Y1, ..., Yn) as its input, so it is unaware of the original ordering of the Xi variables.

List of solvers:


Partial solvers:

Part 1:

Mark Tilford (31 March 06:04)
Hongcheng Zhu (6 April 00:17)

Part 2:


Part 2 for k=1
Mark Tilford (31 March 06:04)

Part 2 for k=2
Hongcheng Zhu (6 April 00:17)

Part 3:


Part 3 for k=1
Mark Tilford (31 March 06:04)

Part 3 for k=n

Part 3, only Z1 and Z2

Part 3, only Z1 through Zk

Elegant 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