Analysis of the entrance exam ShAD-2015 and memories of the graduate of 2017

Introduction

In May of distant 2015, I graduated from the Faculty of General and Applied Physics of the Moscow Institute of Physics and Technology. I mostly do quantum field theory, but at that moment I decided that I would like to get more insight into the modern world of computer science, that you can try to combine MIPT with Yandex SAD (two magistracies). ShAD was already widely known around the world, they were just around saying what a tough course of algorithms was, I liked the site (lol), the topics of the courses, and I decided to enter.

In this post I would like to talk about how my admission to the ShAD took place, tell my decision of the examination option (there are not very many analyzes of the ShAD assignments in the runet) and talk about what I liked / didn’t like in this wonderful place.

Online selection was given without much difficulty, in 2015 they gave 12 tasks for a month, of which more than half were combinatorics with the answer in the form of a number, and only lazy would not write a script on each task to check the answer (I solved only one So). Today, as far as I know, they give some limited time, within a few hours.

After the online stage, I was invited to the exam. I was preparing for the exam for about a week, and by itself it gave me great pleasure. In 4 hours it was necessary to solve 7 problems in mathematics and create one algorithm (a total of 8 tasks). Mathematics is required the most diverse: linear algebra, mat. analysis (almost $$$\ epsilon- \ delta$ formalism), combinatorics and theory. ver., graphs, Fourier transform, etc. It seems to me that it is very correct for applicants to demand knowledge of mathematics, and not any languages ​​or skills there (in general, later it turned out that the SAD is focused on knowledge in essence, and not on technical details).
')
I would like to devote this post to the analysis of the option that I got in the exam. Throwing three cups of espresso and eleutherococcus tincture, I was able to solve seven problems out of eight in a clean way, and I did not even have time to look at the eighth.

My exam

Task 1

Square matrix $$$A$ such that $$$\ mbox {tr} AX = 0$ for any traceless $$$X$ . Prove that the matrix $$$A$ scalar.

Decision

This task immediately reminded me of another, slightly more complicated task from the Physics and Technology exam in linear algebra in the first semester, where it was necessary to prove that only a scalar matrix commutes with all matrices. As there, you need to take advantage of the fact that the matrix $$$X$ any, which means considering the matrices $$$X$ different types, we can impose restrictions on maritsa $$$A$ .

First consider the matrix $$$X$ kind of $$$X_ {i j} = \ delta_ {ik} \ delta_ {j l}$ , that is, a matrix, in which all elements of 0 except for edinichki, standing in $$$k$ line in $$$l$ -th position. Since we remember that $$$X$ - traceless matrix $$$l \ neq k$ . Then the equation from the condition is rewritten in the form (if the index is repeated twice in the formula, it means summation )

$$

$$\ mbox {tr} AX = A_ {ij} X_ {ji} = A_ {ij} \ delta_ {ik} \ delta_ {jl} = A_ {kl} = 0 \; (k \ neq l).$$

That is, with a slight movement of the hand, we proved that in the matrix $$$A$ outside the diagonal are only zeros. If we discard the indices, then we just multiplied the matrix $$$A$ on the matrix of a special type and got some kind of restriction.

Now we know that the matrix $$$A = \ mbox {diag} (\ lambda_1, \ lambda_2, \ ldots, \ lambda_n)$ - diagonal. How to prove that all her own numbers are equal? For this we now consider the matrices $$$X = \ delta_ {i l} \ delta_ {j l} - \ delta_ {i k} \ delta_ {j k}$ , that is, matrices that have $$$l$ that element of the diagonal is $$$+ 1$ and on $$$k$ -t $$$-1$ . Similarly, multiplying the matrix and taking the trail, we get $$$\ lambda_l - \ lambda_k = 0$ (the trace was only equal to the difference of a pair of eigenvalues). By condition for any $$$k, \; l$ this equality must be fulfilled, whence it follows that all eigenvalues ​​are equal, the problem is solved.

Task 2

Having come to the written exam at the ShAD, the students realized that among any four people at least one was already familiar with the three remaining. Prove that then among any four people at least one is already familiar with all other students.

Decision

This task almost killed me, on the exam I came up with a terribly difficult and poor solution. Here it is. I recommend in the process of reading to draw various options in the form of graphs, then it becomes even not so bad!

