Dating and marriage: mathematics can help you find the best partner

Lovers will eventually marry. When we choose blind dating to solve the most important life event, can we find the most ideal partner? How many blind dates do we need to go through to meet the right person?

In fact, this is a classic problem in mathematics - optimal stopping theory. The most amazing thing is that the transcendental number e is hidden in it. Why does this universal constant appear in your blind date? Puzzle 2 in this article will give the answer. Puzzle 3 is another mathematical problem extended from love (puzzle 1 is also very interesting). I wish you all a happy Valentine's Day!

By Pradeep Mutalik

Compilation | Nezha

Last month, we gave three puzzles that seemed ordinary, but contained a twisted story about numbers. Behind the story is the mysterious transcendental number (Euler's number) e. We are most familiar with it as the base of natural logarithms. e is a universal constant and has an infinite number of decimals: 2.7 1828 1828 45 90 45... (This spacing is written just to show a certain regularity of the 15 digits after the decimal point). So why did it suddenly appear in our puzzles?

Before answering this question, we need to know more about the properties of e. Like its transcendental brother π, e has countless ways of being expressed, such as the sum of an infinite series, the product of an infinite number of numbers, the limit of an infinite sequence, and an amazing regular continued fraction.

I remember the first time I learned about e. We were learning about common logarithms in middle school, and I was amazed at how expressing all numbers as fractional powers of 10 turned complicated multiplication into simple addition. However, I wondered, how were fractional and irrational powers calculated? Of course, it was easy to calculate whole-number powers, like 10^2, 10^3, and even 10^2.5 by taking the square root of 10^5 in a pinch. But how did they get, like the logarithm table, that 20 is 10^1.30103? How could one construct a complete logarithm table from scratch? I simply couldn't imagine how this could be done.

Later, I learned of a magical formula that accomplishes this feat. It revealed the origin of the “natural” in “natural logarithm”:

For negative exponents, staggered terms appear:

This powerful formula can be used to compute e raised to any real power, including integer or fractional powers from negative infinity to positive infinity, to any desired precision. It is thus possible to construct a complete table of natural logarithms from scratch, and from this table to obtain general logarithms.

Let x = 1, and we get the expression of e:

Additionally, e has many surprising properties, some of which are implicated in the solution to our puzzle. But there is one property that points to the essence of e and makes it natural to account for logarithmic and exponential growth and decay:

This formula states that the rate of change of e^x at all points is equal to its own value. If expressed as time, this formula states that the rate of growth (or decay, in the case of -x) is equal to the size or amount accumulated so far. There are countless phenomena in the real world that behave like this over a period of time, and we know of them as examples of exponential growth or decay. But beyond its practicality, there is an element of aesthetic perfection and naturalness in this property of e that can really inspire curiosity. It even carries a moral lesson; I like to think of it as a Zen-like function that is always in perfect balance in its pursuit of growth, never going above or below what it has achieved.

Warning: In the following puzzle solutions, we'll be involving more advanced, scary-looking math than is usually found in this puzzle column. Don't worry if the equations make your eyes glaze over; try to follow the general arguments and concepts. I hope everyone can gain some understanding of our puzzles, regardless of how and why they appear. In the BBC series The Ascent of Man, Jacob Bronowski, speaking about the mathematical work of John von Neumann, said that it is important to follow the tone of the conceptual argument when reading mathematics - the equations are just "the orchestration of the bass section."

Now let's try to find out how e appears in the puzzle.

Puzzle 1: Decomposition

Solution to question a:

In the previous article, I gave a hint: when the value of each equal part is closest to e, the product reaches its maximum value. More precisely, when the values ​​of the equal parts are on both sides of e, the two largest products are achieved. For the relatively small, everyday numbers we are considering here, the maximum value of the product can be obtained when the value of the equal parts is the smallest difference from e.

Solution to question b:

From the above, it's easy to see that when two adjacent equally spaced values ​​are nearly equidistant from e, the two products will be closest, one lower than e and the other higher than e. (This is strictly true only if the function is symmetric about e. Here it is not, but in this range it's close enough, as reader Michel Nizette brilliantly explains.)

If the original number is N, this happens when the fractional part of the ratio N/e is close to 0.5, that is, when N/e is close to the midpoint of two integers. Therefore, if you construct a table of N/e where N goes from 1 to 100 and then look for the fractional part closest to 0.5, you will get the integer you want: 53. 53 divided by e is 19.4976, and the difference between the products of dividing 53 into 19 and 20 equal parts is only 0.0013%.

