Kvant 1970, No. 6 · Pages

---

running_head:
folio:

NUMERAL SYSTEMS
I. M. Yaglom

§ 1. Key numbers

FIRST NINE NATURAL NUMBERS WE
DESIGNATED WITH SPECIAL SIGNS
1, 2, 3, 4, 5, 6, 7, 8, 9.

2

3

It would be inconvenient to do the same with all numbers encountered in practice. Further, if our needs were limited to counting within thousands, we would need to remember a thousand special characters. Naturally, for a long time people began to choose one or another series of “key” numbers and only designate them with special signs. This is, for example, the Roman numbering system, based on key numbers
1, 5, 10, 50, 100, 500 and 1000.
These numbers in the Roman numeral system represent the letters I (“i”), V (“ve”), X (“ix”), L (“el”), C (“ce”), D (“de”) and M (“em”).

Such designations were often derived from figure, once depicted corresponding numerals (I - finger, V - five with fingers placed, X - two fives), and are often abbreviations of Latin words (centum - one hundred, demimille - five hundred, mille - thousand).

Since we need the Roman numbering system only as an example, we will consider it in an older, simplified version, when the number “four” was written in the form IIII, and not in the form IV. The number 3477 in this old Roman system is written as follows: MMMSSSSCLXXVII=3·1000+4·100+50+2·10+5+2.

The cashier does the same, having banknotes in denominations of 100 rubles, 50 rubles, 25 rubles, 10 rubles, 5 rubles, 3 rubles and 1 ruble. For a cashier, numbers are key

100, 50, 25, 10, 5, 3 and 1.
Wanting to pay, say, 499 rubles, he first issues as many hundred-dollar bills as possible,

to give away too much:
499 = 4·100 + 99.

Then he issues as many 50-ruble couporas as possible in order to issue no more than the remaining 99 rubles to be paid:
499 = 4·100 + 1·50 + 49,
etc. Sometimes he may end up with a remainder less than the next key number. This will be the case in our example after issuing two ten rubles:
499 = 4·100 + 1·50 + 1·25 + 2·10 + 4.

The next key number is 5, however, since 4 < 5, there will be no need to give out five rubles. But for the painting, we can assume that 0 five rubles were given out, and include the term 0·5 in the sum. The entire procedure for issuing 499 rubles will be written like this:
499 = 4·100 + 1·50 + 1·25 + 2·10 + 0·5 + 1·3 + 1·1.

Let us now try to generalize what has been said, taking as a sequence of key numbers (“basis”) any sequence of increasing numbers:
$q_0 = 1 < q_1 < q_2 < \dots < q_n < \dots$ (1)
Let us describe how to obtain a notation for an arbitrary number $N$ in a system of numbers with basis (1).

In sequence (1) of key numbers there is the largest number $q_n$, not exceeding $N$. Delim $N$ by $q_n$ and we get the (incomplete) quotient $a_n$ and the remainder $r_{n-1}$:
$N = a_nq_n + r_{n-1}$, where $0 \leqslant r_{n-1} < q_n$.

The first remainder $r_{n-1}$ is divided by the next key number $q_{n-1}$. We put
$r_{n-1} = a_{n-1}q_{n-1} + r_{n-2}$,
where $0 \leqslant r_{n-2} < q_{n-1}$, or
$N = a_nq_n + a_{n-1}q_{n-1} + r_{n-2}$.

(Note that we do not exclude here the case when $r_{n-1} = 0$ - in this case, all subsequent quotients

4

and the remainders will be equal to zero!) Terrier new remainder $r_{n-2}$ divided by $q_{n-2}$; we get

$$r_{n-2} = a_{n-2}q_{n-2} + r_{n-3},$$

Where

$$0 \leqslant r_{n-3} < q_{n-2},$$

or

$$N = a_nq_n + a_{n-1}q_{n-1} + a_{n-2}q_{n-2} + r_{n-3}$$

etc.

Finally, dividing the penultimate remainder $r_1$ by $q_1$, we get

$$N = a_nq_n + a_{n-1}q_{n-1} + \dots + a_2q_2 + a_1q_1 + r_0,$$

where $0 \leqslant r_0 < q_1$.

(Since $q_0 = 1$, then dividing the “last remainder” $r_0$ by it is redundant: it is clear that $r_0 = a_0q_0 = a_0$.) In practice, such multiple division is usually written together. We will show how this is done using the already discussed example of recording the amount of 499 rubles. in the “cashier system”:

$$499 \times 100 + 499 \times 50 + 499 \times 25 + 499 \times 10 + 499 \times 5 + 499 \times 1 + 499$$

(Here all partials $a_n, a_{n-1}$, etc. are typed in red numbers, and the number itself $N$ and remainders $r_{n-1}, r_{n-2}$, etc. are in blue.)

§ 2. Positional number systems

You have probably already agreed that in the case of a basis

$$q_0 = 1, \quad q_1 = 10,$$

$$q_2 = 10^2, \dots, q_n = 10^n, \dots$$

we will be dealing with the commonly used children’s number system. But instead of writing, say,

$$4 \cdot 10^5 + 0 \cdot 10^4 + 3 \cdot 10^3 + 0 \cdot 10^2 + 1 \cdot 10 + 7$$

we simply write 403017.

A distracted or overly punctual cashier could prepare a record of his output, where the number of issued bills of different denominations would be recorded in separate columns. In this format, issuing 499 rubles would look like this:

| | 100 | 50 | 25 | 10 | 5 | 3 | 1 |
| :— | :— | :— | :— | :— | :— | :— | :— |
| 499 | 4 | 1 | 1 | 2 | 0 | 1 | 1 |

We can say that in the “cashier number system” the number 499 is written as

$$4112011.$$

Number systems related to those discussed in the last two examples (i.e., the decimal number system and the “cashier system”) are called positional (we will talk about the meaning of this expression below). Instead of cumbersome recording