Consider arbitrary four students $$$A$ , $$$B$ , $$$C$ , $$$D$ . Suppose, on the contrary, none of them is familiar with all the other students. But according to the condition one of the students (let it be $$$A$ ) knows all the remaining three. On the contrary, we concluded that there is some other student $$$X$ which $$$A$ does not know.

In this place we will make a feint with ears and consider the four $$$A$ , $$$B$ , $$$C$ , $$$X$ . In this four there should be a student who knows all three. It can't be $$$A$ or $$$X$ , since they are not familiar, so let $$$B$ knows all three (it doesn't matter, it can be $$$C$ until the symmetry between them is broken).

Since we work on the contrary, each student in the four $$$ABCD$ doesn't know anyone. If in the case of $$$A$ we were forced to take a stranger from the side then in the case of $$$B$ two cases are possible. If a $$$B$ doesn't know someone from inside the four $$$ABCD$ then it can only be $$$D$ , because $$$A$ and $$$C$ he already knows. But in this case, consider the four $$$AXBD$ . Given that $$$A$ does not know $$$X$ and $$$D$ does not know $$$B$ , we cannot satisfy the condition that at least one student in the four know all the other three.

In this way, $$$B$ and $$$D$ should be familiar, and $$$B$ there must be an unfamiliar student from $$$Z$ . But here comes the end. Consider the four $$$ABXZ$ . It is impossible to arrange it so that someone knows the other three students as strangers $$$A$ and $$$X$ , $$$B$ and $$$Z$ , the problem is solved.

Task 3

Two random points are selected on the circle. $$$A$ , $$$B$ find the expected area of ​​the smallest of the segments for which the chord $$$Ab$ breaks a circle.

Decision

As stated in one joke about the ensign, “what is there to think about? need to shake! Fix the point $$$A$ and point $$$B$ parameterize the angle $$$\ varphi$ between radius vectors $$$OA$ and $$$OB$ . Consider the corners $$$\ varphi \ in [0, \ pi]$ . The area of ​​the smaller segment will then be equal to $$$S (\ varphi) = \ varphi R ^ 2/2 - (1/2) R ^ 2 \ sin \ varphi$ then

$$

$$\ bar {S (\ varphi)} = \ frac {1} {\ pi} \ int \ limits_ {0} ^ {\ pi} d \ varphi S (\ varphi) = (R ^ 2/2 \ pi) \ int \ limits_ {0} ^ {\ pi} d \ varphi (\ varphi - \ sin \ varphi) = \ frac {R ^ 2} {2 \ pi} \ left (\ frac {\ pi ^ 2} {2 } - 2 \ right) = \ pi R ^ 2/4 - R ^ 2 / \ pi.$$

Task 4

Dan array of $$$n$ natural numbers. Suggest a method of sorting it by the remainder of dividing by 5 for linear time and constant memory.

Decision

In this place the hands turned cold, I'm not a programmer! But calmly, I told you, this is a math exam.

Sorting needs to be done in-place, since in addition only the memory constant can be spent. Fix some current balance $$$r$ (at first $$$r = 0$ , in the end $$$r = 4$ ) and go through the array from start to finish pointer $$$j$ . Also we will get the so-called insertion index $$$i$ which initially points to the beginning of the array and then only increases.

If the array element $$$A [j]$ has a residue $$$r$ we have to swap it with $$$A [i]$ . After this index $$$i$ we increase until $$$A [i] = r (\ mbox {mod}) 5$ and stop at the moment when this equality is violated. Then we grow the index again. $$$j$ until we find again $$$A [j] = r (\ mbox {mod} 5)$ , to throw him on the position $$$i$ .

In this algorithm there is a certain invariant, namely, behind the index $$$i$ All numbers are already arranged correctly (sorted by remainder). With one pass $$$j$ across the array behind $$$i$ will lie all the elements that when divided by $$$5$ give the remainder $$$0$ . With the next pass, the same fate will befall those who share with the rest $$$1$ and so on. Total required 4 passes (the fifth will no longer be needed).

Task 5

Explore the convergence and absolute convergence series

$$

$$\ sum \ limits_ {n = 0} ^ {+ \ infty} \ sin \ pi \ sqrt {n ^ 2 + 1}.$$

Decision

Shad, are you serious? Well, that's why? Okay…

