I occasionally see puzzles that include language like this:

You go to buy a specific car, whose fair price we’ll call N. You have absolutely no idea what N is

Or this from the same site:

Given any three random integers — X, Y and Z — what are the chances that their product is divisible by 100?

This feels troubling to me, for reasons I talked about here in comments a few years ago but had trouble explaining properly. The thing is that mathematically, there's no way to pick a random integer (or whole number, or real number) such that any integer is as likely as any other one. I'll cite another stackexchange here rather than go into it in detail. You can pick an unbounded random integer, but the way you do it will matter to the answer of the puzzle. For example, you could flip a coin until it gets heads and count how many flips, then flip once more to determine positive or negative. The puzzle creator for the random integer puzzle would hate that idea, though, since he probably wanted us to assume that each integer had a 1 in 5 chance of being divisible by 5, for example, and an integer generated that way has a much less than 1 in 5 chance. A random distribution that gives the intuitive property relevant to that problem would be to pick a power of 100 using the coinflip method, then pick a number less than it by rolling a 100^N-sided die, then flipping a coin for the sign. But that kind of random distribution gives a bad, or non-intuitive, outcome, for the other two problems I linked. For example, if the fair price of a car was generated that way in the first problem, the optimal stopping strategy would take into account that there's a higher probability that the fair price is $50 than $150.

So I'm tempted to say that puzzles shouldn't use terms like "a random number" without specifying either a range or a probability distribution, and equivalently shouldn't say you have "no information" about a number. But with puzzles that do that, I do feel like there's almost always consensus about the answer, that somehow we can safely assume the details of the probability distribution to be irrelevant. Is there some way of formalizing this intuition mathematically to "rescue" this sort of puzzle?


For both of the puzzles you link to, unless I am mistaken, the following is true:

Define the "N-restricted" version of the problem to be what you get by replacing "a random positive integer" with "a random positive integer <= N" and assuming that different integers are chosen independently. Then the limit, as N tends to infinity, of the answer to the N-restricted problem is the "intended" answer.

More strongly, I think something like the following is true:

Suppose the problem depends on $k$ variables $X_1\dots X_k$. Say that a probability distribution on $\mathbb{N}^k$ is $\varepsilon$-good if for any $x=(x_1,\dots,x_k)$ and $y=(y_1,\dots,y_k)$, with probabilities $p,q$, we have $|p-q|<\varepsilon(p+q)+\varepsilon^2$. Suppose we have a sequence of $\varepsilon_n$-good probability distributions with $\varepsilon_n\rightarrow0$, and write $a_n$ for the answer to the question using the $n$th of these; then $a_n\rightarrow A$ where $A$ is the "intended" answer.

Either of these says, in some sense, that if you have something "enough like" the (impossible) uniform distribution we would like to have, then the result is "like" the intended one; the stated problem is a limit of problems involving more-and-more-uniformly distributed integer-valued random variables. I think any way of dealing rigorously with this sort of situation is going to require that.

(Note: I just made up the notion of $\varepsilon$-goodness and it may be stupid. The idea, of course, is to require that different possible outcomes' probabilities converge both absolutely and relatively. Perhaps we actually want to consider not only individual $x,y$ but arbitrary subsets of $\mathbb{N}^k$. That might be impossible. "Nice" subsets in some sense, perhaps. I dunno.)

As will be apparent, this is certainly not The Answer, but I'm pretty sure it points in the direction of the sort of thing that's needed to formalize talk of uniformly-random choice of integers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.