$$N = a_nq_n + a_{n-1}q_{n-1} + \dots + a_2q_2 + a_1q_1 + a_0$$

in a positional number system with basis (1), it is convenient to use a more compact notation from $n+1$ “digits”:

«$a_na_{n-1} \dots a_2a_1a_0$».

It is assumed that the “digits” $a_k$ are obtained in the same way (algorithm) as described above.

From this description it is clear that in a given basis of each natural number $N$ is written in a unique way. Further, since the “major digit” $a_n$ is obtained as the quotient of the number $N$ divided by $q_n$, which by convention is less than $q_{n+1}$ (for otherwise we would start by dividing $N$ by $q_{n+1}$, and not by $q_n$!), then $a_n < q_{n+1}/q_n$. That’s why,

10

13. What conditions must the numbers of the basic sequence $q_1, q_2, q_3, \dots$ satisfy in order for the numbers to contain only two digits: 0 and 1? What other conditions should be imposed on these numbers $q_1, q_2, \dots$ so that no two ones come in a row?

14. Sequence of numbers

$$q_0 = 1, \quad q_1 = 2, \quad q_2 = 3,$$

$$q_3 = 5, \quad q_4 = 8, \quad q_5 = 13, \dots,$$

where $q_{n+1} = q_n + q_{n-1}$ is called the Fibonacci sequence. Prove that the Fibonacci system of numbers satisfies all the conditions of the previous problem. Find the sum of numbers in this system

a) $\underbrace{100 \dots 00}_{k} + \underbrace{100 \dots 00}_{l}$;

b) $\underbrace{10101 \dots 01}_{2m+1} + 1$;

c) $\underbrace{10101 \dots 01}_{2m+1} + \underbrace{100 \dots 00}_{2m+1}$.

15. Is it possible to divide all natural numbers 1, 2, 3, 4, 5, 6, 7, … into two increasing sequences $a_1, a_2, a_3, a_4, \dots$ and $b_1, b_2, b_3, b_4, \dots$ such that $b_k - a_k = k$ for any $k = 1, 2, 3, \dots$?

After some thought, you will, of course, agree on how to choose such sequences (this can be done in the only way)

$$\begin{array}{cccccccc} a_1 & b_1 & a_2 & a_3 & b_2 & a_4 & b_3 & a_5 & a_6 & b_4 & a_7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ a_8 & b_5 & c_9 & b_6 & \dots \\ 12 & 13 & 14 & 15 & \dots \\ \end{array}$$

It is not so easy to satisfy pairs $(a_k, b_k)$ in education. How can you find out, for example, which of the two sequences $-a_k$ or $b_k$ 100 belongs to, what number it corresponds to, what number will be with it (without writing out all the previous $a_k$ and $b_k$)?

It turns out that in order to formulate this pattern, you need to write these sequences not in the decimal, but in the Fibonacci number system. Try to discover and prove it.

10

12

There are different sides to it - the “face” and the “wrong side”. After this, you need to count all the lines of force that pierce the film from the inside on the face, and subtract from this number the lines of force that pierce the film in the opposite direction, if there are such lines. The difference and dact us the magnitude of the magnetic flux, which, thus, can be negative. Precisely because the ignoring lines of force do not circulate, it does not matter what kind of film the contour is covered with - wrap it sparingly or sew a whole net to the contour - the flow will be the same (Fig. 1). The flow is denoted by the letter F (perhaps because it is similar to a line of force producing a circuit). If we change the magnetic field in Gauss, the dimension Ф will be $eaycc \cdot cm^2$ (ess. $cm^2$).

If the magnetic flux covered by the circuit changes over time by values ​​$\Delta \Phi$ in time $\Delta t$, and the circuit is made of wire with electrical resistance $R$, then according to the law of electromagnetic induction, the current begins to cycle along the circuit

$$I = -10^{-8} \frac{\Delta \Phi}{\Delta t} \cdot \frac{1}{R} \text{ amper} \quad (1)$$

($\Phi$ is expressed in $ec \cdot cm^2$, $t$ is in seconds, and $R$ is in ohms). This current in the circuit flows under the influence of the electromotive force of induction

$$\varepsilon = -10^{-8} \frac{\Delta \Phi}{\Delta t} \text{ волт.} \quad (2)$$

The minus sign in these formulas is connected with this: we consider positive the current in the circuit, which itself creates a magnetic field in it with a positive flux (such a current flows around the circuit clockwise, if viewed from the inside out). The negative sign, therefore, shows that if the flux decreases with time $\left( \frac{\Delta \Phi}{\Delta t} \text{ отрицательно} \right)$, then the excited current will be positive and will itself create a positive flux. On the contrary, if the flow returns, the current in the circuit creates a flow in the opposite direction (Lenz’s rule). Since the flux Ф consists of the flux of the external field and the flux created by the circuit itself, the induction of current in the circuit leads to a slowdown in the change in the total flux through the circuit.

Let the current be zero at the initial moment, and the flow is created by some external field source, for example a magnet. Now let’s quickly remove the magnet. Then, at the same time, a current will arise in the circuit, which itself creates a magnetic flux of the same magnitude, that is, it will not allow the magnetic flux higher out of the circuit. In order for a current to exist in a circuit with electrical resistance $R$, it is necessary, of course, for the flow to change. Therefore, in subsequent moments, Ф will still gradually decrease, but the slower, the smaller $R$. Likewise, if we want to increase the flow of the internal circuit, this can only be done gradually.

It is necessary to note one great advantage of the law of electromagnetic induction: all our reasoning and formulas remain valid regardless of how we change the magnetic flux through the circuit - whether we change the magnetic field itself or also move, bend,

15

Fig. 3. Connection diagram of a superconducting coil with a superconducting switch. Part of the circuit is at low temperature. The power circuit heating $B$ to figure is not shown.