Write

$$

$$\ sin \ pi \ sqrt {n ^ 2 + 1} = \ sin \ pi n \ sqrt {1 + 1 / n ^ 2} = \ sin \ left (\ pi n + \ frac {\ pi} {2 n } + \ mathcal {o} (n ^ {- 2}) \ right) = (-1) ^ n \ sin \ left (\ frac {\ pi} {2 n} + \ mathcal {o} (n ^ { -2}) \ right) = \\ = (-1) ^ n \ left (\ frac {\ pi} {2 n} + \ mathcal {o} (n ^ {- 2}) \ right).$$

It can be seen that the series converges conditionally. Term $$$\ mathcal {o (n ^ {- 2})}$ converges on an integral basis, and the term $$$(- 1) ^ n / n$ converges on the basis of Dirichlet. If we consider absolute convergence, we must recall the property $$$| a + b | \ geqslant | a | - | b |$ . Term $$$b = \ mathcal {o (n ^ {- 2})}$ still converges on the same integral feature, but the term $$$a \ sim 1 / n$ diverges as the sum of the harmonic series, and therefore the whole series does not converge.

Task 6

You have an unlimited number of bones in the form of all possible regular polyhedra. Is it possible, once asking for a set of such bones, to simulate a roll (a) of a correct 7-faced bone, (b) of a regular 15-faced bone?

Decision

I did not even have time to read this task on the exam itself, so it was like homework. There are five regular polyhedra in total: pyramid (4), cube (6), octahedron (8), dodecahedron (12), icosahedron (20).

Note that we can simulate a throw $$$5$ -faced bone, taking the remainder of the division by five of what fell on the icosahedron. Similarly, we can simulate a throw of a triangular bone, dividing the remainder of the division by $$$3$ from everything that falls on the pyramid. Then if $$$d_3$ and $$$d_5$ - the results of throwing such bones, the result of throwing $$$15$ -face we will count as $$$d_ {15} = 5 (d_3 - 1) + d_5.$ Note that here all the outcomes are equally probable, that is, this is indeed the correct bone.

However, the cast $$$7$ - the face bone cannot be simulated. By this time, it became clear that if we have an honest cube $$$d_i$ then we can simulate any dividers $$$i$ and also if we have two fair dice $$$d_i$ and $$$d_j$ we can simulate a piece $$$d_ {ij}$ . That is why we can simulate any number that decomposes into prime factors. $$$2$ , $$$3$ and $$$5$ (there are no others among the Platonic solids).

Suppose we want to simulate a number that does not decompose into a product of such prime factors. Kinema for this $$$N$ bones $$$d_ {i_1}, \; d_ {i_2}, \; \ ldots, \; d_ {i_N}$ and numbers dropped by all $$$N$ bones, we write in one vector that describes a point in the hypercube size $$$i_1 \ times i_2 \ times \ ldots \ times i_N$ . If we want to simulate $$$7$ -sized bone, we must divide the points in this space by $$$7$ groups of equal size that can not be done, because otherwise the product $$$i_1 \ times i_2 \ times \ ldots \ times i_N$ will have to be divided by $$$7$ , but this we have not received.

Task 7

Let be $$$A$ , $$$B$ - square real matrices. Prove that $$$\ mbox {det} \ left (E - AB \ right) = \ mbox {det} \ left (E - BA \ right).$

Decision

Here the formula that I love terribly in theory really helped me. physics, and I strongly recommend it to adopt for those who go to the exam. For any matrix $$$A$ which all eigenvalues ​​are positive is true $$$\ mbox {det} A = \ exp \ mbox {tr} \ log A.$

How to apply our formula here? I will say right away, we will lay out the logarithm in a row. Under the logarithm we will have the expression of the form $$$E - AB$ that can be laid out in a row only if $$$| AB | _2 <1$ . This completely corresponds to the radius of convergence of the logarithm, but only in multidimensional space.

To begin with, let us reformulate the assignment and prove that $$$\ mbox {det} \ left (E - \ lambda AB \ right) = \ mbox {det} \ left (E - \ lambda BA \ right)$ for any real number $$$\ lambda$ and then just take $$$\ lambda = 1.$ Why do you need it? This is necessary in order to make the norm of matrices. $$$| AB | _2$ less $$$1$ . When considered very small $$$\ lambda$ , you can safely write such a chain (under the matrix trace, you can move around the loop):

$$

$$\ mbox {det} \ left (E - \ lambda AB \ right) = \ exp \ mbox {tr} \ log (E - \ lambda AB) = \ exp \ mbox {tr} \ left (- \ lambda AB - \ frac {\ lambda ^ 2 (AB) ^ 2} {2} - \ frac {\ lambda ^ 3 (AB) ^ 3} {3} - \ ldots \ right) = \\ = \ exp \ mbox {tr} \ left (- \ lambda BA - \ frac {\ lambda ^ 2 (BA) ^ 2} {2} - \ frac {\ lambda ^ 3 (BA) ^ 3} {3} - \ ldots \ right) = \ mbox {det} (E - \ lambda BA).$$

Here we brazenly used the property $$$\ mbox {tr} (AAAAA \ ldots AAABBBBB \ ldots BBB) = \ mbox {tr} (BBBBB \ ldots BBBAAAAA \ ldots AAA).$

Well, we have proven this formula for some segment. $$$\ lambda$ near zero. How now to extend it to all $$$\ lambda$ , in particular $$$\ lambda = 1$ ? Note that in the left and right sides of the proven formula there are polynomials on $$$\ lambda$ (after all, only works are included in the determinant)! That is, we have proved that two polynomials coincide on a segment, but this immediately implies that they coincide everywhere on the number line.

Task 8

Sit at the table $$$n$ prospectors, in front of each of which lies a handful of golden sand. Every minute all the miners take half of the sand from the left pile and half from the right pile and put it to themselves. Describe the asymptotic behavior of the amount of sand in piles for an arbitrary $$$n$ .

Decision

In essence, we are invited to find the asymptotics of the solution of such a difference scheme (for any initial conditions):

$$

$$a (x, t + 1) = \ frac {a (x - 1, t) + a (x + 1, t)} {2},$$

Where $$$a (x, t)$ - the amount of gold in the prospector sitting in the position $$$x$ during $$$t$ . Coordinate $$$x$ closed in a circle $$$x = 0, 1, \ ldots, n - 1$ .

Such things are solved in many ways, but the most natural is the discrete Fourier transform. We are dealing with a function that is periodic $$$x$ and it can and should be decomposed into the final Fourier sum by $$$x$ :

$$

$$a (x, t) = \ frac {1} {N} \ sum \ limits_ {k = 0} ^ {n - 1} \ sum \ limits _ {\ omega = 0} ^ {T - 1} \ tilde { a} (k, t) e ^ {2 \ pi ikx / n}.$$

This economy must satisfy our difference equation, so we substitute this sum explicitly in the equation and require that the coefficients for all the exponents on the left and right coincide. In fact, we simply made a replacement of the basis (went over to flat waves) and demand that in our new basis the coefficients in front of the basis vectors coincide. This leads to the equation

$$

$$\ tilde {a} (k, t + 1) = \ frac {e ^ {2 \ pi ik / n} \ tilde {a} (k, t) + e ^ {- 2 \ pi ik / n} \ tilde {a} (k, t)} {2} = \ cos (2 \ pi k / n) \ tilde {a} (k, t).$$

For fixed $$$k$ it is an equation in itself, which is similarly solved by another Fourier transform. We will denote the Fourier transform by the coordinate by the tilde, and by the coordinate + time by the lid. Writing down

$$

$$\ tilde {a} (k, t) = \ frac {1} {T} \ sum \ limits _ {\ omega = 0} ^ {T - 1} \ hat {a} (k, \ omega) e ^ { 2 \ pi i \ omega t / T},$$

substituting this in the last equation and again equating the exponents, we get

$$

$$e ^ {2 \ pi i \ omega} = \ cos (2 \ pi i k).$$

We obtained the so-called dispersion relation. That is, plane waves here may not be arbitrary. $$$k, \; \ omega$ , but only with those who obey this formula. This dispersion relation is a reformulation of the original equation in a new basis. Suppose we have fixed some momentum $$$k$ and trying to find the appropriate frequency $$$\ omega$ which may exist in such a system.

If the cosine of the right modulo is less than one, then the complex exponent will have to substitute the complex frequency $$$\ omega = \ omega '+ i \ omega' '$ (which will have an imaginary part). It is easy to see that the imaginary part of this exponent will then be positive ( $$$\ omega ''> 0$ ), then it will enter the exhibitor as$$ $ inline $ -2 \ pi \ omega '' / T $ inline $ and reduce its module after cosine. But, fortunately, such frequencies will quickly retire. Indeed, if we look at the contribution that modes with such frequencies will give, we will see that they will exponentially decay in time. Such modes asymptotics will not contribute.

Therefore, we have two cases. If a $$$n$ - odd, the cosine is equal $$$1$ modulo only once when $$$k = 0$ . In this case $$$\ omega = 0$ . This plane wave is only average. It turns out, with odd $$$n$ there is no anthropic dynamics in infinity: the wealth of the prospectors converges to the average of what was originally:

$$

$$a (x, t) \ to \ frac {1} {N} \ sum \ limits_ {b = 0} ^ {n - 1} a (b, 0).$$

If $$$n$ odd, the cosine may still be equal $$$-1$ , if a $$$k = n / 2$ but then an additional solution is possible $$$\ omega = T / 2, \; \ tilde {a} (k, t) = \ hat {a} (k, T / 2) (-1) ^ t / T$ (in the sum, only the term in which the real $$$\ omega$ , we recorded it). In this case

$$

$$a (x, t) = \ frac {1} {N} a (n / 2, t) = \ frac {1} {NT} (-1) ^ x (-1) ^ t \ hat {a} (n / 2, T / 2).$$

Similarly, there remains only one term, and we write it. Now we know almost everything about the decision. This is some kind of such a design that changes the sign as with a step in time, and with a step in space. Notice that if here $$$n$ it was not even, it would break the circularity around the circle. It remains only to find the value of the coefficient.

Let's look at the inverse Fourier transform:

$$

$$\ hat {a} (n / 2, T / 2) (-1) ^ t / T = \ tilde {a} (n / 2, t) = \ sum \ limits_ {x = 0} ^ {n - 1} a (x, t) e ^ {- 2 \ pi i (n / 2) x / n}.$$

With $$$t = 0$ on the left is $$$\ hat {a} (k, \ omega) / T$ and the one on the right is just $$$\ sum \ limits_ {x = 0} ^ {n - 1} a (x, 0) (-1) ^ x$ , that is, the alternating amount of wealth at the original moment in time. So we get

$$

$$a (x, t) \ to \ frac {(- 1) ^ x (-1) ^ t} {N} \ sum \ limits_ {b = 0} ^ {n - 1} a (b, 0) ( -1) ^ b + \ frac {1} {N} \ sum \ limits_ {b = 0} ^ {n - 1} a (b, 0).$$

Afterword

For the control gave seven points out of eight. I have not written about the trick with $$$\ lambda$ in the problem about the matrix, and just laid out - this was not noticed. Then there was the interview. They did not ask me anything about the exam, they just talked for life, why I want to enter the SAD (prepare the answer to this question!). The guys, who had fewer tasks, were asked to solve something on the spot, so it would be better to come to the fighting mood. There will also be an opportunity to clear the undelivered for the control points.

I really liked the training in the ShAD. Some theory is being pushed here all the time, they are read by the most recent articles, and not by 50-year-old books, and, most importantly, the theory is always supported by a very suitable and logical practice.

Pros:

1. Very cool courses, eyes run: there is for every taste, from very practical to very theoretical, almost all modern branches of computer science for fresh articles.
2. Teachers in the bulk of the fire, it was not too lazy to go after the labs in the evening to the other end of Moscow to listen.
3. Great presentation of the material, everything is recorded on video, you can not go. You can donate remotely, but you still want to go.
4. Healthy fellow students!

As such, the cons, I did not even notice. Curators treat everyone in a kind way, they don’t rush to deduct. In Yandex (Mamontov premises) there is a very pleasant atmosphere, air conditioners, snacks, comfortable chairs, human furnishings! And, most importantly, quite a lot of freedom in choosing courses and your profile, even within the chosen specialty.

Go to the shad! And, yes, I forgot, make sure you understand the formula for the complete decomposition of the determinant

$$

$$\mbox{det} A = \epsilon^{i_1 i_2 i_3\ldots i_N} a_{1 i_1} a_{2 i_2} \ldots a_{N i_N}.$$