Breaking matches, or Alice in the land of mathematical errors
I have a favorite puzzle forum. I recently stumbled upon the following task:
I quickly proved that the probability of this event is zero. Proud of myself, I posted a decision and an answer, waiting for a plus sign in karma. It turned out, however, that the author's answer is completely different:1 - 1 / e . Looking ahead, I will say that this answer is incorrect.
')
Wrong author decisions are quite common in Internet puzzles. And I would never write this post if the author of the problem, as well as its incorrect decision, was not the British logician and algebraist Charles L. Dodgson, better known by the pseudonym Lewis Carroll.
All mathematicians know that the author of Alice in Wonderland was a mathematician. The bike that Queen Victoria, having read both “Alice”, wished to familiarize herself with the other books of the author was widely known and was very surprised when she was given treatises on analytical geometry and linear algebra. In addition to these fundamental areas, Carroll was fond of 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 task of matches was taken (of course, Vasya did not appear in the original). Five years later, Charles Dodgson was gone.
The decision posted on the forum was stated very clumsily. I had to guess what the author wanted to say. Then I turned to the source - the very book "Midnight Tasks". I had to be surprised the second time: my opponent in the forum didn’t miss a single word. Translated from Russian into Russian, I received something like the following:
In his decision, the author has managed the only variable n. In fact, we have two variables: the number of matches and the number of points on each of them. We denote them as 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 push p and q to infinity, F rushes to the desired probability ... or does it not rush?
The problem is that the function of two variables F has no limit at infinity. At the same time, however, we can get a certain limit, moving to infinity along a certain trajectory (in this case, Carroll finds the 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, then we get the probability(1 - 1 / n) 2n , which in the limit gives 1 / e 2 .
Similarly, we can get 1 / e 3 , 1 / e 42 , and even 1 / e 256 . It is obvious that the chosen method of solution is not suitable for this task.
Zero, of course. Geometric probability to get to a single point is zero, not to get into it - one. The probability of not getting into it never for an infinite number of attempts is equal to a unit in the degree of infinity, which, in turn, equals ... to a unit? Not really. It is the same ambiguity as zero divided by zero. More subtle methods will be required here.
The mysterious mistake of a professional mathematician intrigued me, and I decided to find the original of the book. Having tormented Google for about twenty minutes, I managed to achieve what I wanted. What did I see?
Firstly, the presentation was much more logical than in the Russian translation, which initially seemed very strange to me. Compare, for example:
and
Secondly, part of the proof from the translation in the original was simply absent! In particular, the value1–1 / e was not even indicated there. In addition, there was an interesting note:
All of this indicates that Carroll’s “wrong decision” was more of a draft than reasoning. For some unknown reason, he simply could not pay enough attention to this task. It is also clear from the calculations that mathematical analysis is not an area of ​​specialization of the author.
Having clarified the question that worried me, I sat down to write my first post on Habr.
Vasya sat once in his kitchen and had nothing to do with matches and broke them. Broke, broke and wondered - what is the probability that at least one match will be broken exactly in the middle? The stock of matches at Vasya is unlimited.
I quickly proved that the probability of this event is zero. Proud of myself, I posted a decision and an answer, waiting for a plus sign in karma. It turned out, however, that the author's answer is completely different:
')
Wrong author decisions are quite common in Internet puzzles. And I would never write this post if the author of the problem, as well as its incorrect decision, was not the British logician and algebraist Charles L. Dodgson, better known by the pseudonym Lewis Carroll.
Trivia
All mathematicians know that the author of Alice in Wonderland was a mathematician. The bike that Queen Victoria, having read both “Alice”, wished to familiarize herself with the other books of the author was widely known and was very surprised when she was given treatises on analytical geometry and linear algebra. In addition to these fundamental areas, Carroll was fond of 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 task of matches was taken (of course, Vasya did not appear in the original). Five years later, Charles Dodgson was gone.
Carroll's decision
The decision posted on the forum was stated very clumsily. I had to guess what the author wanted to say. Then I turned to the source - the very book "Midnight Tasks". I had to be surprised the second time: my opponent in the forum didn’t miss a single word. Translated from Russian into Russian, I received something like the following:
Take n matches, each of them is divided by n points inton + 1 equal parts. Suppose that n is odd, and matches can break only at marked points, and in each with equal probability. Then the probability of breaking a match in the middle is1 - 1 / n , the probability of not breaking in the middle of any of the n matches is(1 - 1 / n) n . Letting n go to infinity, we get 1 / e. Accordingly, the probability of breaking exactly in the middle at least one match will be equal to1 - 1 / e .
Why is this not working?
In his decision, the author has managed the only variable n. In fact, we have two variables: the number of matches and the number of points on each of them. We denote them as 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) =
The problem is that the function of two variables F has no limit at infinity. At the same time, however, we can get a certain limit, moving to infinity along a certain trajectory (in this case, Carroll finds the 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, then we get the probability
Similarly, we can get 1 / e 3 , 1 / e 42 , and even 1 / e 256 . It is obvious that the chosen method of solution is not suitable for this task.
Deeper into the wilds
There are two fundamental reasons why this limit transition did not help and could not help Carroll solve the problem (at least, solve it correctly). The first of these is this: by marking 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 a segment has the power of a continuum, which is a higher-order infinity. This distinction was established by Georg Cantor somewhere in the 1870s. However, at the time of writing the Midnight Tasks, Cantor set theory was not yet the foundation of mathematical analysis that later became, and Carroll, according to biographers, was "far from the leading edge of the mathematical science of his time." Anyway, even in the limit of the place of a possible fracture, they are only a small subset of the points of the match.
The second reason is that in the initial and limiting case, we are essentially dealing with different probability spaces and different definitions of probability. When we select one point from n, it occurs within the discrete probability space, the choice of a point on the segment is already a geometric probability. Even if such a transition is correct, it needs additional justification.
The second reason is that in the initial and limiting case, we are essentially dealing with different probability spaces and different definitions of probability. When we select one point from n, it occurs within the discrete probability space, the choice of a point on the 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. Geometric probability to get to a single point is zero, not to get into it - one. The probability of not getting into it never for an infinite number of attempts is equal to a unit in the degree of infinity, which, in turn, equals ... to a unit? Not really. It is the same ambiguity as zero divided by zero. More subtle methods will be required here.
Impressionable not look
We show that, for an arbitrarily small d, the probability of P breaking at least one match in half is less than d.
We find c such that1 - d = e c . To be precise, c = ln (1 - d) . Let the matches be of one length and numbered. In the middle of the first match, paint a segment of length 1 - e c / 2 , in the middle of the second - with a length of 1 - e c / 4 , in the middle of the nth one - with a length of 1 - e c / 2 n . Note that c <0 , so all the specified lengths will be positive.
The probability that no match will be broken at the point belonging to the shaded segment ise c / 2 * e c / 4 * ... * e c / 2 n * ... = e (c / 2 + c / 4 + ... + c / 2 n + ...) = e c = 1 - d. Consequently, the probability that at least one fault falls into a shaded segment is d. Since if one of the matches is broken in the middle, the fault falls on a 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, pt.d.
We find c such that
The probability that no match will be broken at the point belonging to the shaded segment is
The number d was chosen arbitrarily. Therefore, P is less than any positive number, i.e. P = 0, pt.d.
In fact
The mysterious mistake of a professional mathematician intrigued me, and I decided to find the original of the book. Having tormented Google for about twenty minutes, I managed to achieve what I wanted. What did I see?
Scan pages
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 absent! In particular, the value
NB What follows here was NOT thought out.
Important Note: The next part was not carefully thought out.
All of this indicates that Carroll’s “wrong decision” was more of a draft than reasoning. For some unknown reason, he simply could not pay enough attention to this task. It is also clear from the calculations that mathematical analysis is not an area of ​​specialization of the author.
Having clarified the question that worried me, I sat down to write my first post on Habr.
Post Scriptum
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 “head on” in which it makes sense to talk about such a probability, then the problem arises, in fact, with the measure. It seems that it is not as easy to set an appropriate sigma-additive measure in a countable dimensional unit cube as I would like.
On the other hand, it is possible to determine the probability of an event with an infinite breaking of matches as the limit of this probability for breaking en matches with an en aspiring yourself know where. Then everything becomes completely obvious, and my decision under the spoiler is no longer required.
If you try to build a probabilistic space “head on” in which it makes sense to talk about such a probability, then the problem arises, in fact, with the measure. It seems that it is not as easy to set an appropriate sigma-additive measure in a countable dimensional unit cube as I would like.
On the other hand, it is possible to determine the probability of an event with an infinite breaking of matches as the limit of this probability for breaking en matches with an en aspiring yourself know where. Then everything becomes completely obvious, and my decision under the spoiler is no longer required.
Source: https://habr.com/ru/post/167041/
All Articles