After the superconducting switch is closed, wires $B$ are no longer needed and are even harmful, since heat penetrates into the dewar through them.

There is another ingenious way of “pumping” magnetic flux into superconducting coils, which allows you to bypass it without inserting wires into the dewar at all. The circuit of a device based on this method is shown at figure 4. The coil, which for simplicity we have replaced at figure with a flat circuit $A$, is connected in parallel by two superconducting wires $B$ and $B$. Magnet $M$ can move around the contour. The path of its lower end is shown in figure 4 point. The magnet must be so strong that its field can destroy the superconductivity of wires $B$ and $B$.

The successive positions of the magnet when pumping flux into the circuit are shown at Fig. 5,$a$—5,$\delta$. The magnetic flux coming out of the end of the magnet is indicated by dots - traces of the lines of force. In position $a$ the magnet destroyed superconductivity

18

§ 1. Definition and simplest properties of binomial coefficients

If the binomial (binomial) $1+x$ is weighed by some natural power $n$, then, obviously, the result is a polynomial of the $n$ degree (i.e., the highest degree to which $x$ appears in this polynomial will be equal to $n$). For example:

$$(1+x)^0 = 1,$$
$$(1+x)^1 = 1+x,$$
$$(1+x)^2 = 1+2x+x^2,$$
$$(1+x)^3 = 1+3x+3x^2+x^3,$$
$$(1+x)^4 = 1+4x+6x^2+4x^3+x^4,$$
$$(1+x)^5 = 1+5x+10x^2+10x^3+$$
$$+5x^4+x^5,$$

The coefficients of these polynomials are called binomial. There is special notation for them: the coefficient of $x^m$ in $(1+x)^n$ is denoted by $C_n^m$. For example, $C_2^1=2$, $C_4^2=6$, $C_5^3=10$. In old algebra textbooks, the number $C_n^m$ is called “the number of combinations of $n$ through $m$”. There are reasons for this, but we don’t

From here it is easy to obtain that

$$(a+x)^n = C_n^0a^n + C_n^1a^{n-1}x\ldots$$
$$\ldots + C_n^nx^n$$

(it is enough to apply formula (1) to the calculation of $(1+x)a^n$ and multiply both sides of the resulting equality by $a^n$). The last formula is called Newton’s binomial. Hence the name of the coefficients - binomial.

It is clear that $C_n^m$ are non-negative integers and that $C_n^m=0$ for $m>n$ (the polynomial $(1+x)^n$ has degree $n$, and $x^m$ with $m>n$ is not included in it). It is easy to verify further that $C_n^0=C_n^1=1$. Other binomial coefficients $C_n^m$, where $0<m<n$, can be found by raising $1+x$ to various powers. Their values ​​for $n\leqslant10$ are given in the table.

We see that binomial coefficients are quite rapidly growing numbers. An observant reader will notice a number of patterns in the arrangement of these numbers. As a rule, such patterns are easily derived from the definition of binomial coefficients. We will prove here only the main ones. Let’s start with the most important of all - the so-called Pascal identity.

We will highlight in them: for us this is not important. So,

$$(1+x)^n = C_n^0+C_n^1x+C_n^2x^2+\ldots$$
$$\ldots +C_n^nx^n.$$

(1)

Theorem 1 (Pascal’s identity).

$$C_n^m = C_{n-1}^m+C_{n-1}^{m-1}$$

(2)

for any natural $n, m$.

20

Thus, formula (3) holds for $n=1$, and from its validity for $n-1$ it follows that it is true for $n$. This proves formula (3) for any $n$.

We recommend that the reader, having become acquainted with formula (3) for the first time, deduce from it the already known equalities $C_n^0 = C_n^n = 1$ and $C_n^m = 0$ for $m>n$.

Formula (3) is interesting because the fraction on its right side is equal to a whole number, that is, all the numbers in its denominator will cancel with the numbers in the numerator.

The following theorem will be used further.

Theorem 3. If the numbers $n$ and $m$ are coprime (that is, the greatest common divisor of the numbers $n$ and $m$ is 1), then $C_n^m$ is divisible by $n$.

Proof:

$$C_n^m = \frac{n(n-1)\ldots(n-m+1)}{1\cdot2\ldots m} = \frac{n}{m} \cdot \frac{(n-1)\ldots(n-m+1)}{1\cdot2\ldots(m-1)} = \frac{n}{m} \cdot C_{n-1}^m$$

Thus,

$$mC_n^m = nC_{n-1}^m$$

i.e. the number $mC_n^m$ is divisible by $n$. But since $m$ and $n$ are coprime, i.e. $m$ is not divisible by any prime divisor of $n$, then $C_n^m$ is divisible by $n$.

For example, $C_9^4 = 126$ is divisible by 9, $C_{10}^3 = 120$ is divisible by 10.

Let us indicate a few more properties of biomial coefficients:

1. $C_n^m = C_{n-1}^m$
2. $C_n^m + C_{n+1}^m + \ldots + C_{m+k}^m = C_{m+k+1}^m$
3. $C_n^0 + C_n^1 + \ldots + C_n^n = 2^n$
4. $C_n^0 + C_n^2 + C_n^4 + \ldots = C_n^1 + C_n^3 + C_n^5 + \ldots$

We leave the proof of these properties to the reader.

§ 2. Residues from dividing biomial coefficients by prime numbers

In this (and in the next) paragraph we will often have to use the form “the numbers $a$ and $b$ have equal remainders when divided by $p$”. Generally, this form is replaced by the abbreviated notation “$a \equiv b$ (mod $p$)”. In other words, the formula “$a \equiv b$ (mod $p$)” means that $a-b$ is divisible by $p$. For example, $4 \equiv 1$ (mod 3), $999999 \equiv 222222$ (mod 7), etc. The formula “$a \equiv b$ (mod $p$)” is sometimes read like this: “the number $a$ is comparable to the number $b$ modulo $p$” (however, we will not use expressions either).

Here are two very properties of the symbol ≡:

1. If $a \equiv b$ (mod $p$) and $k$ are integers, then $ka \equiv kb$ (mod $p$).

Indeed, if $a-b$ is divisible by $p$, then $ka-kb = k(a-b)$ is also divisible by $p$.

2. If $a \equiv b$ (mod $p$) and $b \equiv c$ (mod $p$), then $a \equiv c$ (mod $p$).

Indeed, if $a-b$ is divisible by $p$ and $b-c$ is divisible by $p$, then $a-c = (a-b)+(b-c)$ is also divisible by $p$.

Let us recall that any natural number $a$ can be divided by a natural number $p$ “with a remainder”, i.e. $a$ can be uniquely written in the form $a=bp+c$, where $b$, $c$ are integers such that $0 \leq c < p$.

The main goal of this section is to prove the following statement.

Theorem 4. Let $p$ be a prime number, $m$ and $n$ be natural numbers. Let, further, $k$ and $l$ be the partials of dividing the numbers $m$ and $n$ by $p$, and $s$ and $t$ be the remainders (i.e. $m=kp+s$, $n=lp+t$, where $k$, $l$, $s$, $t$ are integers and $0 \leq s < p$, $0 \leq t < p$). Then

$$C_n^* = C_l^* \cdot C_s^* \pmod p.$$

As we will see below, this theorem allows us to find remainders from dividing biomial coefficients by prime numbers, almost without performing any calculations.

23

in such a way that $C_{119}^{33} \equiv 0$ (mod 3), i.e. $C_{119}^{33}$ is divisible by 3 without remainder.

Note that if we apply our Theorem 4 to $C_n^m$, where $n \geq m$, then by writing $m = kp + s$, $n = lp + t$ we will of course have $l \geq k$; however, it is impossible to predict which of the numbers $s$, $t$ will be larger. If there is $s > t$, then according to our theorem $C_n^m \equiv C_l^k C_s^t = 0$ (mod $p$), i.e. $C_n^m$ is divisible by $p$. As we have seen, to determine the remainder when dividing the number $C_n^m$ by $p$ one usually comes to use Theorem 4 several times; and every time a phenomenon similar to that described above can occur, and whenever this happens, this means that a similar number $C_n^m$ is divisible by $p$. Similarly, we got that $C_{119}^{33}$ is divisible by 3.

We see that the larger $n$, the more likely the number $C_n^m$ is divisible by $p$. It is easy to prove the following, more precise statement: the total number of numbers $C_n^m$ with $0 \leq n \leq p^r$, $0 \leq m \leq n$ there are $\frac{p^r (p^r + 1)}{2}$, of which is not divisible by $p$ exactly $\frac{p^r (p + 1)^r}{2^r}$ (here $p$ is simple, $r$ natural; the proof is based only on Theorem 3, we leave it to the reader). It is emphasized that for large $r$ the number $\frac{p^r (p + 1)^r}{2^r}$ is many times smaller than the number $\frac{p^r (p^r + 1)}{2}$.

So, for example, of the numbers $C_n^m$ with $0 \leq n \leq 3^5$, $0 \leq m \leq n$ approximately 26.2% are not divisible by 3; if $0 \leq n \leq 3^{10}$, then approximately 3.6%, and if $0 \leq n \leq 3^{15}$, then approximately 0.45%.

In conclusion, let’s say a few words about the weight of the visual interpretation of Theorem 4, which can be obtained by considering the so-called “Pascal’s triangle according to the $p$ model”. This is the name of the triangular table that will be obtained from Pascal’s triangle if each number in it is replaced by its remainder when divided by $p$. We do not prove any theorems about this triangle, but we invite the reader to look at two pictures (on the cover and on page 22) that depict Pascal’s triangles modulo 2 and 3. Think about how these triangles are arranged in the part that is not visible on figure. Try to formulate Theorem 4 in such a way that it becomes a theorem about the structure of Pascal’s triangle modulo $p$.

§ 3. A little about remainders from dividing biomial coefficients by powers of prime numbers

We do not consider in any general way the question of remainders from dividing biomial coefficients into composite numbers. (However, the reader can think about this for himself; what, for example, is the remainder of dividing the number $C_{119}^{33}$ by 4: one or trem?) We will limit ourselves to talking about one amazing phenomenon that has not been fully explained by us.

Let’s start with some calculations. Using the formula for biomial coefficients (see § 1, formula (2)), we obtain

$$C_2^1 = 2,$$
$$C_4^2 = 6,$$
$$C_8^4 = 70,$$
$$C_{16}^8 = 12870,$$
$$C_{32}^16 = 601080390.$$

(Everyone knows, of course, that 1, 2, 4, 8, 16, 32, … are successive powers of two.) The resulting numbers themselves should not be used in any special way; their successive differences, however, reveal striking properties. Let’s look at them:

$$6 - 2 = 4 = 2^2,$$
$$70 - 6 = 64 = 2^6,$$
$$12870 - 70 = 12800 = 2^9 \cdot 25,$$

24

---

running_head:
folio:

$$601\ 080\ 390 - 12\ 870 = 601\ 067\ 520 = 2^{12} \cdot 146\ 745.$$

We see that these differences are divided into high powers of two - so large that this phenomenon does not cause harm. It is possible to prove a theorem that explains it at least partially.

Theorem 5. If $n > 1$, then the number
$$\alpha_n = C_{2n+1}^{2n} - C_{2n}^{2n-1}$$
is divisible by $2^{2n+2}$.

Sweeping.
1°. The assumption that $n > 1$ is significant since $\alpha_1$ is equal to 4 and is not divisible by $2^{2n+2} = 2^4 = 16$.
2°. One might expect that $\alpha_n$ for $n > 1$ is even divisible by $2^{3n}$: this is true for $n = 2, 3, 4$. But we don’t know how to prove this.

Proof. Let’s start with the general observation that if the number $r$ is odd, then $C_{2n}^{r}$ is divisible by $2^n$. In fact, since $r$ is odd, and $2^n$ has no prime divisors other than two, then the numbers $r$ and $2^n$ are coprime and the statement we need follows from Theorem 3.

Let us put the theory
$$P(x) = (1+x)^{2n+1} - (1-x^2)^{2n}.$$

The polynomial $P(x)$ contains $x^{2n}$ with coefficient $C_{2n+1}^{2n} - C_{2n}^{2n-1} = \alpha_n$ (here we use the fact that $n > 1$: when $(1-x^2) = 1 + (-x^2)$ appears to the power $2^n$, we obtain with coefficient $C_{2n}^{2n-1}$ not $x^{2n}$, but (-x^2)^{2n-1} = (-1)^{2n-1}x^2^n, while the number $(-1)^{2n-1}$ is 1 at $n > 1$ and equal to $-1$ at $n = 1$.

On the other side,
$$P(x) = (1+x)^{2n+1} - (1+x)^{2n} = (1+x)^{2n}[(1+x)^{2n} - (1-x)^{2n}].$$

At the same time
$$(1+x)^{2n} - (1-x)^{2n} = (1+x)^{2n} - (1+(-x))^{2n} = 1 + C_{2n}^{1}x + C_{2n}^{2}x^2 + C_{2n}^{3}x^3 + \dots + x^{2n} - 1 - C_{2n}^{1}(-x) - C_{2n}^{2}(-x)^2 - C_{2n}^{3}(-x)^3 - \dots - (-x)^{2n} =$$
(since $(-x)^k$ is equal to $x^k$ when $k$ is even and equal to $-x^k$ when $k$ is odd)
$$= 2\left(C_{2n}^{1}x + C_{2n}^{3}x^3 + C_{2n}^{5}x^5 + \dots + C_{2n}^{2n-1}x^{2n-1}\right).$$

We emphasize that the resulting polynomial $x$ appears only in odd powers.

We want to know with what coefficient $x^{2n}$ enters $P(x)$, i.e., into the product
$$(1+x)^{2n}[(1+x)^{2n} - (1-x)^{2n}] = 2\left(1 + C_{2n}^{1}x + C_{2n}^{2}x^2 + C_{2n}^{3}x^3 + \dots + x^{2n}\right) \times \left(C_{2n}^{1}x + C_{2n}^{3}x^3 + C_{2n}^{5}x^5 + \dots + C_{2n}^{2n-1}x^{2n-1}\right).$$

Obviously, $x^{2n}$ can be obtained by multiplying $x^{2n-1}$ from the first factor and $x$ from the second, by multiplying $x^{2n-3}$ from the second factor and $x^3$ from the second, etc. Thus, the coefficient in $P(x)$ for $x^{2n}$, equal, as we know, to $\alpha_n$, is also equal
$$2\left(C_{2n}^{1}C_{2n}^{2n-1} + C_{2n}^{3}C_{2n}^{2n-3} + \dots + C_{2n}^{2n-1}C_{2n}^{1}\right).$$

As we know, each of the numbers $C_{2n}^{1}, C_{2n}^{3}, \dots, C_{2n}^{2n-1}$ is divisible by $2^n$. Therefore, each term in brackets is divided by $2^n \cdot 2^n = 2^{2n}$; in addition, the two comes before the entire expression,

25

and besides, each term in brackets occurs twice. Thus, $\alpha_n$ is divisible by $2^{2n+2}$, as required.

So, the strange phenomenon of divisibility of numbers $\alpha_n$ into high powers of two is to some extent explained. But nothing similar is observed if you replace the two with a three, five, seven. Really,

$$C_9^3 - C_3^1 = 84 - 3 = 81 = 3^4;$$

$$C_{27}^9 - C_9^3 = 4686825 - 84 = 4686741 = 3^7 \cdot 2143;$$

$$C_{81}^{27} - C_{27}^9 = 2306279447501851002720 - 4686825 = 2306279447501846315895 = 3^{10} \cdot 39057044954221855;$$

$$C_{25}^5 - C_5^1 = 43130 - 5 = 43125 = 5^5 \cdot 69;$$

$$C_{49}^7 - C_7^1 = 85900584 - 7 = 85900577 = 7^5 \cdot 5111.$$

In short, it seems to be true that for prime $p$ the number

$$C_{pn+1}^{p^n} - C_{pn}^{p^n-1}$$

is divisible by a high power of the number $p$. But we don’t know how to prove this.

By the way, if $p$ is not prime, then nothing like this is observed. For example,

$$C_{16}^4 - C_4^1 = 1820 - 4 = 1816$$

not even divisible by $4^2$;

$$C_{36}^6 - C_6^1 = 1947792 - 6 = 1947786$$

is not even divisible by $6^2$.

We believe that one of the readers of «Kvant» can understand this complex issue of biomial coefficient arithmetic.

HAPPENING
WITH DEDEKIND

The author of the most widespread theory of irrational numbers, P. Dedekind, died, as is known, on February 12, 1916 at the age of 84.

However, back in 1904, in the “Book of Memoirs.dat for Mathematicians,” published as a supplement to the catalog of the Teudner publishing house and intended for participants in the third international mathematical congress, held in Heidelberg in the same year, the date September 4, 1899 was mentioned … the death day of P. Dedekind.

The latter was not replaced by writing a letter by the compiler of the mentioned book with approximately the following content: “Dear colleague! In your informative “Book of Memories.dat” you kindly remembered me. I am very grateful to you for this. I allow myself, however, to draw your attention to the fact that in indicating the date of my death, at least the year must be indicated incorrectly.”

29

Entrance exams in mathematics at the Moscow Institute of Steel and Alloys are typical for most technical schools.

At the faculties of MCHMIS (metallurgy of ferrous metals and alloys) and MCRMIS (metallurgy of non-ferrous metals and alloys) the disciplines are written mathematics, physics and chemistry; at the faculties of Physics (physics and chemistry) and PMP (semiconductor materials and devices) - written and oral mathematics and physics. The competition for all faculties is held separately.

Note that about 19% (179 people) of the new student body was recruited in industrial centers: Bekabad, Volgograd, Zaporozhye, Norilsk, Orsk, Cherepovets.

The content of the tickets for written and oral examinations strictly corresponded to the mathematics program for applicants to universities.

Let’s look at one of the options offered at the faculties of MCHMIS and MCRMIS.

Option 1.

1. Solve the equation
   $$\sec^2 \frac{x}{2} + \cos^2 \frac{x}{2} = 16 \text{ ctg } x.$$

2. Solve inequality
   $$\frac{3x^2 - 2x - 1}{\lg(x - 1)} < 0.$$

3. Simplify
   $$\left[ 4(a + 1) + \left( \frac{\sqrt{ab^2} + \sqrt{a}}{\sqrt{3}a + \sqrt{3}b} + \frac{\sqrt{6}a}{3} \right)^3 \right]^{1/2}$$

4. Let $E$ be the midpoint of side $AB$ of the trapezoid $ABCD$ ($BC \parallel AD$). Prove that the area of ​​the triangle $ECD$ is equal to half of the trapezoid $ABCD$.

5. A cube with edge $a$ is inscribed in a regular quadrangular paramid such that four of its vertices are on the side edges, and four other vertices are on the base of the paramid. The lateral faces of the paramid are inclined to the plane of the base at an angle $\alpha$. Determine the volume of the paramid.

Solution

1. Let us define the ODZ equation:
   $$x \neq \pi l \quad (l = 0, \pm 1, \dots).$$

Let’s start solving the equation. We have
$$\frac{1}{\cos^2 \frac{x}{2}} + \frac{1}{\sin^2 \frac{x}{2}} = 16 \frac{\cos x}{\sin x},$$
where
$$\frac{1}{\cos^2 \frac{x}{2}} \sin^2 \frac{x}{2} = 16 \frac{\cos x}{\sin x}$$
or
$$\frac{4}{\sin^2 x} = 16 \frac{\cos x}{\sin x}.$$

Since $\sin x \neq 0$, we get
$$4 \sin x \cos x = 1$$
or
$$\sin 2x = \frac{1}{2},$$
where
$$2x = (-1)^n \frac{\pi}{6} + \pi n,$$

31

---

running_head:
folio:

Fig. 3.

Therefore
$$S_{ECD} = \frac{1}{2} S_{ABCD}.$$

5. First of all, note that the vertices of the lower base of the cube lie on the diagonals of the base of the paramid (projection of the side edges) and that $\angle ETO = \alpha$ (Fig. 2).

Let us denote the side of the base of the paramid by $x$. From $\triangle EOT$ there is $EO$ paramid:

$$EO = OT \cdot tg\alpha = \frac{x}{2} tg\alpha.$$ Next, from the similarity of triangles $EO_1K_1$ and $EOC$ we have $EO_1:EO = O_1K_1:OC$ or

\frac{x}{2} tg\alpha - a}{\frac{x}{2} tg\alpha} = \frac{a \sqrt{2}}{2},

where

$$x = \frac{2a(1 + tg\alpha)}{tg\alpha}.$$

The volume of paramid $EABCD$ is equal to

$$V = \frac{1}{3} x^2 \frac{x}{2} tg\alpha = \frac{1}{6} x^3 tg\alpha =$$

$$= \frac{4}{3} a^3 \frac{(1 + tg\alpha)^3}{tg^2\alpha} =$$

$$= \frac{8 \sqrt{2} a^3 \cos^3(\alpha - \frac{\pi}{4})}{3 \sin^2\alpha \cos\alpha} =$$

$$= \frac{16 \sqrt{2} a^3 \cos^3(\alpha - \frac{\pi}{4})}{3 \sin 2\alpha \sin\alpha}.$$

Answer:

$$V = \frac{16 \sqrt{2} a^3 \cos^3(\alpha - \frac{\pi}{4})}{3 \sin 2\alpha \sin\alpha}.$$

Let us now examine one of the options offered in the written exam at the faculties of PH and PMP.

Option 2

1. A quadrangular paramid is inscribed in a ball of radius $R$, the lateral edges of which are inclined to the plane of the base at an angle $\alpha$. Determine the volume of the paramid if at its base lies a rectangle with an angle $\beta$ between the diagonals.

2. Solve the equation

$$\sqrt{2} \sin 10x + \sin 2x = \cos 2x.$$

3. Solve inequality

$$\log_{3x+4} x^2 < 1.$$

4. Simplify an expression

$$(a + x^{1/2})^{-1/2} + (a - x^{1/2})^{-1/2},$$

where $x = 4(a-1)$, and $1 < a < 2$.

Solution

1. The plane of the base of the paramid intersects the ball in a circle (Fig. 3) circumscribed near the base $ABCD$. The height of the paramid will pass through the center $O$ of the ball and through the center $O_1$ of this circle, since all the edges are inclined to the base at equal angles. A plane passing through the diagonal of the base $AC$ and the vertex $E$ will intersect the ball along a great circle circumscribed about the diagonal section of the paramid $AEC$. From $\triangle AEC$, where $\angle AEC =$

32

= 180° - 2α, by the theorem of sines, finding that
AC = 2R sin (180° - 2α) = 2R sin 2α. Because
AO₁ = $\frac{1}{2}$ AC = R sin 2α.

From △ AEO₁ we determine the straightness height:
EO₁ = H = AO₁ · tg α = R sin 2α · tg α.

The area of ​​the base of the straight line is equal to
S_{ABCD} = 2 (S_{AO₁B} + S_{BO₁C}) =
= 2 [$\frac{1}{2}$ AO₁² sin β +

• $\frac{1}{2}$ AO₁² sin (180° - β)] =
  = 2R² sin² 2α sin β.

The volume of straight line V will be equal to
V = $\frac{1}{3}$ 2R² sin² 2α sin β · R sin 2α · tg α =
= $\frac{2}{3}$ R³ sin³ 2α tg α sin β.

Answer:
V = $\frac{2}{3}$ R³ sin³ 2α tg α sin β.

2. Noticing that
   cos 2x - sin 2x =
   = sin ($\frac{\pi}{2}$ - 2x) - sin 2x =
   = $\sqrt{2}$ sin ($\frac{\pi}{4}$ - 2x),

we rewrite the equation in the form
$\sqrt{2} \sin 10x = \sqrt{2} \sin (\frac{\pi}{4} - 2x)$

or
sin 10x + sin (2x - $\frac{\pi}{4}$) = 0,

where
sin (6x - $\frac{\pi}{8}$) cos (4x + $\frac{\pi}{8}$) = 0.

Equating each of the components to zero, we get
x₁ = $\frac{\pi}{48}$ (8n + 1) (n = 0, ±1, …),
x₂ = $\frac{\pi}{32}$ (8k + 1) (k = 0, ±1, …).

3. Let’s consider two cases: 3x + 4 > 1 and 0 < 3x + 4 < 1.

In the first case we get
$$\begin{cases} 3x + 4 > 1, \\ x^2 < 3x + 4, \\ x^2 > 0 \end{cases}$$ or $$\begin{cases} x > -1, \\ -1 < x < 4, \\ x \neq 0, \end{cases}$$

where is the location from?
-1 < x < 0, 0 < x < 4.

In the second case we have
$$\begin{cases} 0 < 3x + 4 < 1, \\ x^2 > 3x + 4, \\ x^2 > 0 \end{cases}$$

or
$$\begin{cases} -\frac{4}{3} < x < -1, \\ x < -1, x > 4, \\ x \neq 0, \end{cases}$$

where do we get it from?

• $\frac{4}{3} < x < -1$.

Answer:

• $\frac{4}{3} < x < -1$;
• -1 < x < 0; 0 < x < 4.

When solving this problem, the conditions x ≠ 0 were not taken into account, and therefore, together with the last two integrals, we obtained -1 < x < 4.

4. We have
   $$(a + x^{1/2})^{-1/2} = \frac{1}{\sqrt{a + \sqrt{x}}} =$$
   $$= \frac{1}{\sqrt{a + 2\sqrt{a - 1}}} =$$
   $$= \frac{1}{\sqrt{(a - 1) + 2\sqrt{a - 1} + 1}} =$$
   $$(a - x^{1/2})^{-1/2} = \frac{1}{\sqrt{a - \sqrt{x}}} =$$
   $$= \frac{1}{\sqrt{a - 2\sqrt{a - 1}}} =$$
   $$= \frac{1}{\sqrt{(a - 1) + 2\sqrt{a - 1} + 1}} =$$
   $$= \frac{1}{\sqrt{(a - 1) - 1} + 1} =$$

33

$$\frac{1}{\sqrt{a-1}-1} = \frac{1}{1-\sqrt{a-1}},$$

since $1 < a < 2$, i.e. $\sqrt{a-1} < 1$.

Finally we get

$$\left(a + x^{1/2}\right)^{-1/2} + \left(a - x^{1/2}\right)^{-1/2} = \frac{1}{1+\sqrt{a-1}} + \frac{1}{1-\sqrt{a-1}} = \frac{2}{2-a}.$$

When solving this problem, they forgot a lot about the condition $1 < a < 2$ and therefore made mistakes when extracting the root.

Written exams showed the following highest places among those who built:

1. Many mistakes are still made when simplifying algebraic expressions: applicants have poor knowledge of degrees and make mistakes where they need to use a certain argument root (see problem 4 from option 2 discussed above).

2. Many applicants do not have fluency in trionometric formulas, as a result of which errors arose when solving a trionometric problem, or they chose far from the shortest path to solve such a problem.

3. When solving inequalities, mistakes were made due to the insignificance of both the properties of inequalities and the properties of functions. Very often, for example, applicants did not take into account the VA of the functions included in the inequality (see task 2 from option 1, task 3 from option 2).

4. When solving stereometric problems, the stumbling block was often the lack of meaning of the basic concepts of stereometrics. For example, people often incorrectly found the linear angle of the arc angle between adjacent lateral edges parameters. Many people mistakenly believed that the linear angle in this case would be the angle at the vertex of the underlying polygon parameters.

Now try to solve some problems from other entrance exam options yourself.

Problems proposed at the faculties of MCHMIS and MCRMIS.

1. Convert to work

$$\sin 5\alpha \cdot \sin 4\alpha + \sin 4\alpha \cdot \sin 3\alpha - \sin 2\alpha \cdot \sin \alpha.$$

2. Find $tg \frac{\alpha}{2}$ if $\sin \alpha + \cos \alpha = 1,4$; $0 < \alpha < 45^\circ$.

3. Prove the same gesture

$$\frac{1}{1 + tg \alpha tg 2\alpha} = \sin \left(\frac{\pi}{2} + 2\alpha\right).$$

4. Compute $18 \sin \frac{3}{2} x \sin \frac{x}{2}$ if $\cos x = \frac{2}{3}$.

5. Prove equality

$$\cos 10^\circ \sin 20^\circ - 2 \sin 70^\circ = 1.$$

6. Solve inequality

$$3^{x+1} + 18 \cdot 3^{-x} < 29.$$

7. Solve the equation

$$\log_2 \left(4^{x-2} + 1\right) - x + 4 = \log_2 17.$$

8. Solve inequality

$$\log_3 \frac{5x-3}{2-x} > 0.$$

9. Solve inequality

$$\log_x \frac{15}{1-2x} < -2.$$

10. Solve system of equations

$$\begin{cases} \frac{x}{2} + \frac{3}{y} = 7,5, \\ \frac{7}{x} + \frac{y}{6} = 1,5. \end{cases}$$

11. Solve system of equations

$$\begin{cases} \sqrt[3]{\frac{x}{y}} + \sqrt[3]{\frac{y}{x}} = 2,5, \\ x + y = 9. \end{cases}$$

12. Solve system of equations

$$\begin{cases} 2 \log_a x + \log_a y = 3, \\ \log_b x - \log_b y = 1. \end{cases}$$

13. Find all real values ​​of $a$ for which the system of equation

$$\begin{cases} x^2 - y^2 = 1, \\ y = ax \end{cases}$$

has valid solutions.

14. Find all values ​​of $a$ for which trilen

$$(a^2 - 1)x^2 + 2(a - 1)x + 2$$

will be positive for all real values ​​of $x$.

34

15. Find for what values ​​of $a$ the solution of the system
    $$\begin{cases} x + y = 3, \\ ax + 4y = 6 \end{cases}$$
    satisfies the inequalities $x > 1, y > 0$.

16. For what values ​​of $a$ do equations $3x^2 - x - a = 0$ and $4x^2 + 8x + a = 0$ both have real roots?

17. In what interval should the number $m$ change so that the roots of the equation $x^2 - 2mx + m^2 - 1 = 0$ are between -2 and 4?

18. Prove that if the median and altitude drawn from one vertex of a triangle divide the angle into three equal parts, then the triangle is rectangular.

19. Prove that in a regular pentagon one of the segments of intersecting diagonals is equal to the side of the pentagon.

20. Triangle $ABC$ rotates around bisector $AD$. Prove that the areas of the surfaces described by the sides $AB$ and $AC$ are related as volumes obtained by rotating the parts $ABD$ and $ACD$.

21. Prove that if a ball can be inscribed in a truncated cone, then the volume of the cone is equal to the product of its total surface and $1/6$ height.

22. Prove that the volume of a cone is equal to the product of its total surface and $1/3$ the radius of the inscribed ball.

Problems proposed at the faculties of PH and PMP.

23. A rectangular parallelepiped is inscribed in a cylinder, one of the sides of its base is equal to $b$. The diagonal of the parallelepiped forms an angle $\alpha$ with the plane of the base, and an angle $\beta$ with the side face passing through this side of the base. Determine the lateral surface of the cylinder.

24. Determine the volume of a regular quadrangular paramid whose lateral edge is equal to $l$, and the angle between adjacent lateral faces is equal to $\beta$.

25. Calculate without using a table
    $$\text{tg} 9^\circ - \text{tg} 27^\circ - \text{tg} 63^\circ + \text{tg} 81^\circ.$$

26. Solve the equation
    $$\sec^2 x = \frac{2 - \cos x - \sin x}{1 - \sin x}.$$

27. Solve inequality
    $$x^2 + \frac{5}{2} x - \frac{3}{2} < 1.$$

28. Solve inequality
    $$\frac{|x - 2| - |x + 2|}{x - 1} < 0.$$

29. Solve inequality
    $$\left(\frac{1}{2}\right)^{\log_3 \log_2 \left(x^2 - \frac{4}{5}\right)} < 1.$$

30. Solve inequality
    $$\lg \left| \frac{3x - 1}{2x + 1} \right| < 0.$$

31. Solve inequality
    $$\log_2 x 2 \log_2 x 2 \log_2 (4x) > 1.$$

32. Prove that for $n^2 < a < 2n^2(n > 0)$
    $$\left(\sqrt{a + 2n \sqrt{a - n^2}} + \sqrt{a - 2n \sqrt{a - n^2}}\right):$$
    $$\left(\frac{1}{\sqrt{a} + \sqrt{a + 1}} + \frac{1}{\sqrt{a + 1} + \sqrt{a + 2}} + \dots + \frac{1}{\sqrt{a + n - 1} + \sqrt{a + n}}\right) = 10^{\lg 2} + \lg \left(\sqrt{a} + \sqrt{a + n}\right).$$

33. Solve the equation
    $$\sqrt{a^2 + bx} + \sqrt{a^2 - bx} = \sqrt{2abx}$$
    at $a > 0, b > 0$.

34. Simplifying, solve the equation
    $$\frac{\left(\sqrt{x - 1} + \sqrt{x + 1} + 2\right)(2x - \sqrt{x^2 - 1})}{(x + 1)^{3/2} + (x - 1)(x - 1)^{1/2}} = \sqrt{x^2 - 1} \left(\frac{\log_a x}{\log_ab x} - \log_a b\right).$$

35. Solve system of equations
    $$\begin{cases} 3 |x| - 5y = 3, \\ 2x + |y| = 11. \end{cases}$$

36. Prove that
    $$\left[ \frac{1}{2^{1/4} + 2^{1/8} + 1} + \frac{1}{2^{1/4} - 2^{1/8} + 1} - 2 \cdot \frac{2^{1/4} - 1}{2^{1/2} + 2^{1/4} + 1} \right] \cdot \frac{2^{1/2} + 2^{1/4} + 1}{2} = 1 + \lg 4 + \sqrt{4 \lg^2 2 + \lg 5 - \lg 8}.$$

37. For what values ​​of the parameter $t$ the equation
    $$1 + \sqrt{x + 2 \lg t} = \sqrt{x - 1}$$
    has valid solutions?

V. V. Galdbere