Breaking matches, or Alice in the country of mathematical errors

I have a favorite puzzle forum. I recently came across the following task there:

Once Vasya sat in his kitchen and broke nothing for nothing to make matches. Broke, break and think - what is the probability that at least one match will be broken exactly in the middle? The supply of matches for Vasya is unlimited.


I quickly proved that the probability of this event is zero. Proud of myself, I posted a decision and an answer, expecting a plus sign in karma. It turned out, however, that the author’s answer was completely different: 1 - 1 / e . Looking ahead, I will say that this answer is incorrect.

Wrong copyright solutions are a fairly common occurrence in online puzzles. And I would never write this post if the author of the problem, as well as its incorrect solution, were not the British logician and algebraist Charles L. Dodgson, better known under the pseudonym Lewis Carroll.

Trivia


All mathematicians know that the author of Alice in Wonderland was a mathematician. It is widely known that Queen Victoria, having read both Alice, wished to read the author’s other books and was very surprised when they brought her treatises on analytic geometry and linear algebra. In addition to these fundamental areas, Carroll was interested in mathematical puzzles and other interesting things. In 1888, he published the book “Mathematical Curiosities,” and five years later, its continuation, “Midnight Tasks,” from which the problem of matches was taken (of course, no Vasya appeared in the original). Five years later, Charles Dodgson died.

Carroll's decision


The solution posted on the forum was very clumsy. I had to rather guess what exactly the author wanted to say. Then I turned to the source - the same book, “Midnight Tasks.” I had to be surprised a second time: my forum opponent did not misinterpret a single word. Translating from Russian into Russian, I got something like the following:

Take n matches, each of them is divided by n points into n + 1 equal parts. Suppose that n is odd, and matches can break only at marked points, and at each with equal probability. Then the probability of breaking a match not in the middle is 1 - 1 / n , the probability of not breaking in the middle of any of the n matches is (1 - 1 / n) n . Tending n to infinity, we obtain 1 / e. Accordingly, the probability of breaking at least one match exactly in the middle will be 1 - 1 / e .


Why is this not working?


In his decision, the author managed the only variable n. In fact, we have two variables: the number of matches and the number of points on each of them. Denote them by p and q, respectively. Then the probability that none of the p matches will be broken in the middle of q points is F (p, q) = (1 - 1 / q) p . When we rush p and q to infinity, F rushes to the desired probability ... or does not rush?

The problem is that the function of two variables F does not havelimit at infinity. In this case, however, we can get a certain limit by moving to infinity along a certain trajectory (in this case, Carroll finds a limit along the trajectory described by the equation p = q). However, the value of this limit depends entirely on the trajectory. For example, if we mark n points, but take not n matches, but 2n, we get the probability (1 - 1 / n) 2n , which in the limit gives 1 / e 2 .

In the same way, we can get 1 / e 3 , and 1 / e 42 , and even 1 / e 256 . Obviously, the chosen solution method is not suitable for this task.

Deeper into the wilds
There are two fundamental reasons why this passage to the limit did not help and could not help Carroll solve the problem (at least solve it correctly). The first of them is as follows: having marked a finite number of points on a segment, in the limit we get an infinite, but countable, set of them. At the same time, the set of points of the segment has a power continuum, which is an infinity of a higher order. This distinction was established by George Cantor somewhere in the 70s of the XIX century. However, at the time of writing Midnight Problems, Cantor set theory was not yet the foundation of mathematical analysis that it later became, and Carroll, according to biographers, was "far from the cutting edge of the mathematical science of its time." One way or another, even in the limit of the place of a possible fracture, they turn out to be only a small subset of the match points.

The second reason is that in the initial and limiting case, we, in fact, are dealing with different probability spaces and different definitions of probability. When we select one point from n, this happens within the discrete probability space, while choosing a point on a segment is already a geometric probability. Even if such a transition is correct, it needs additional justification.


What is the correct answer?



Zero, of course. The geometric probability of getting to a single point is zero, not getting into it is one. The probability of not getting into it once in an infinite number of attempts is equal to unity in the degree of infinity, which, in turn, is equal to ... unity? Not really. This is the same uncertainty as zero divided by zero. More subtle methods will be required here.

Impressive not to watch
Let us show that for an arbitrarily small d, the probability P to break at least one match in half is less than d.

Find c such that 1 - d = e c . To be precise, c = ln (1 - d) . Let the matches have a unit length and be numbered. In the middle of the first match, fill in a segment of length 1 - e c / 2 , in the middle of the second - length of 1 - e c / 4 , in the middle of the nth - length of 1 - e c / 2 n . Note that c <0 ; therefore, all indicated lengths will be positive.

The probability that no match will be broken at a point belonging to the shaded segment is equal to e c / 2 * e c / 4* ... * e c / 2 n * ... = e (c / 2 + c / 4 + ... + c / 2 n + ...) = e c = 1 - d . Therefore, the probability that at least one fault falls into the shaded segment is d. Since if one of the matches is broken in the middle, the fault will fall on the shaded segment, we can conclude that P <d .

The number d was chosen arbitrarily. Therefore, P is less than any positive number, i.e. P = 0, p.t.


In fact


The mysterious mistake of a professional mathematician intrigued me, and I decided to find the original book. After tormenting Google for about twenty minutes, I managed to achieve what I wanted. What did I see?

Page Scan
image


Firstly, the presentation was much more logical than in the Russian translation, which initially seemed very strange to me. Compare, for example:

The chance of one failure is (n - 1) / n

and
The probability of breaking a match at one point is (n - 1) / n


Secondly, part of the proof from the translation in the original was simply missing! In particular, the value 1 - 1 / e was not even indicated there . In addition, there was an interesting note:
NB What follows here was NOT thought out.
Important Note: The next part has not been carefully thought out.


All this indicates that Carroll’s “wrong decision” was a rough draft rather than a complete reasoning. For some reason unknown to us, he simply could not devote sufficient attention to this task. It is also noticeable from calculations that mathematical analysis is not the area of ​​specialization of the author.

Having clarified the question that bothered me in this way, I sat down to write my first post on Habr.

Post script
I thought about the comments regarding the existence of this probability. Indeed, this is a serious problem that I did not immediately notice.

If you try to build a probabilistic space “in the forehead” in which it makes sense to talk about such a probability, then a problem arises, in fact, with measure. It seems that setting a suitable sigma-additive measure in a countable-dimensional unit cube is not as easy as I would like.

On the other hand, it is possible to determine the probability of an event during endless breaking of matches as the limit of this probability for breaking en matches when en tends to know where you are. Then everything becomes completely obvious, and my decision under the spoiler is no longer required.

Also popular now: