ALGORITHM

COMPUTATION

CRYPTOGRAPHY

FRONTEND

GAME-THEORY

INVESTMENT

JS&TS

LINUX

MATHEMATICS

NODE

OTHERS

PROJECT-PRACTICE

REACT

THOUGHTS

古文整理

文史哲艺


This issue can be seen as a classic case of historical inertia combined with outdated reforms in the education system. This encapsulates the core of the problem.

Frankly, I find it difficult to tolerate the myriad justifications people offer to defend this situation. It is merely a residual consequence of the glacial pace of educational reform, yet some have framed it as "developing logical thinking" or claimed that "university isn't a training camp." Such arguments are utterly untenable.

In reality, even if computer science majors studied more mathematics instead of physics, it would be far more beneficial.

Computer science fundamentally diverges from traditional engineering disciplines such as civil engineering, mechanical engineering, electronic engineering, and chemical engineering. These traditional fields are rooted in physics, whereas computer science is deeply grounded in mathematics.

Traditional engineering disciplines primarily engage with the physical world. Their foundations lie in natural sciences, particularly physics, and they boast histories spanning decades, if not centuries. The primary focus of these disciplines is the transformation of the physical realm.

Consider this: as a mechanical engineering major, it is inconceivable to bypass the study of mechanics—how else would you design gears? If you are in precision instrumentation, knowledge of optics and electronics is indispensable for designing sensors. For chemical engineering students, quantum mechanics and thermodynamics are fundamental to understanding molecular interactions. Similarly, hydraulic engineering requires mastery of fluid mechanics.

Each traditional engineering discipline is built upon natural sciences like physics, dedicated to leveraging these principles to reshape the material world.

In stark contrast, computer science follows an entirely distinct trajectory. It is a "formal science," entirely man-made, with most of its concepts abstracted directly from mathematics.

Modern computer science theory originated with Alan Turing, whose work on computability theory employed pure mathematical constructs to define the concept of a "computer." These theoretical foundations were later implemented to create various types of computing systems.

Computer science, at its core, studies theoretical frameworks. While engineers apply these frameworks to design chips and systems, the discipline itself focuses on abstract structures and models rather than the tangible, physical world.

Formal sciences—such as mathematics, logic, and computer science—emphasize abstract, logical constructs instead of physical phenomena. They rely on deductive reasoning and logical proofs rather than empirical observation, which aligns computer science closely with mathematics.

For instance, many foundational concepts in computer science, such as Turing machines, operating system models, and the Von Neumann architecture, are mathematical abstractions. These constructs do not exist in nature; they are products of human ingenuity.

Even programming concepts such as functions, pointers, parameters, and operators—or areas like complexity analysis—are rooted in mathematical models. Algorithm design exemplifies this reliance on mathematical abstraction.

So, what justification exists for requiring computer science majors to study physics? Will they be calculating the forces involved in moving servers? Or perhaps determining the melting point of silicon to fabricate CPUs?

Let us be candid: computer science is fundamentally a repository of mathematical abstractions. This alignment with mathematics is entirely unsurprising, given the discipline's origins.

And for those who argue, "We study electronics to design circuits for CPUs," it is crucial to clarify: digital circuits and logic gates are mathematical abstractions as well. The physical implementation of chips falls under the domain of electronic engineering, not computer science. The role of computer science is to provide the models, theories, and blueprints, while other fields handle physical realization.

Furthermore, most computer science graduates today pursue careers in software development. It is unrealistic to assume they are designing CPUs.

In China, computer science was only formalized as a university discipline in the 1980s, following the reinstatement of the national college entrance exams. However, the theoretical foundations of computer science had already been established during World War II. By the time China integrated it into its educational system, we were already lagging behind Western nations by no less than half a century.

During that era, computers were a rarity in China, and expertise in teaching the subject was even scarcer. Lacking domestic models to emulate, we resorted to copying. Since physics was a staple of other STEM fields, it was incorporated into computer science curricula as well.

And yet, we remain entrenched in these antiquated practices. Despite nearly four decades, our approach to computer science education continues to stagnate. For example, certain universities still teach C++ using VC6, a tool that is unequivocally obsolete by contemporary standards.

In conclusion, the shortcomings of computer science education in China can be attributed to historical inertia and outdated reforms. Unlike traditional engineering disciplines rooted in physics, computer science is grounded in mathematics and focuses on abstract models. The inclusion of subjects like physics in the curriculum reflects a failure to adapt to the unique nature and practical demands of this field.


China's computer science education is outdated, often including irrelevant subjects like physics, due to historical and systemic inertia.

Should Computer Science Majors Learn College Physics


In the United States, the date format is uniquely distinctive and stands out globally. Unlike the European "small to large" DMY format or the East Asian "large to small" YMD format, the U.S. uses MDY. Moreover, unlike other Europeans who prefer pure numeric date formats, Americans use a semi-numeric, semi-English format: English month + numeric date + numeric year. For example, today is November 27, 2024. While a British person might write it as 27/11/2024, an American would write it as November 27, 2024!

Below is a map of date formats around the world:

![](https://image-assets.dreams.plus/images20241128101343.webp)

In the map, blue areas represent DMY, yellow areas represent YMD, red areas use a mix of DMY and MDY, green areas use a mix of DMY and YMD, and pink areas exclusively use MDY. The only country that uses this date format is the United States.

A British author once complained American written form, and wrote this on his book.
> “Most British people write the day first, followed by the month. Businesspeople and older women still insist on putting the month first.” \
> —— _Have His Carcase_, by Dorothy Leigh Sayers

I am genuinely puzzled by the logic behind the American date format. Many former British colonies or Commonwealth countries have adopted the British DMY format. But why didn't the United States, once a British colony heavily influenced by British culture, inherit the DMY format?

In fact, the American insistence on their date format has led to some amusing anecdotes. For instance, a British woman and an American man planned a date and wrote "10/12/1997" in their letters. However, they never met. Why? Because the American man understood it as October 12, while the British woman understood it as December 10!

If the world only had YMD and DMY formats, even when Asians and Westerners read each other's texts, there would be no ambiguity.

For example, dates like "2024-11-11" and "11-11-2024" can be easily understood by looking at the position of the year, allowing one to quickly determine the date format and identify the corresponding month and day. The world would be a much better place.

However, the problem lies in the strong influence of the United States in computer science and technology, which has forced their culture, including the anti-human MDY date format, onto the world, including Europe.

If you encounter an English text with a date like "11/11/2024" and cannot determine whether it was written by an American or a British person, how would you interpret it?

As a result, many English-speaking countries, including several European nations, have had to compromise: when dates are ambiguous, the month should be written in abbreviated form. For example, the British would write the above date as 11 November, 2024, or 11 Nov. 2024.

Thus, the world is now caught in a three-way battle between MDY, YMD, and DMY.

The origins of the YMD and DMY formats reflect the long-term practical needs of Eastern and Western civilizations. The reasons for these differences are varied and inconclusive, but there are two plausible explanations from cultural needs and cognitive linguistics.

The first explanation is based on cultural needs.

For a long time, the Chinese did not adopt the Western Gregorian calendar but used the era name system. Era names held significant political importance in ancient China, reflecting the will of the state and the emperor. After Emperor Wu of Han, official documents often placed the era name at the beginning to show its importance. China, being an agricultural society, developed the lunar calendar, where agricultural activities were often organized by months for planting, cultivating, and harvesting. Hence, the Chinese prioritized the year and month. Other East Asian countries like Korea, Japan, and Mongolia were also influenced by the Chinese lunar calendar.

Europeans, on the other hand, had a different approach. During the Middle Ages, Europe was deeply religious, and Europeans frequently participated in religious activities such as Sundays and sermon days. Church activities emphasized specific dates of holidays and religious events, with months being secondary information and years changing less frequently, thus placed last. For example: "Die 31 mensis Decembris anno Domini 2024" (December 31, 2024). This tradition of prioritizing the "day" has continued in many European countries, influencing their date formats.

The second explanation comes from cognitive linguistics.

From a linguistic perspective, the Western DMY format is used because European languages generally follow a logical sequence from specific to abstract, with the date as a modifier expressed first, close to the core words of month and year. In many Indo-European languages, modifiers (such as specific dates or temporal features) usually precede the main information. Western address formats also share this characteristic, starting with the house number and street, followed by the city, state, or province. This format aligns with the European linguistic habit of "modifiers being close to the modified object" and fits their cultural emphasis on logic and linear time flow. Chinese, using a large-to-small logic (year → month → day), emphasizes the progressive relationship of time, aligning with the Chinese narrative structure of "background to specifics."

In my opinion, the best date format should be one that is friendly to both humans and computers, which is the YMD format popular in East Asian countries. YMD is more intuitive for humans and most convenient for organizing documents.

While the differences between YMD and DMY can be explained from various angles, what is the logic behind the American MDY format? What is the rationale for using MDY?

After extensive online research, I have not found a concrete reason.

I strongly suspect that some American just came up with this date format on a whim.

Since most languages (like Chinese and English) are read from left to right, imagine you need to sort a pile of documents by date. When you see a date like "20241111," you can easily scan the numbers 2-0-2-4-1-1-1-1 in sequence, quickly identifying the year and month prefix, and categorize it into a "broad range" for easier sorting. However, if the date format is the British DMY, like "12072024," you need to interrupt your reading flow, start scanning from the end (4-2-0-2), then correct the order to "2-0-2-4" to identify the year, and then scan "7-0," correcting it to "0-7" to identify July. Thus, when scanning a DMY date, extracting the year and month requires changing direction four times. While manageable in the short term, it becomes a significant mental burden with large workloads, greatly increasing the chance of errors due to carelessness.

The YMD format is also very computer-friendly. YMD dates can be directly sorted in computers, as the string format "2024-07-12" is sequentially encoded, making dictionary sorting straightforward.

Imagine you have two files:

```plaintext
2024-11-12-document1.docx
2024-12-07-document2.docx
```

With the date format prefix, the former file name will always have a higher dictionary order than the latter, allowing file explorers to sort by date directly using the file names.

Numeric dates like "20240712" also make it easy to compare two dates using simple computer comparison operators like `>` and `<`, without needing additional processing.

These advantages are not present in the DMY format.

American stubbornness is not limited to date formats; their measurement standards are also a mess. For example, Fahrenheit and imperial units (miles, inches, feet, gallons, ounces, etc.). The imperial system originated during the Roman Empire in Europe and has long been a confusing mess with no fixed standards, changing over different historical periods. It wasn't until the Middle Ages that Britain standardized these units.

However, when Britain established the imperial system, there were no strict, standard measurements. For example, an inch was defined as the length of three barleycorns laid end to end, and a foot was the distance from King Edward's nose to his outstretched hand. The problem is, using barleycorns to define an inch means a thousand barleycorns could have a thousand different lengths, and using body parts for length definitions means a thousand people could have a thousand different lengths. It remains a confusing mess.

The long-standing confusion in measurements was only resolved with the development of modern French natural science, leading to the strict definition of the metric system. The metric system uses reproducible physical experiments for definitions, making it much more rigorous than the imperial system.

Thus, today, the entire world, except the United States, uses the metric system. But the U.S. remains an outlier, stubbornly clinging to the imperial tradition under the guise of "cultural heritage" and "preserving freedom and diversity." The American refusal to adopt the metric system is as irrational as the Lilliputians in _Gulliver's Travels_ arguing over which end of an egg to crack. It's truly bizarre.


In the United States, the date format is unique in the world. It is different from the European "small to large" DMY and the East Asian countries' "large to small" YMD. It is actually MDY.

Complain on American Date Format

Let us implement rendering markdown in React and we'll embark on fundamental conceptions of Markdown compiling procession with usages and examples for unified plugins.

How to Render Markdown Document in React


British economist John Maynard Keynes and Austrian economist Friedrich Hayek are two of the most renowned figures in the history of 20th-century economic thought. Their ideas not only had a profound impact on the past economic and social landscape, but they will continue to influence current and future economic and social development until a more convincing economic ideology takes hold. The debate between Keynes and Hayek is known as “the most classic and famous duel in economic history.” American journalist Nicholas Wapshott, who was a senior editor at *The Times* of London and *The New York Sun*, systematically examined this debate in his book *Keynes Hayek: The Clash that Defined Modern Economics*. As we revisit this classic academic feast, we also reflect on the serious economic question: “To what extent should the government intervene in the market?”

Today, people are already quite familiar with the starkly opposing economic views of Keynes and Hayek. Keynes believed that the root cause of an economic crisis is the lack of confidence among capitalists in investment prospects, leading to reduced investment, and thus advocated for effective government intervention and control over social economic activities. Hayek, on the other hand, believed that the root cause of economic crises was over-investment by capitalists and argued that government intervention would only damage the mechanisms of market development and functioning. Therefore, he firmly defended the idea of a free market order. Keynes argued that the government could expand public spending through fiscal deficits and national debt, increase state investment and consumption, and indirectly advocated for the "nationalization of currency." Hayek, by contrast, proposed that currency issuance should be handed over to private banks, which would provide sound and stable money based on their own interests, advocating for the "denationalization of currency."

Keynes supported inflationary policies to increase corporate profits, stimulate investment, expand employment, and achieve stable economic development. Hayek argued that inflation would widen the income gap, cause asset prices to soar, and eventually lead to greater unemployment and economic vicious cycles. He believed that business cycles would naturally return to full employment. Keynes argued for increased investment in public works, improving social welfare, and providing relief spending for those living below the poverty line. Hayek, however, believed that public goods do not directly satisfy any specific demand but provide certain conditions under which individuals and smaller groups can enjoy better opportunities to meet their respective needs.

The debate between Keynes and Hayek is characterized by a vast ideological chasm, and throughout their lives, they could never reconcile with each other’s viewpoints. Their debates were later carried on by their passionate disciples, such as John Kenneth Galbraith and Milton Friedman. In terms of personality, the two were also very different. Keynes was highly articulate and charismatic, often painting an optimistic vision of the world, which was embraced by an entire generation of politicians and economists on both sides of the Atlantic. In contrast, Hayek was meticulous and persistent, swimming against the tide, but found support among market advocates and libertarians. To this day, the two distinct schools of thought in economics continue their “battle.”

This economic battle has left government decision-makers oscillating between the two scholars' ideas, influencing the ups and downs of the world economy, affecting the lives and livelihoods of billions. The global economic crisis of 1929–1933 led to the widespread adoption of Keynesianism, represented by the "New Deal" of Franklin D. Roosevelt, and it seemed that Keynes had triumphed over Hayek. However, the oil crisis of the 1970s plunged the global economy into the dilemma of "stagflation," and the neoliberalism represented by the "Washington Consensus" became the dominant policy-making ideology, giving Hayek a comeback. By the end of the 20th century, the failure of neoliberal economic policies in Latin America, Russia, Southeast Asia, and Eastern Europe, coupled with the impact of the 2008 global financial crisis, suggested that Keynesianism might once again be on the rise.

In terms of policy practice, the struggle between Keynesianism and neoliberalism may continue, and it is still too early to conclude who will ultimately prevail. Interestingly, the Nobel Prize in Economics, which is seen as a "weather vane" for academic trends, has also been swayed by economic crises and shifts in government decision-making. Since the Nobel Prize in Economics was first awarded in 1968, Keynes, who had passed away by then, was naturally ineligible. Hayek, however, won the prize in 1974. During the 1970s and 1980s, when neoliberalism was on the rise, figures like Milton Friedman, Robert Lucas, Finn Kydland, and Edward Prescott also won the prize. Later, however, new Keynesians like Joseph Stiglitz and Peter Diamond, who carried on Keynes' legacy, were awarded the prize as well. In 2012, with the resurgence of neoliberalism, Alvin Roth and Lloyd Shapley took home the Nobel Prize in Economics.

In fact, despite their dramatic disagreements, Keynes and Hayek had similar aims. They both studied the same subject: the cycles of boom and bust in commercial activity that emerged from the ruins of World War I. Both sought to establish a theoretical framework that combined real and monetary phenomena to explain the dynamics of the economy, especially the business cycle. Their economic theories both originated from Knut Wicksell's theory of monetary equilibrium and the concept of "natural interest rates." Furthermore, they shared a deep commitment to the basic principles of a market economy governed by freedom, democracy, and the rule of law. If we look purely at logical reasoning, both of their theoretical conclusions and policy recommendations could explain the causes of economic recessions and offer solutions. The historical choices made by policymakers ultimately explain the root cause of their disagreements—it was a matter of experience and practical judgment.

It’s worth mentioning that although their debate was often heated, with sharp criticisms exchanged, the mutual respect they maintained beyond academia, and their personal friendship, is even more commendable. Although Hayek had differing views on credit from Keynes, he praised Keynes' *A Treatise on Money* as "an outstanding description and classification of different forms of money." Similarly, Keynes was deeply moved by Hayek's great work *The Road to Serfdom*. Keynes not only provided housing for Hayek when he first arrived in London, but in their debate letters, they openly discussed their friendship. Hayek once said, “Although I still disagreed with Keynes' views and had fierce debates with him, we maintained the best of personal friendships. And as a man, I held him in the highest esteem in many ways.”

Their ideas not only had a profound impact on the past economic and social landscape, but they will continue to influence current and future economic and social development until a more convincing economic ideology takes hold.

The Historical Debate Between Hayek and Keynes


## The Largest Ear of Wheat

It is said that Socrates once led his students for a walk in a wheat field. His students asked him: how can one find the most suitable life partner?

Socrates looked at the wheat field and gave them a task: "Go into the wheat field and find the largest ear of wheat, but as you walk, you can only move forward and cannot turn back."

The students began walking while choosing, and the field was full of large ears of wheat. But which one was the largest? They walked with their heads down, checking one ear of wheat after another. They shook their heads at this one; they shook their heads at that one. They always believed that the largest ear was still ahead. Although they picked a few, they were not satisfied and threw them away. They thought there were plenty of chances and no need to decide too early.

The students continued walking with their heads down, carefully selecting as they went, for quite a long time. Suddenly, they heard Socrates' deep, resounding voice: "You have reached the end." At that moment, the students, empty-handed, realized what had happened and felt disheartened.

Socrates said to them: "There is certainly a largest ear of wheat in this field, but you may not encounter it; and even if you do, you may not make the correct judgment. Therefore, the largest ear is the one you just picked."

This story tells us that life is like walking in a wheat field, also searching for the largest ear of wheat. Some people, upon seeing a full and ripe ear, seize the opportunity and pick it without hesitation; others keep looking around and miss their chances again and again. Of course, the goal should be the largest ear, but holding the one in hand is the most tangible reality.

**So, the question arises: Is there a method that can help us find the largest ear of wheat as efficiently as possible?**

## Treasure Box Game

Let’s consider another example. Imagine there is a gambling game with the following rules: There are $m$ treasure boxes, each containing a random prize amount between $0$ and $x$ dollars, uniformly distributed. **However, you don’t know what the maximum amount $x$ in the boxes is.** Once you open a treasure box and see the prize, you have two choices: either take the prize and stop, or discard the box and open another one. However, once discarded, a box cannot be chosen again.

Now the question arises: how should you strategize to get the most money possible? Naturally, the more money, the better.

What would happen if we didn’t use any strategy and randomly picked a treasure box?

Let’s assume the amounts in the treasure boxes range from $1000, 999, 998, ..., 0$, with the top prize being $1000$. What is the probability of drawing the top prize?

Since each specific amount (including the top prize of $1000) has an equal chance of appearing, and the prize is uniformly distributed, the probability of drawing the top prize can be calculated as follows:

$$
P_{Jackpot} = \frac{1}{(\text{MaxMoney} - \text{MinMoney} + 1)}
$$

In this case, the maximum prize is $1000$ and the minimum is $0$, so:

$$
P_{Jackpot} = \frac{1}{(1000 - 0 + 1)} = \frac{1}{1001}
$$

Therefore, the probability of randomly picking a treasure box containing the top prize of $1000$ is $0.0999\% ≈ 0.1\%$. The odds are very low indeed.

Since chasing the jackpot is unrealistic, let’s lower our expectations a bit. What if we aim for a prize of at least $800$? What is the probability of winning that?

We can use the formula for uniform distribution. For a prize uniformly distributed between $0$ and $1000$, the probability density function is constant. The formula for probability is:

$$
P(a \leq X \leq b) = \frac{b - a}{\text{range}}
$$

In this case, the range is from $0$ to $1000$, so the total range is $1000$. We want to calculate the probability for the interval from $800$ to $1000$, so:

$$
P(800 \leq X \leq 1000) = \frac{1000 - 800}{1000} = \frac{200}{1000} = 0.2
$$

Thus, the probability of randomly selecting a treasure box with a prize between $800$ and $1000$ is $20\%$.

While the probability has increased significantly, $20\%$ is still relatively low.

So, if you randomly pick a treasure box and decide to keep it, the chances of getting a high prize are still slim, which clearly isn’t the optimal strategy.

## Optimization

**In most cases, we don’t know the maximum prize inside the treasure boxes.** Just like in the story of Socrates' students picking the largest ear of wheat, they didn’t know how big the largest ear was.

Let’s change our approach. Even though we don’t know the maximum prize, we do know that if we sample a portion of the treasure boxes, the probability of finding the jackpot in the sample is equal to its probability in the entire set. By sampling some treasure boxes, we can estimate the value of the jackpot based on the maximum prize in the sample.

Let’s denote the jackpot in the entire set as $M$. Since the jackpot is uniformly distributed among the treasure boxes, we can take a sample from the boxes and record the maximum prize in that sample, denoted as $M'$. Clearly, this sample maximum $M'$ will be close to the overall jackpot $M$.

Sampling a portion of the boxes to estimate the jackpot $M$ is feasible, and the more samples we take, the closer $M'$ will be to $M$.

However, the sample size cannot be too small, or the difference between $M'$ and $M$ will be large, making the estimate ineffective. On the other hand, the sample size cannot be too large either, because there will be fewer treasure boxes left to choose from, reducing the chance of finding the jackpot. Consider an extreme example: if we sample $999$ treasure boxes out of $1000$, $M'$ will likely be almost equal to $M$, but with only one treasure box remaining, the chance of hitting the jackpot becomes negligible.

Thus, it is important to balance the sample size with the total number of treasure boxes. Is there an optimal sample size where $M'$ is close to $M$ and the probability of winning a high prize is maximized afterward?

Next, we will use mathematical methods to derive this “balance point.” Suppose the total number of treasure boxes is $m$, and the sample size is $r$. We will find the expression for the optimal $r$.

## Mathematical Derivation

Assume we have a total of $N$ treasure boxes, and we select the first $r$ boxes as a sample. In this scenario, we aim to find the optimal sample size $r$ that maximizes the probability of selecting the highest prize after discarding the sample.

### Probability Derivation

For a fixed $r$, suppose the highest prize appears in the $k$-th treasure box. To win the highest prize after discarding the sample, it is necessary that the second-highest prize appears in the first $k-1$ boxes, and specifically, this second-highest prize must also appear within the sample (the first $r$ boxes). The probability of this happening is $\frac{r}{k-1}$.

This can be visualized with a diagram, where the red arrow indicates the positions where the second-highest prize occurs:

![](https://image-assets.dreams.plus/20240922115506.webp)

Thus, we derive the following equation:

$$
P = \frac{1}{N} \sum_{k=r+1}^{N} \frac{r}{k-1} = \frac{r}{N} \sum_{k=r+1}^{N} \frac{1}{k-1}
$$

In this equation, $\frac{1}{N}$ represents the probability of the highest prize appearing in the $k$-th treasure box, and $\frac{r}{k-1}$ represents the probability that the second-highest prize is within the sample of the first $r$ boxes. $P$ is the probability of winning the highest prize after discarding the sample.

### Summation Approximation

The above equation contains a harmonic series, which does not have a simple closed form but can be approximated using the following formula:

$$
\sum_{k=1}^{N} \frac{1}{k} = \ln(N) + \gamma
$$

where $\ln(N)$ is the natural logarithm and $\gamma$ is Euler's constant. Here, we want to approximate the summation from $r+1$ to $N$. To do this, we rewrite the sum as:

$$
\sum_{k=r+1}^{N} \frac{1}{k-1} = \sum_{k=1}^{N-(r+1)+1} \frac{1}{k} = \sum_{k=1}^{N-r} \frac{1}{k}
$$

Thus, the sum starts from $k=1$ and follows the same harmonic series approximation:

$$
\sum_{k=r+1}^{N} \frac{1}{k-1} = \left( \ln(N) + \gamma \right) - \left( \ln(r) + \gamma \right) = \ln(N) - \ln(r)
$$

Finally, using logarithmic properties, we simplify this to:

$$
\ln(N) - \ln(r) = \ln\left(\frac{N}{r}\right)
$$

### Substituting into the Original Equation

Now, we substitute the simplified sum into the original probability equation:

$$
P = \frac{r}{N} \ln\left(\frac{N}{r}\right)
$$

Next, we introduce a new variable $x = \frac{r}{N}$ to represent the proportion of the total boxes chosen as the sample, yielding:

$$
P = x \ln\left(\frac{1}{x}\right)
$$

### Maximizing the Probability

To maximize $P$, we take the derivative of $P = x \ln\left(\frac{1}{x}\right)$ with respect to $x$:

$$
\frac{dP}{dx} = \frac{d}{dx} \left(x \ln\left(\frac{1}{x}\right)\right)
$$

Using the product rule:

$$
\frac{d}{dx}(uv) = u \frac{dv}{dx} + v \frac{du}{dx}
$$

where $u = x$ and $v = \ln\left(\frac{1}{x}\right)$, we calculate the derivatives:

$$
\frac{du}{dx} = 1
$$

and

$$
\frac{dv}{dx} = \frac{d}{dx} \ln\left(\frac{1}{x}\right) = \frac{d}{dx} \left(-\ln(x)\right) = -\frac{1}{x}
$$

Substituting these into the product rule:

$$
\frac{dP}{dx} = x \left(-\frac{1}{x}\right) + \ln\left(\frac{1}{x}\right) \cdot 1 = -1 + \ln\left(\frac{1}{x}\right)
$$

To find the maximum probability $P$, we set the derivative equal to zero:

$$
-1 + \ln\left(\frac{1}{x}\right) = 0
$$

Thus, we have:

$$
\ln\left(\frac{1}{x}\right) = 1
$$

Exponentiating both sides, we get:

$$
\frac{1}{x} = e
$$

Therefore, $x = \frac{1}{e}$, which means the probability is maximized when $\frac{r}{N} = \frac{1}{e}$.

### Maximum Probability

At this optimal point, the maximum probability is:

$$
P = P_{max} = \frac{1}{e} \approx 0.368
$$

This shows that the optimal strategy is to sample approximately $\frac{1}{e}$ (about 36.8%) of the total treasure boxes and then select the next box that is greater than all the ones in the sample. This strategy maximizes the chance of selecting the highest prize.

## Program Simulation

We can use TypeScript to simulate the process described above.

To verify the probability of winning the highest prize using this strategy, we can calculate the ratio of successful trials where the highest prize is obtained to the total number of trials. Below is a TypeScript program that simulates this process:

```typescript
function simulateGamblingGame(m: number, x: number, trials: number): number {
  let successCount = 0;

  for (let trial = 0; trial < trials; trial++) {
    const boxes = Array.from({ length: m }, () => Math.random() * x);
    const firstPart = boxes.slice(0, Math.floor(m * 0.37));

    // Remember the highest prize in the first 37% of boxes
    const p = Math.max(...firstPart);

    // Find the maximum prize in all boxes
    const maxPrize = Math.max(...boxes);

    // Check from the 37% onward if a prize higher than p is found
    for (const prize of boxes.slice(Math.floor(m * 0.37))) {
      if (prize > p) {
        if (prize === maxPrize) {
          successCount++;
        }
        break; // Stop once a higher prize is found
      }
    }
  }

  return successCount / trials; // Return the success probability
}

// Set parameters
const m = 100; // Total number of boxes
const x = 1000; // Maximum prize in each box
const trials = 100000; // Number of trials

const successProbability = simulateGamblingGame(m, x, trials);
console.log(`Probability of winning the highest prize: ${successProbability}`);
```

### Explanation

1. **Parameters**:
   - `m`: Total number of treasure boxes.
   - `x`: Maximum prize in each box.
   - `trials`: Number of simulation trials. More trials increase accuracy.
2. **Simulation Process**:

   - Randomly generate the prize for each box.
   - Calculate the maximum prize in the first 37% of the boxes (`p`).
   - Find the highest prize (`maxPrize`) in all boxes.
   - Starting from the 38% box, check if there is a prize higher than `p` and if it equals `maxPrize`.

3. **Result**:
   - Return the probability of winning the highest prize after many trials.

Running this simulation produces a result like this:

```plaintext
Probability of winning the highest prize: 0.367999
```

As shown, the probability of winning the highest prize increases to around 37%, which is a significant improvement from 0.1%.

---

To further verify, let's simulate the probability of winning the top $t\%$ prizes by dividing the prize ranges into $10\%$ increments (e.g., top 10%, top 20%, etc.).

### Modified TypeScript Code for Different Prize Ranges

```typescript
function simulateGamblingGameWithRanges(
  m: number,
  x: number,
  trials: number
): number[] {
  const successCounts = Array(10).fill(0);
  // Array to store the number of successes in each range

  for (let trial = 0; trial < trials; trial++) {
    const boxes = Array.from({ length: m }, () => Math.random() * x);

    const k = Math.floor(m * 0.37);
    const firstPart = boxes.slice(0, k);

    const p = Math.max(...firstPart);

    let chosenPrize = 0;

    // Find the first box greater than p after the first 37% boxes
    for (const prize of boxes.slice(k)) {
      if (prize > p) {
        chosenPrize = prize;
        break;
      }
    }

    // If no box greater than p is found, select the last box
    if (chosenPrize === 0) {
      chosenPrize = boxes[boxes.length - 1];
    }

    const sortedBoxes = [...boxes].sort((a, b) => b - a);

    // Determine the prize range that the chosen prize falls into
    for (let i = 1; i <= 9; i++) {
      const thresholdPrize = sortedBoxes[Math.floor((m * i * 10) / 100)];
      if (chosenPrize >= thresholdPrize) {
        successCounts[i - 1]++;
      }
    }

    // The top 100% prize is always chosen, so increment this count
    successCounts[9]++;
  }

  // Convert counts to probabilities
  const successProbabilities = successCounts.map((count) => count / trials);

  return successProbabilities;
}

// Set parameters
const m = 100; // Number of boxes
const x = 1000; // Maximum prize
const trials = 100000; // Number of trials

const successProbabilities = simulateGamblingGameWithRanges(m, x, trials);

// Output the probabilities for each prize range
for (let i = 1; i <= 10; i++) {
  console.log(
    `Probability of winning a prize in the top ${i * 10}%: ${(
      successProbabilities[i - 1] * 100
    ).toFixed(2)}%`
  );
}
```

### Results from the Program

```plaintext
Probability of winning a prize in the top 10%: 66.96%
Probability of winning a prize in the top 20%: 70.67%
Probability of winning a prize in the top 30%: 74.42%
Probability of winning a prize in the top 40%: 78.06%
Probability of winning a prize in the top 50%: 81.70%
Probability of winning a prize in the top 60%: 85.45%
Probability of winning a prize in the top 70%: 89.14%
Probability of winning a prize in the top 80%: 92.84%
Probability of winning a prize in the top 90%: 96.60%
Probability of winning a prize in the top 100%: 100.00%
```

We see that, using this strategy, we maximize the chances of getting a high-value prize.

## Conclusion

The simulation verifies that selecting 37% of the boxes first and then choosing the next box with a prize greater than the maximum from the first 37% is the optimal strategy. This maximizes the probability of winning the highest prize, known as the **37% rule**.

This strategy can also be applied in real-life scenarios, such as making optimal choices in uncertain situations.


This article proposes the classic 37% rule in game theory and its mathematical derivation process.

Socrates: The Story of Searching for the Largest Ear of Wheat


## Wallis's Formula

Let's start with a definite integral:

$$
\int_{0}^{\frac{\pi}{2}} \sin^n x \, dx
$$

We can derive the following result:

$$
\int_{0}^{\frac{\pi}{2}} \sin^n x \, dx = -\int_{0}^{\frac{\pi}{2}} \sin^{n-1} x \, d(\cos x)
$$

Using integration by parts, where $\int u \, dv = uv - \int v \, du$, we get:

$$
-\int_{0}^{\frac{\pi}{2}} \sin^{n-1} x \, d(\cos x) \\ = -\left( \sin^{n-1} x \cos x \right) \Big|_{0}^{\frac{\pi}{2}} + \int_{0}^{\frac{\pi}{2}} \cos x \, d\left(\sin^{n-1} x \right)
$$

$$
= \int_{0}^{\frac{\pi}{2}} \cos^2 x \cdot (n-1) \sin^{n-2} x \, dx \\ = (n-1) \int_{0}^{\frac{\pi}{2}} \left( \sin^{n-2} x - \sin^n x \right) \, dx
$$

Thus:

$$
\int_{0}^{\frac{\pi}{2}} \sin^n x \, dx = (n-1) \int_{0}^{\frac{\pi}{2}} \left( \sin^{n-2} x - \sin^n x \right) \, dx
$$

We get:

$$
n \int_{0}^{\frac{\pi}{2}} \sin^n x \, dx = (n-1) \int_{0}^{\frac{\pi}{2}} \sin^{n-2} x \, dx \\ \implies \int_{0}^{\frac{\pi}{2}} \sin^n x \, dx = \frac{n-1}{n} \int_{0}^{\frac{\pi}{2}} \sin^{n-2} x \, dx
$$

Therefore:

**For even $n$, i.e., $n = 2k$:**

$$
\int_{0}^{\frac{\pi}{2}} \sin^{2k} x \, dx = \frac{2k-1}{2k} \int_{0}^{\frac{\pi}{2}} \sin^{2k-2} x \, dx \\ = \frac{2k-1}{2k} \cdot \frac{2k-3}{2k-2} \cdots \frac{1}{2} \int_{0}^{\frac{\pi}{2}} \sin^0 x \, dx \\= \frac{2k-1}{2k} \cdot \frac{2k-3}{2k-2} \cdots \frac{1}{2} \cdot \frac{\pi}{2}
$$

**For odd $n$, i.e., $n = 2k + 1$:**

$$
\int_{0}^{\frac{\pi}{2}} \sin^{2k+1} x \, dx \\ = \frac{2k}{2k+1} \int_{0}^{\frac{\pi}{2}} \sin^{2k-1} x \, dx \\ = \frac{2k}{2k+1} \cdot \frac{2k-2}{2k-1} \cdots \frac{2}{3} \int_{0}^{\frac{\pi}{2}} \sin^1 x \, dx \\ = \frac{2k}{2k+1} \cdot \frac{2k-2}{2k-1} \cdots \frac{2}{3}
$$

Here, we need the double factorial:

$$
m!! = m (m-2) (m-4) \cdots
$$

Thus:

$$
\int_{0}^{\frac{\pi}{2}} \sin^{2k} x \, dx = \frac{(2k-1)!!}{(2k)!!} \cdot \frac{\pi}{2}
$$

$$
\int_{0}^{\frac{\pi}{2}} \sin^{2k+1} x \, dx = \frac{(2k)!!}{(2k+1)!!}
$$

Since $\sin^{2k+1} x < \sin^{2k} x < \sin^{2k-1} x$ for $x \in (0, \frac{\pi}{2})$, we have:

$$
\int_{0}^{\frac{\pi}{2}} \sin^{2k+1} x \, dx < \int_{0}^{\frac{\pi}{2}} \sin^{2k} x \, dx < \int_{0}^{\frac{\pi}{2}} \sin^{2k-1} x \, dx
$$

Substituting the above formulas:

$$
\frac{(2k)!!}{(2k+1)!!} < \frac{(2k-1)!!}{(2k)!!} \cdot \frac{\pi}{2} < \frac{(2k-2)!!}{(2k-1)!!}
$$

We can examine the difference between the bounds for $\int_{0}^{\frac{\pi}{2}} \sin^{2k} x \, dx$:

$$
\lim_{k \rightarrow \infty} \left( \frac{(2k-2)!!}{(2k-1)!!} - \frac{(2k)!!}{(2k+1)!!} \right) \\ = \lim_{k \rightarrow \infty} \left( \frac{(2k-2)!!}{(2k-1)!!} - \frac{2k}{2k+1} \cdot \frac{(2k-2)!!}{(2k-1)!!} \right) \\ = \lim_{k \rightarrow \infty} \frac{1}{2k+1} \cdot \frac{(2k-2)!!}{(2k-1)!!} = 0
$$

Note: Here $\frac{2k-2}{2k-1} < 1$

For the inequality:

$$
\frac{(2k)!!}{(2k+1)!!} < \frac{(2k-1)!!}{(2k)!!} \cdot \frac{\pi}{2} < \frac{(2k-2)!!}{(2k-1)!!}
$$

Multiply all terms by $\frac{(2k)!!}{(2k-1)!!}$:

$$
\frac{(2k)!!^2}{(2k+1)!! (2k-1)!!} < \frac{\pi}{2} < \frac{(2k-2)!! (2k)!!}{(2k-1)!!^2}
$$

We can further examine the difference between the bounds for $\frac{\pi}{2}$:

$$
\lim_{k \rightarrow \infty} \left( \frac{(2k-2)!! (2k)!!}{(2k-1)!!^2} - \frac{(2k)!!^2}{(2k+1)!! (2k-1)!!} \right) \\= \lim_{k \rightarrow \infty} \left( \frac{1}{2k} - \frac{1}{2k+1} \right) \cdot \frac{(2k)!!^2}{(2k+1)!! (2k-1)!!} \\= \lim_{k \rightarrow \infty} \frac{1}{2k} \cdot \frac{(2k)!!^2}{(2k+1)!!^2} = 0
$$

Thus, we obtain **Wallis's Formula**:

$$
\lim_{k \rightarrow \infty} \frac{(2k)!!^2}{(2k+1)!! (2k-1)!!} = \frac{\pi}{2}
$$

**This formula introduces Wallis's result in preparation for deriving Stirling's formula.**

## Stirling's Formula

Stirling's formula reveals a relationship between $n!$, $n^n$, and $e^n$.

> As $n$ approaches infinity, $n!$ is approximately $\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$.

First, introduce a limit:

$$
\lim_{n \rightarrow \infty} \left( \frac{n!}{n^n} \right)^{\frac{1}{n}} = \frac{1}{e}
$$

Proof:

$$
\lim_{n \rightarrow \infty} \left( \frac{n!}{n^n} \right)^{\frac{1}{n}} = \lim_{n \rightarrow \infty} e^{\frac{1}{n} \ln \left( \frac{n!}{n^n} \right)}
$$

which is equivalent to proving:

$$
\lim_{n \rightarrow \infty} \frac{1}{n} \ln \left( \frac{n!}{n^n} \right) = -1
$$

We have:

$$
\lim_{n \rightarrow \infty} \frac{1}{n} \ln \left( \frac{n!}{n^n} \right) \\ = \lim_{n \rightarrow \infty} \frac{1}{n} \left( \ln \frac{1}{n} + \ln \frac{2}{n} + \cdots + \ln \frac{n}{n} \right) \\ = \int_{0}^{1} \ln x \, dx = (x \ln x - x) \Big|_{0}^{1} = -1
$$

QED.

Thus,

$$
\frac{n!}{n^n} \sim \frac{1}{e^n}
$$

We would like to verify:

$$
\lim_{n \rightarrow \infty} \frac{n!}{n^n} e^n = 1
$$

Let’s test this.

**Using the ratio test:**

$$
a_n = \frac{n!}{n^n} e^n, \quad a_{n+1} = \frac{(n+1)!}{(n+1)^{n+1}} e^{n+1}
$$

$$
\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \frac{e}{\left(1 + \frac{1}{n}\right)^n} > 1
$$

Although the limit of the expression is $e$, it is always approaching $e$ from below, so it is still greater than 1, indicating that $a_n$ is divergent.

Mathematicians have attempted various approaches and found:

$$
a_n = \frac{n!}{n^{n + \frac{1}{2}}} e^n
$$

To prove that $a_n$ converges, use the **ratio test** again:

$$
a_n = \frac{n!}{n^{n + \frac{1}{2}}} e^n, \quad a_{n+1} = \frac{(n+1)!}{(n+1)^{n + \frac{3}{2}}} e^{n+1}
$$

$$
\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \frac{e}{\left(1 + \frac{1}{n}\right)^{n + \frac{1}{2}}}
$$

Compare this with:

$$
\left(1 + \frac{1}{n}\right)^{n + \frac{1}{2}} = e^{(n + \frac{1}{2}) \ln \left(1 + \frac{1}{n}\right)}
$$

and $e$.

Thus, compare:

$$
(n + \frac{1}{2}) \ln \left(1 + \frac{1}{n}\right)
$$

with 1.

Specifically, compare $\ln \frac{n+1}{n}$ with $\frac{1}{n + \frac{1}{2}}$:

Since:

$$
\frac{1}{n + 1} < \ln \left(1 + \frac{1}{n}\right) < \frac{1}{n}
$$

**Note:** The right side follows from the inequality $\ln(1 + x) < x$ (for $x \neq 0$).

**The left side follows from:** $1 - \frac{n}{n+1} < \ln \left(\frac{n+1}{n}\right)$, where $\frac{n}{n+1}$ is considered as a whole. This is high school knowledge.

Because $\frac{1}{x}$ is a concave function:

$$
\int_{n}^{n+1} \frac{1}{x} \, dx = \ln \frac{n+1}{n} > \frac{1}{n + \frac{1}{2}}
$$

Therefore:

$$
\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \frac{e}{\left(1 + \frac{1}{n}\right)^{n + \frac{1}{2}}} < 1
$$

Thus, $a_n$ is monotonically decreasing and $a_n > 0$, so it must converge, i.e., it has a limit.

Let:

$$
\lim_{n \rightarrow \infty} \frac{n!}{n^{n + \frac{1}{2}}} e^n = a
$$

Then, we need to find this limit.

From the earlier Wallis formula:

$$
\lim_{k \rightarrow \infty} \frac{(2k)!!^2}{(2k+1)!! (2k-1)!!} = \frac{\pi}{2}
$$

$$
(2n)!! = 2n (2n-2) \cdots 2 = 2^n n!
$$

$$
(2n-1)!! = \frac{(2n)!}{(2n)!!} = \frac{(2n)!}{2^n n!}
$$

$$
(2n+1)!! = \frac{(2n+2)!}{(2n+2)!!} = \frac{(2n+2)!}{2^{n+1} (n+1)!}
$$

Thus, Wallis' formula becomes:

$$
\lim_{n \rightarrow \infty} \frac{16^n (n!)^4 (2n+2)}{(2n)!(2n+2)!} = \frac{\pi}{2}
$$

Using:

$$
n! \sim a e^{-n} n^{n + \frac{1}{2}}
$$

Substitute into:

$$
\lim_{n \rightarrow \infty} \frac{a^2 e^2}{4 \left(\frac{n+1}{n}\right)^{2n + \frac{3}{2}}} = \frac{\pi}{2}
$$

Solve for:

$$
a = \sqrt{2 \pi}
$$

Thus, as $n$ approaches infinity:

$$
n! \sim \sqrt{2 \pi} e^{-n} n^{n + \frac{1}{2}}
$$

or equivalently:

$$
n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n
$$


Stirling's formula finds a relationship of n!,nⁿ,eⁿ while n trends to infinity.

The Stirling Formula


## Content

The Box-Muller transform is a method used to generate normally distributed random variables from uniformly distributed random variables.

Specifically, it involves selecting two random variables, $U_1$ and $U_2$, which are uniformly distributed over the interval $[0,1]$. The random variables $X$ and $Y$ are constructed as follows:

$$
X = \cos(2\pi U_1) \sqrt{-2\ln U_2}
$$

$$
Y = \sin(2\pi U_1) \sqrt{-2\ln U_2}
$$

Then, $X$ and $Y$ follow a normal distribution with a mean of 0 and a variance of 1.

## Derivation

Assume that $X$ and $Y$ are independent, normally distributed random variables with a mean of 0 and a variance of 1. Let $p(X)$ and $p(Y)$ be their probability density functions. Thus, we have:

$$
p(X) = \frac{1}{\sqrt{2\pi}} e^{-\frac{X^2}{2}}, \\ p(Y) = \frac{1}{\sqrt{2\pi}} e^{-\frac{Y^2}{2}}
$$

Since $X$ and $Y$ are independent, their joint probability density function is:

$$
p(X,Y) = \frac{1}{2\pi} e^{-\frac{X^2 + Y^2}{2}}
$$

We now perform a coordinate transformation by defining:

$$
X = R \cos(\theta), \\ Y = R \sin(\theta)
$$

Thus, the joint distribution in polar coordinates becomes:

$$
\int_{0}^{\infty} \int_{0}^{2\pi} \frac{1}{2\pi} e^{-\frac{R^2}{2}} R \, d\theta \, dR = 1
$$

From this, we can derive the distribution functions for $R$ and $\theta$, denoted as $P_R$ and $P_\theta$:

$$
P_R(R \leq r) = \\ \int_{0}^{r} \int_{0}^{2\pi} \frac{1}{2\pi} e^{-\frac{R^2}{2}} R \, d\theta \, dR = 1 - e^{-\frac{r^2}{2}}
$$

$$
P_\theta(\theta \leq \phi) = \\ \int_{0}^{\phi} \int_{0}^{\infty} \frac{1}{2\pi} e^{-\frac{R^2}{2}} R \, dR \, d\theta = \frac{\phi}{2\pi}
$$

It is evident that $\theta$ follows a uniform distribution over $[0, 2\pi]$. Let

$$
F_R = 1 - e^{-\frac{r^2}{2}}
$$

The inverse function is given by:

$$
R = F_R^{-1}(z) \\ = \sqrt{-2 \ln(1 - z)}
$$

When $z$ is uniformly distributed over $[0,1]$, the distribution function of $R$ is $F_R(r)$. Therefore, we can select two random variables $U_1$ and $U_2$, uniformly distributed over $[0,1]$, such that:

$$
\theta = 2\pi U_1, \\ 1 - z = U_2, \\ R = \sqrt{-2 \ln U_2}
$$

Substituting these into the earlier expressions, we obtain:

$$
X = R \cos(\theta), \\ Y = R \sin(\theta)
$$

Thus, the original expressions for $X$ and $Y$ are recovered, where they follow a normal distribution with mean 0 and variance 1.

## Verification

To generate a random variable $X \sim N(0,1)$ following a standard normal distribution, we note that the inverse of the error function $\mathrm{erf}^{-1}$ is not elementary. Using a series expansion to approximate this inverse can introduce significant computational error.

Elementary functions, on the other hand, have well-established high-precision algorithms. Thus, we aim to construct a normally distributed random variable from a uniformly distributed one using elementary functions.

Let $U, V \in (0,1)$ be uniformly distributed random variables. Consider the following transformations:

$$
X = \sqrt{-2\ln U} \cos(2\pi V), \\ Y = \sqrt{-2\ln U} \sin(2\pi V)
$$

Next, we verify that $X$ and $Y$ are independent and follow a standard normal distribution.

Define:

$$
R = \sqrt{X^2 + Y^2}, \\ \Theta = \arctan\left(\frac{Y}{X}\right)
$$

Note that $\Theta = 2\pi V$ and $R = \sqrt{-2\ln U}$. We now show that $R$ and $\Theta$, under the polar coordinate transformation, are independent and that they yield standard normal random variables.

Consider the probability density function of one variable when the other

is fixed. The probability density function of $\Theta$ is:

$$
P_\Theta(\Theta) = \frac{1}{2\pi}
$$

which is straightforward. For $R$, the cumulative distribution function is:

$$
P(R \leq R_0) = \\ P\left(U \leq \exp\left(\frac{-R_0^2}{2}\right)\right)
$$

Thus, the probability density function of $R$ is:

$$
P_R(R) = R e^{-\frac{R^2}{2}}
$$

Hence, the joint probability density of $R$ and $\Theta$ is:

$$
P(R, \Theta) = \frac{1}{2\pi} R e^{-\frac{R^2}{2}}
$$

Since the polar coordinates yield:

$$
R \, dR \, d\Theta = dX \, dY
$$

we obtain the joint probability density of $X$ and $Y$:

$$
P(X,Y) = \frac{1}{2\pi} e^{-\frac{X^2 + Y^2}{2}} \\ = \left(\frac{1}{\sqrt{2\pi}} e^{-\frac{X^2}{2}}\right) \left(\frac{1}{\sqrt{2\pi}} e^{-\frac{Y^2}{2}}\right)
$$

This is precisely the probability density function of two independent, normally distributed random variables $X$ and $Y$, each following a standard normal distribution.

## Code Implementation

```typescript
function randInterval(): number {
  return Math.random();
}

function boxMuller(mu: number, sigma: number): [number, number] {
  const u = randInterval();
  const v = randInterval();
  const x = Math.cos(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  const y = Math.sin(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  return [x * sigma + mu, y * sigma + mu];
}

// Usage example
const [value1, value2] = boxMuller(0, 1);
console.log(value1, value2);
// Outputs two normally distributed random numbers
```

To verify that the `boxMuller` function generates numbers that follow a normal distribution, one can generate a large set of random numbers and plot a histogram to compare with a standard normal distribution. You can use libraries such as `plotly` to visualize the histogram and evaluate the output.

Here is a test program that generates a dataset using the `boxMuller` function and performs basic statistical tests, along with plotting the histogram. Assuming you are running in a Node.js environment, you can use `plotly-nodejs` or directly use `plotly.js` in the browser to generate the graph.

First, install the required dependencies:

```bash
npm i plotly.js-dist
```

Then, execute the following code:

```typescript
import * as fs from "fs";
import * as plotly from "plotly.js-dist";

// Generate random numbers following a normal distribution using Box-Muller
function randInterval(): number {
  return Math.random();
}

function boxMuller(mu: number, sigma: number): [number, number] {
  const u = randInterval();
  const v = randInterval();
  const x = Math.cos(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  const y = Math.sin(2 * Math.PI * u) * Math.sqrt(-2 * Math.log(v));
  return [x * sigma + mu, y * sigma + mu];
}

// Generate n normally distributed random numbers
function generateNormalDistribution(
  mu: number,
  sigma: number,
  n: number
): number[] {
  const values: number[] = [];
  for (let i = 0; i < n / 2; i++) {
    const [value1, value2] = boxMuller(mu, sigma);
    values.push(value1, value2);
  }
  return values;
}

// Generate the data
const mu = 0;
const sigma = 1;
const sampleSize = 10000; // Sample size
const values = generateNormalDistribution(mu, sigma, sampleSize);

// Calculate the mean and variance of the generated random numbers
const mean = values.reduce((acc, val) => acc + val, 0) / values.length;
const variance =
  values.reduce((acc, val) => acc + (val - mean) ** 2, 0) / values.length;

console.log(`Mean: ${mean}`);
console.log(`Variance: ${variance}`);

// Plot the histogram
const trace = {
  x: values,
  type: "histogram",
  xbins: {
    size: 0.1, // Bin size for the histogram
  },
  marker: {
    color: "blue",
  },
  opacity: 0.7,
  name: "Box-Muller Distribution",
};

const data = [trace];

const layout = {
  title: "Generated Normal Distribution",
  xaxis: { title: "Value" },
  yaxis: { title: "Frequency" },
  bargap: 0.05,
};

const graphOptions = {
  filename: "box-muller-distribution",
  fileopt: "overwrite",
};
fs.writeFileSync("box-muller.html", plotly.plot(data, layout, graphOptions));

console.log("Box-Muller distribution data saved as box-muller.html.");
```

This program uses the `boxMuller` function to generate 10,000 random numbers that follow a normal distribution. It calculates the mean and variance of the generated dataset. The random numbers are visualized using a histogram, allowing for a direct comparison with a standard normal distribution. The histogram is saved as a file named `box-muller.html`, which can be opened in a browser for viewing.


The Box-Muller transformation is a method to construct a random variable that follows a Gaussian distribution by using a random variable that follows a uniform distribution.

Box-Muller Transformation


## Algorithm Overview

Programmers are generally familiar with random numbers, and it is well-known that the random numbers generated by computers are often pseudo-random. What exactly is a pseudo-random sequence?

> **Pseudo-random numbers** are a sequence of numbers that appear random but are generated using a **deterministic** algorithm, meaning they are not truly random.

Since randomness is simulated through an algorithm, what kind of algorithm can achieve an effect close to true randomness, and how does it work?

One of the simpler methods is the linear congruential generator (LCG).

The LCG is based on the recursive formula:

$$
N_{j+1} = (A * N_{j} + B) \% M
$$

The most important elements in the LCG are three integers: the multiplier $A$, the increment $B$, and the modulus $M$.

These values, $A$, $B$, and $M$, are constants set by the generator. The period of the LCG is at most $M$, though in most cases, it will be less than $M$. To achieve the maximum period, the following conditions must be met:

- $B$ and $M$ are coprime;
- All prime factors of $M$ divide $A-1$;
- If $M \% 4 = 0$, then $A-1$ must also be divisible by 4;
- $A$, $B$, and $N_{0}$ must be smaller than $M$, and $A$, $B$ must be positive integers.

The advantage of the LCG is that it is **very easy to implement and generates numbers quickly**. However, its drawback is also clear: for a 32-bit number, the maximum period is limited to $2^{32}$, which is inadequate for applications that require high-quality random numbers, such as cryptography.

## Randomness Analysis

With this understanding, one might wonder, how does the LCG simulate a random process? True randomness implies that any number can appear, meaning **all outcomes are equally probable, following a uniform distribution**. So, how does the LCG achieve uniform distribution?

First, we need to understand the period of the LCG. From the definition above, it is clear that for a modulus $M$, the sequence generated by the LCG has a maximum period of $M$. Suppose the recursive formula is $N_{j+1} = (A * N_{j} + B) \mod M$. If the period is $T$, then $N_{k+T} = N_{k}$, and since $N_{k+1} = (A * N_{k} + B) \mod M$, this implies that each value of $N_{k}$ uniquely determines the value of $N_{k+1}$. Thus, the period $T$ must be less than or equal to $M$, because there are only $M$ possible distinct integers when taken modulo $M$. The $(M+1)$-th number will necessarily be the same as one of the previous numbers, and since the recursive relationship is one-to-one, the subsequent sequence will repeat, leading to a period $T \leq M$.

Next, it is important that the multiplier and modulus be coprime. This is easy to understand: consider $N_{j+1} = (A * N_{j} + B) \mod M$. If $A$ and $M$ are not coprime, suppose $A = a * d$ and $M = m * d$ where $d > 1$. Expanding the recursive formula yields $N_{j+1} = A * N_{j} + B + k * M$. Since $B$ is constant, it can be treated as a shift, and by subtracting $B$ from both sides, we get $N_{j+1} - B = (a * (N_{j} - B) + a * B + k * m) * d$. This shows that all values of $N_{j+1} - B$ contain the factor $d$. For example, if $d = 2$, the sequence of $M$ possible numbers will only yield even numbers plus the shift $B$, meaning the period $T \leq M / 2$. This disrupts the uniform distribution of the sequence.

A few simple examples can illustrate this. Suppose $A = 3$, $M = 5$, and $N_0 = 2$, the sequence would be $\{2, 1, 3, 4, 2, 1, \dots\}$, with a period of 5. If we set $A = 6$, $M = 10$, and $N_0 = 2$, the sequence would be $\{2, 2, 2, \dots\}$, with a period of 1.

Returning to the initial question, how does the LCG achieve uniform distribution? As seen from the discussion above, with carefully chosen parameters, it is possible to construct a sequence with a period of $M$, where each number appears exactly once in each cycle. This ensures that the frequency of appearance for each number in the sequence is the same, thus satisfying the uniform distribution requirement.

## Solving Linear Congruences

Having understood the relationship between random distribution and the linear congruential method, let's extend our knowledge to learn how to solve linear congruences. This is not just a theoretical mathematical problem; it has numerous practical applications. For instance:

> On a circular track, two frogs, $A$ and $B$, start from positions $x$ and $y$ respectively, with $A$ jumping $m$ units and $B$ jumping $n$ units each time. The total circumference of the track is $L$. If both frogs start at the same time, they are said to meet if they land on the same point. The question is, after how many jumps will the two frogs meet at the earliest?

Based on these conditions, we can formulate the following equation:

$$
(x + m*k) ≡ (y + n*k) \pmod{L}
$$

Where $≡$ denotes congruence modulo $L$.

Expanding this gives:

$$
x + m*k = y + n*k + L*k'
$$

Rearranging terms, we get:

$$
x - y = (n - m)*k + L*k'
$$

Thus,

$$
(x - y) ≡ (n - m)*k \pmod{L}
$$

Let $n - m = a$ and $x - y = b$, \
yielding the standard linear congruence:

$$
a*k ≡ b \pmod{L}
$$

> Definition: If $a$ and $b$ are integers, the expression $a*x ≡ b \pmod{M}$, where $x$ is an unknown integer, is called a linear congruence. Here, $≡$ and $(\pmod{M})$ indicate that both sides are taken modulo $M$.

To solve a linear congruence, we proceed with the following transformations:

1. The standard linear congruence $a*x ≡ b \pmod{M}$ is equivalent to the Diophantine equation $a*x + M*y = b$.
2. Let $d$ be the greatest common divisor (gcd) of $a$ and $M$, denoted $gcd(a,M) = d$. If the equation has a solution, $d$ must divide $b$. We rewrite the equation as $a_0*x + M_0*y = b_0$, where $a = a_0*d$, $M = M_0*d$, and $b = b_0*d$. Here, $a_0$ and $M_0$ are coprime, meaning $gcd(a_0, M_0) = 1$.
3. Let $x = x_0*b_0$ and $y = y_0*b_0$. The equation becomes $a_0*x_0 + M_0*y_0 = 1$, or equivalently $a_0*x_0 ≡ 1 \pmod{M_0}$.

Finally, we use modular inversion to compute $x_0$.

> **Theorem:** If $a$ and $M$ are coprime integers and $M > 1$, there exists a unique inverse of $a$ modulo $M$.

This theorem can be proven as follows:

Since $a$ and $M$ are coprime, there exist integers $s$ and $t$ such that $s*a + t*M = 1$. (If $a$ and $M$ have a common divisor $d > 1$, then $s*a + t*M = d*k$, which cannot equal 1). Taking the equation modulo $M$, we get $s*a ≡ 1 \pmod{M}$. Thus, $s$ is the modular inverse of $a$ modulo $M$.

Let $\bar{a}$ denote the modular inverse of $a$ modulo $M$, so $x_0 ≡ \bar{a} \pmod{M_0}$, meaning $x_0 ≡ \bar{a} + k*M_0$.

For example:

To solve $5*x ≡ 7 \pmod{9}$:

1. Since $gcd(5,9) = 1$, we know that $5$ has an inverse modulo $9$. Using the extended Euclidean algorithm, we find $2*5 + (-1)*9 = 1$.
2. Therefore, $2$ is the inverse of $5$ modulo $9$. Multiplying both sides of the original equation by $2$ gives $2*5*x ≡ 2*7 \pmod{9}$.
3. Simplifying, we get $x ≡ 14 \pmod{9} ≡ 5 \pmod{9}$.
4. Thus, the solution is $x = 5 + 9k$.

In summary, we can solve a general linear congruence $a*x ≡ b \pmod{L}$ by transforming it into a standard congruence $a_0*x_0 ≡ 1 \pmod{M_0}$. After solving the standard congruence, we map the solution back. If the solution to the standard equation is $x_0 \in \{x = p + q*M_0\}$, then the solution to the original equation is $x \in \{x = \frac{b}{d}*p + q'*M_0\}$.

Through this, we have outlined the process of solving linear congruences and deepened our understanding of the linear congruential method.

## Insecurity of the Linear Congruential Method

The linear congruential method (LCG) is a pseudo-random number generation technique based on deterministic mathematical algorithms. Although it can meet the needs for general pseudo-random numbers, it is not suitable for high-security applications, such as cryptography or applications requiring strong randomness. Below are some key considerations regarding the insecurity of LCG:

1. **Determinism**: LCG is deterministic, meaning that the same seed and parameters will always produce the same sequence of random numbers. This poses a security risk, as an attacker could reproduce the sequence by guessing the seed and parameters, breaking the randomness.
2. **Periodicity**: The random number sequences generated by LCG are periodic. Once the sequence reaches its period, it starts repeating. This periodicity can cause problems in applications that require long-term randomness.
3. **Non-uniformity**: In some cases, LCG-generated sequences may not be uniformly distributed, especially when parameters are poorly chosen, leading to statistical biases.
4. **Security**: LCG is unsuitable for cryptographic or high-randomness security applications. For such use cases, cryptographically secure pseudo-random number generators (CSPRNGs) must be employed.

In conclusion, while LCG can be used for general pseudo-random number generation in simulations, games, or random testing, it should not be used in applications that require high security and strong randomness.

## Code Implementation

Below is the implementation of a Linear Congruential Generator (LCG) using TypeScript, along with a simple program to test the effectiveness of its randomness.

### LCG Implementation

```typescript
class LinearCongruentialGenerator {
  private seed: number;
  private readonly a: number;
  private readonly c: number;
  private readonly m: number;

  constructor(
    seed: number,
    a: number = 1664525,
    c: number = 1013904223,
    m: number = 2 ** 32
  ) {
    this.seed = seed;
    this.a = a;
    this.c = c;
    this.m = m;
  }

  public next(): number {
    this.seed = (this.a * this.seed + this.c) % this.m;
    return this.seed;
  }

  public nextFloat(): number {
    return this.next() / this.m;
  }
}

// Example usage
const lcg = new LinearCongruentialGenerator(12345);
console.log(lcg.next());
// Outputs a random integer
console.log(lcg.nextFloat());
// Outputs a random floating-point number between 0 and 1
```

### Code to Test Randomness

We can test the randomness of the generator by generating a set of random numbers and plotting their distribution. Below is a simple test program:

```typescript
function testRandomness(
  generator: LinearCongruentialGenerator,
  iterations: number = 10000
): void {
  const results: number[] = new Array(10).fill(0);

  for (let i = 0; i < iterations; i++) {
    const randomValue = Math.floor(generator.nextFloat() * 10);
    results[randomValue]++;
  }

  console.log("Randomness Test Results:");
  results.forEach((count, index) => {
    console.log(`${index}: ${"*".repeat(count / 100)}`);
  });
}

// Example usage
const lcgTest = new LinearCongruentialGenerator(12345);
testRandomness(lcgTest);
```

This test program generates a set of random numbers and counts the occurrences of each number. By observing the distribution of the output, we can make an initial assessment of the randomness of the generator.


Linear congruential method is a pseudo-random number generation method that generates a random number sequence based on a deterministic mathematical algorithm.

Linear Congruential for Pseudorandom Number


**Definition ($k$-th Order Minor):** In an $n$-th order determinant $D$, a $k$-th order minor $M$ is a $k \times k$ determinant formed by selecting any $k$ rows and $k$ columns from $D$ ($k \le n$), and taking the $k^2$ elements at the intersections of these rows and columns in their original order.

When $k < n$, after removing these $k$ rows and $k$ columns from $D$, the remaining $(n-k)$-th order determinant $M'$ formed by the leftover elements is called the cofactor of the $k$-th order minor $M$.

**Example:**

$$
D=\begin{vmatrix}  a_{11} & a_{12} & a_{13} & a_{14} & a_{15}\\  a_{21} & a_{22} & a_{23} & a_{24} & a_{25}\\ \vdots   & \vdots  & \vdots  & \vdots  & \vdots \\ a_{51} & a_{52} & a_{53} & a_{54} & a_{55} \end{vmatrix}, \\ M=\begin{vmatrix} a_{12}  & a_{13} & a_{15} \\ a_{22}  &  a_{23} & a_{25} \\ a_{42}  & a_{43} & a_{45} \end{vmatrix}, \\ M'=\begin{vmatrix} a_{31} & a_{34} \\ a_{51} & a_{54} \end{vmatrix}
$$

**Note:** In the above example, the algebraic cofactor of $M$ is

$$
(-1)^{(1+2+4)+(2+3+5)}M'=-M'
$$

**Definition (Algebraic Cofactor):** Let $M$ be a $k$-th order minor of $D$ with row and column indices $i_{1},i_{2},\cdots,i_{k}; \ j_{1},j_{2},\cdots,j_{k}$, respectively. The cofactor $M'$ of $M$ is multiplied by the sign $(-1)^{(i_{1}+i_{2}+\cdots+i_{k})+(j_{1}+j_{2}+\cdots+j_{k})}$ to form the algebraic cofactor of $M$.

**Lemma:** Every term in the product of any minor $M$ of determinant $D$ and its algebraic cofactor $A$ corresponds to a term in the expansion of determinant $D$, with the same sign.

**Proof:** First, consider the case where $M$ is located in the upper-left corner of determinant $D$:

$$
\begin{vmatrix}  a_{11} & a_{12} & \cdots & a_{1k} & |& a_{1,k+1} & \cdots & a_{1n}\\  \vdots

& \vdots & M & \cdots & | & \vdots &  &\vdots \\  a_{k1} & a_{k2} &\cdots  &  a_{kk}& | & a_{k,k+1} & \cdots & a_{kn}\\ -&- &- &- &-|-&- &- &- \\   a_{k+1,1}& a_{k+1,2} &\cdots  & a_{k+1,k} &  |& a_{k+1,k+1} & \cdots & a_{k+1,n}\\  \vdots & \vdots &  &  \vdots&  |& \vdots & M' & \vdots\\  a_{n1} & a_{n2} & \cdots & a_{nk} &  |& a_{n,k+1} & \cdots & a_{nn}\end{vmatrix}
$$

In this case, the algebraic cofactor of $M$ is:

$$
A=(-1)^{(1+2+\cdots +k)+(1+2+\cdots+k)}M'=M'
$$

Each term in $M$ can be written as $a_{1\alpha_{1}}a_{2\alpha_{2}}\cdots a_{k\alpha_{k}}$, where $\alpha_{1}\alpha_{2}\cdots\alpha_{k}$ is a permutation of $1,2,\cdots,k$. The sign of this term is $(-1)^{\tau(\alpha_1 \alpha_2\cdots\alpha_k)}$.

Each term in $M'$ can be written as $a_{k+1,\beta_{k+1}}a_{k+2,\beta_{k+2}}\cdots a_{n\beta_{n}}$, where $\beta_{k+1}\beta_{k+2}\cdots\beta_{n}$ is a permutation of $k+1,k+2,\cdots,n$, and its sign is $(-1)^{\tau((\beta_{k+1}-k)(\beta_{k+2}-k)\cdots(\beta_{n}-k))}$.

The product of these two terms is $a_{1\alpha_{1}}a_{2\alpha_{2}}\cdots a_{k\alpha_{k}}a_{k+1,\beta_{k+1}}\cdots a_{n\beta_{n}}$, and the combined sign is:

$$
(-1)^{\tau(\alpha_{1}\alpha_{2}\cdots\alpha_{k})+\tau((\beta_{k+1}-k)(\beta_{k+2}-k)\cdots(\beta_{n}-k))}= (-1)^{\tau(\alpha_{1}\alpha_{2}\cdots \alpha_{k}\beta_{k+1}\cdots \beta_{n}) }
$$

Thus, this product is a term in the expansion of determinant $D$ with the same sign.

Now, we will prove the general case.

Let minor $M$ be located in rows $i_1, i_2, \cdots, i_k$ and columns $j_1, j_2, \cdots, j_k$ of $D$, where $i_1 < i_2 < \cdots < i_k$, and $j_1 < j_2 < \cdots < j_k$.

We rearrange the rows and columns of determinant $D$ such that $M$ is moved to the top-left corner.

First, swap the $i_1$-th row with rows $i_1-1, i_1-2, \cdots, 2, 1$, which takes $i_1-1$ swaps to move the $i_1$-th row to the first row. Then, swap the $i_2$-th row $i_2-2$ times to move it to the second row, and so on. In total, this requires

$$
(i_1-1)+(i_2-2)+\cdots+(i_k-k)=(i_1+i_2+\cdots+i_k)-(1+2+\cdots+k)
$$

row swaps to move rows $i_1, i_2, \cdots, i_k$ to rows $1, 2, \cdots, k$.

Using similar column swaps, we move the columns of $M$ to columns $1, 2, \cdots, k$, requiring

$$
(j_1-1)+(j_2-2)+\cdots+(j_k-k)=(j_1+j_2+\cdots+j_k)-(1+2+\cdots+k)
$$

column swaps.

Let $D_1$ denote the new determinant after these transformations. We have:

$$
D_1 = (-1)^{(i_1+i_2+\cdots+i_k)-(1+2+\cdots+k)+(j_1+j_2+\cdots+j_k)-(1+2+\cdots+k)}D \\ = (-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}D
$$

Thus, the expansion of $D_1$ contains the same terms as that of $D$, but with each term having a sign difference of $(-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}$.

Now, $M$ is located in the top-left corner of $D_1$, and the cofactor and algebraic cofactor of $M$ in $D_1$ are both $M'$. Therefore, each term in the product $MM'$ corresponds to a term in $D_1$ with the same sign.

The algebraic cofactor $A$ of $M$ in $D$ gives $MA = (-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}MM'$, which is a term in $D_1$ with a sign difference of $(-1)^{i_1+i_2+\cdots+i_k+j_1+j_2+\cdots+j_k}$. Hence, $MA$ is a term in $D$ with the same sign.

**Theorem (Laplace's Theorem):** For any $k$ ($1 \le k \le n-1$) rows chosen from determinant $D$, the sum of the products of all $k$-th order minors formed from these rows and their respective algebraic cofactors equals the determinant $D$.

**Proof:** Let the minors formed from the chosen $k$ rows of $D$ be $M_1, M_2, \cdots, M_t$, with algebraic cofactors $A_1, A_2, \cdots, A_t$. The theorem claims that:

$$
D = M_1A_1 + M_2A_2 + \cdots + M_tA_t
$$

where

$$
t = \text{C}_{n}^{k} = \dfrac{n!}{k!(n-k)!}
$$

By the lemma, each term in $M_iA_i$ corresponds to a term in $D$ with the same sign, and there are no common terms between $M_iA_i$ and $M_jA_j$ ($i \ne j$).

The left-hand side of the equation contains $n!$ terms, and the right-hand side contains

$$\sum\limits_{i=1}^{t}k!(n-k)! = k!(n-k)!\dfrac{n!}{k!(n-k)!} = n!$$

terms. Hence, the theorem is proven.

**Example:** In the determinant $D=\begin{vmatrix} 1  & 2 & 1 &4 \\  0 & -1 & 2 & 1\\  1 & 0 & 1 & 3\\ 0  &  1& 3 & 1\end{vmatrix}$, selecting the first two rows yields six minors:

$$
M_{1}= \begin{vmatrix}   1& 2\\  0 &-1 \end{vmatrix}=-1, \quad M_{2}= \begin{vmatrix}  1 &1 \\   0& 2\end{vmatrix}=2, \quad M_{3}= \begin{vmatrix} 1  & 4\\  0 &1 \end{vmatrix}=1,
$$

$$
M_{4}= \begin{vmatrix}   2& 1\\   -1&2 \end{vmatrix}=5, \quad M_{5}= \begin{vmatrix}   2& 4\\  -1 &1 \end{vmatrix}=6, \quad M_{6}= \begin{vmatrix}   1& 4\\   2&1 \end{vmatrix}=-7.
$$

Their algebraic cofactors are:

$$
A_1=-8, \quad A_2=3, \quad A_3=-1, \quad A_4=1, \quad A_5=-3, \quad A_6=1 \Rightarrow D=-7.
$$

**Theorem:** The product of two $n$-order determinants

$$
D_{1}=\begin{vmatrix}  a_{11} & a_{12} & \cdots &a_{1n} \\ a_{21}  &a_{22}  &\cdots  & a_{2n}\\ \vdots  & \vdots &  &\vdots \\  a_{n1} & a_{n2} &\cdots  & a_{nn}\end{vmatrix}, \\ D_{2}=\begin{vmatrix}  b_{11} & b_{12} & \cdots &b_{1n} \\ b_{21}  &b_{22}  &\cdots  & b_{2n}\\ \vdots  & \vdots &  &\vdots \\  b_{n1} & b_{n2} &\cdots  & b_{nn}\end{vmatrix}
$$

is equal to a determinant

$$
C = \begin{vmatrix}  c_{11} &c_{12} & \cdots &c_{1n} \\ c_{21}  &c_{22}  &\cdots  & c_{2n}\\ \vdots  & \vdots &  &\vdots \\  c_{n1} & c_{n2} &\cdots  & c_{nn}\end{vmatrix}
$$

where each element $c_{ij}$ is the sum of the products of elements from the $i$-th row of $D_1$ and the corresponding elements from the $j$-th row of $D_2$,

i.e.

$$
c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.
$$

**Proof:** Construct a $2n$-order determinant

$$
D = \begin{vmatrix}  a_{11} & a_{12} & \cdots &a_{1n} &0&0&0&0\\ a_{21}  &a_{22}  &\cdots  & a_{2n}&0&0&0&0\\ \vdots  & \vdots &  &\vdots &0&0&0&0\\  a_{n1} & a_{n2} &\cdots  & a_{nn} &0&0&0&0\\ -1&0&\cdots &0&b_{11}&b_{12}&\cdots&b_{1n}\\ 0&-1&\dotso&0&b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots & \vdots & &\vdots&\vdots & \vdots &&\vdots \\ 0&0&\cdots&-1 &b_{n1}&b_{n2}&\cdots &b_{nn} \end{vmatrix}
$$

According to Laplace's theorem, expanding $D$ by the first $n$ rows, all of the minors formed by the first $n$ rows and other elements will be zero except for the minor at the top left, so

$$
D = \begin{vmatrix}  a_{11} & a_{12} & \cdots &a_{1n} \\ a_{21}  &a_{22}  &\cdots  & a_{2n}\\ \vdots  & \vdots &  &\vdots \\  a_{n1} & a_{n2} &\cdots  & a_{nn}\end{vmatrix}\cdot \begin{vmatrix}  b_{11} & b_{12} & \cdots &b_{1n} \\ b_{21}  &b_{22}  &\cdots  & b_{2n}\\ \vdots  & \vdots &  &\vdots \\  b_{n1} & b_{n2} &\cdots  & b_{nn}\end{vmatrix}=D_1D_2.
$$

Next, we show that $D = C$. Perform elementary row operations on $D$: add the $a_{11}$-multiple of the $(n+1)$-th row, the $a_{12}$-multiple of the $(n+2)$-th row, $\dots$, and the $a_{1n}$-multiple of the $(2n)$-th row to the first row to get

$$
D = \begin{vmatrix}  0&0&\cdots&0&c_{11}&c_{12}&\cdots&c_{1n}\\ a_{21}  &a_{22}  &\cdots  & a_{2n}&0&0&0&0\\ \vdots  & \vdots &  &\vdots &0&0&0&0\\  a_{n1} & a_{n2} &\cdots  & a_{nn} &0&0&0&0\\ -1&0&\cdots &0&b_{11}&b_{12}&\cdots&b_{1n}\\ 0&-1&\dotso&0&b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots & \vdots & &\vdots&\vdots & \vdots &&\vdots \\ 0&0&\cdots&-1 &b_{n1}&b_{n2}&\cdots &b_{nn} \end{vmatrix}.
$$

Similarly, successively add the $a_{k1}$-multiple of the $(n+1)$-th row, the $a_{k2}$-multiple of the $(n+2)$-th row, $\dots$, and the $a_{kn}$-multiple of the $(2n)$-th row to the $k$-th row to obtain

$$
D = \begin{vmatrix}  0&0&\cdots&0& a_{11} & a_{12} & \cdots &a_{1n} \\ 0&0&\cdots&0&a_{21}  &a_{22}  &\cdots  & a_{2n}\\ \vdots &\vdots & &\vdots &\vdots  & \vdots &  &\vdots \\  0&0&\cdots&0&a_{n1} & a_{n2} &\cdots  & a_{nn} \\ -1&0&\cdots &0&b_{11}&b_{12}&\cdots&b_{1n}\\ 0&-1&\dotso&0&b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots & \vdots & &\vdots&\vdots & \vdots &&\vdots \\ 0&0&\cdots&-1 &b_{n1}&b_{n2}&\cdots &b_{nn} \end{vmatrix}.
$$

In this determinant, the first $n$ rows contain only one non-zero $n$-order minor. Therefore, by Laplace's theorem,

$$
D = \begin{vmatrix}  c_{11} &c_{12} & \cdots &c_{1n} \\ c_{21}  &c_{22}  &\cdots  & c_{2n}\\ \vdots  & \vdots &  &\vdots \\  c_{n1} & c_{n2} &\cdots  & c_{nn}\end{vmatrix} ~\\ ~\\ \ast (-1)^{(1+2+\cdots+n)+(n+1+n+2+\cdots +2n)} ~\\ ~\\ \ast \begin{vmatrix} -1  & 0 & \cdots & 0\\  0 & -1 & \cdots & 0\\ \vdots  & \vdots &  &\vdots \\   0& 0 & \cdots &-1 \end{vmatrix} = C.
$$


Laplace's theorem in determinants and its applications

The Laplace Theorem for Determinant

This article mainly introduces the basic operations and examples of relational algebra such as union, difference, selection, projection and join.

MY BLOG

ALL POSTS