Solution to question c:

Voila! That’s how e appears and gets the maximum product.

This tells us that e has an optimization property. It can appear in situations where we are looking for maxima or minima, as we will see in Puzzle 2. A basic version of this property of e can be seen when evaluating a function where x is over all positive real numbers (this is Steiner's problem). The x at which the function is maximized over an infinite number of real numbers is e. The maximum value of x^1/x is equivalent to the maximum value of Inx/x, and the derivative of the latter is (1-Inx)/x^2, which is zero if and only if Inx=1, that is, x=e.

Puzzle 2: Blind Date

As readers have pointed out, this is a restatement of the famous secretary problem. The main points are summarized below.

The heir must choose the best one from a pool of 10 potential spouse candidates according to the following rules. Candidates are interviewed one by one and are either accepted (if deemed the best) or rejected before the next candidate is considered. Rejected candidates cannot be recalled, and the process stops once a candidate is accepted. If the process has not ended, the last candidate must be accepted by default.

Solution to question a:

a. Assuming there are no ties in ranking, how can an heir maximize his chances of choosing the best mate?

This situation requires the heir to unconditionally reject a certain number of candidates (the "rejection" phase) and then enter the "selection phase" - in which the heir selects from the remaining candidates the first candidate that is ranked higher than all previously rejected ones. The chance of selecting the best candidate is greatest when the rejection phase has a certain length. The probability of selecting the best decreases if the rejection phase is longer (the best candidate is more likely to be rejected) or shorter (he does not have enough experience to properly rank the candidates, resulting in the acceptance of a lower-ranked candidate).

This is called the "optimal stopping"[2] problem, and e appears in its solution because it is optimal. For a large number of candidates n, the number of candidates initially rejected should be equal to n divided by e.

Here is the probability calculation for n = 10. If the rejection stage (r) = 3, that is, 3 people are rejected, let's see what the answer is.

First, note that the best candidate may appear at any point in the 10 interviews, with a 1/10 probability (1/n) of being in any particular position. For each interviewer's position (i), we multiply this 1/10 by the probability that the best candidate will be selected in that position. We then add up the probabilities for all positions to establish the general expression.

• If the best candidate is in position 1 to 3, they will be automatically rejected. Probability of selecting the best candidate:

Solution to question b:

b. If there is a 10% chance that two people tie for first place, how does the heir's chance of meeting the best partner change?

Since the succession now has two top-ranked candidates, the chances of finding the best candidate increase.

Solution to question c:

c. This is a classic problem whose solution is related to e. Can you explain how e enters the answer?

e enters the scene twice in this puzzle! As n gets larger, Euler's number shows up in the probability of making the best choice, and in the fraction of people who initially reject it.

The probability expression we derived above can be expressed as a limit as n→∞ by substituting x for r/n (the rejection rate), p for (i-1)/n (the incremental probability at each n), and dp for 1/n (the rate of change from one integer to the next).

So the limit of probability is:

Puzzle 3: Intimacy

A large auditorium is hosting a show that only couples are allowed in. When a couple enters the auditorium, they randomly select a pair of seats next to each other. Each newlywed couple does this, and in many cases, this results in an empty seat between the couples. Entries continue until only single seats are left, then the auditorium is declared full and the show begins.

Solution to question a:

a. When seating stops, what percentage of seats are expected to be empty?

Dividing these numbers by the number of seats gives the percentage of vacant seats, and one reader calculated that for 10 seats it is 16.24%, for 100 seats it is 13.804%, for 1,000 seats it is 13.561%, and for 6,000 seats it is 13.538%. You can see that the numbers are close to or 13.5335…%. But how do we know that this is what they are aiming for? Because their relationship takes a long time to calculate.

Recursive relations are nice, but it's like trying to climb an infinite staircase step by step. What we really need is a closed expression that depends only on n. A closed expression is like an elevator. Press the button for any n, and whoosh! The elevator takes you there, even to the top of the building, where the view is infinite.

Notes

[1] Wolfram Alpha is an intelligent computing tool available at:

https://www.wolframalpha.com/

[2] See Optimal Stopping Theory and Classic Secretary Problem:

https://blog.csdn.net/hilda_Huang/article/details/8099202

This article is translated from:

Where Transcendental Numbers Hide in Everyday Math

Original link:

https://www.quantamagazine.org/why-eulers-number-is-just-the-best-20211124/