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

Introduction

In May 2015, I graduated from the undergraduate faculty of general and applied physics at the Moscow Institute of Physics and Technology. I mainly deal with quantum field theory, but at that moment I decided that I would like to delve deeper into the modern world of computer science, that I could try to combine MIPT with Yandex SHAD (two master's programs). At that time, everyone had already heard ShAD, everyone around just kept saying what a tough course of algorithms there was, I liked the site (lol), the subjects of the courses, and I decided to do it.

In this post, I would like to talk about how my admission to the ShAD took place, to tell me my decision of the exam option (there are not very many analyzes of ShAD tasks on Runet) and talk about what I liked / did not like about this wonderful institution.

Online selection was not difficult, 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 a lazy would not write a script for each task to check the answer (I generally solved only one problem So). Today, as far as I know, they give some limited time, within a few hours.

After the online phase, I was invited to the exam. I was preparing for the exam for about a week, and by itself, he gave me great pleasure. In 4 hours it was necessary to solve 7 problems in mathematics and compose one algorithm (a total of 8 tasks). The mathematics required is the most diverse: linear algebra, mat. analysis (almost$$ϵ - δ 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 some languages ​​or skills there (in general, it later turned out that ShAD 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 on the exam. Throwing in three cups of espresso and tincture of Eleutherococcus, I was able to cleanly solve seven of the eight problems, and I did not even have time to look at the eighth.

My exam

Task 1

Square matrix $$A is such that$$tr A X = 0 for any traceless$$The X . Prove that the matrix$$A scalar.

Decision

This task immediately reminded me of a different, slightly more complicated problem from the Fiztekh 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, here you need to take advantage of the fact that the matrix$$X is any, and therefore, considering matrices$$X of various kinds, we can impose restrictions on the marina$$A .

First, consider the matrix$$X view$$X i j = δ i k δ j l , that is, a matrix in which all elements of 0 except the unity in$$k- th line on$$l- th position. Since we remember that$$X is a traceless matrix,$$l ≠ k . Then the equation from the condition is rewritten in the form (if in the formula the index is repeated twice,summing isimplied by it)

$$tr A X = A i j X j i = A i j δ i k δ j l = A k l = 0( k ≠ l ) .

That is, with a flick of the wrist we proved that in the matrix $$A outside the diagonal are only zeros. If we drop the indices, then we just multiplied the matrix$$A on a matrix of a special form and got some kind of restriction.

Now we know that the matrix$$A = diag ( λ 1 , λ 2 , ... , λ n ) is diagonal. How to prove that all its eigenvalues ​​are equal? To do this, we now consider the matrices$$X = δ i l δ j l - δ i k δ j k , i.e., matrices with$$l -th diagonal element should$$+ 1 , and on$$k -th -$$- 1 . Similarly, multiplying the matrices and taking the trace, we get$$λ l - λ k = 0 (the trace turned out to be equal to only the difference of the pair of eigenvalues). By condition for any$$the k ,l this equality must be satisfied, whence it follows that all eigenvalues ​​are equal, the problem is solved.

Task 2

Arriving for a written exam at the SHAD, 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 the other students.

Decision

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

Consider an arbitrary four students$$A ,$$Bed and ,$$the C ,$$D . Suppose, on the contrary, none of them are familiar with all the other students. But by condition, one of the students (let it be$$A ) knows all three remaining. 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 our ears and consider the four$$A ,$$Bed and ,$$the C ,$$The 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 are working on the contrary, then every student in the four$$A B C D does not know anyone. If in the case of$$And we were forced to take a stranger from the side, then in the case of$$B There are two possible cases. If a$$B does not know someone from inside the four$$A B C D , then it can only be$$D since$$A and$$C he already knows. But in this case, consider the four$$A X B D . Given the fact that$$A does not know$$X and$$D don't know$$B , we cannot satisfy the condition that at least one student in the four knows all the other three.

In this way,$$B and$$D should be familiar, while u$$B must be an unfamiliar student by$$The Z . But here comes the end. Consider the four$$A B X Z . It is impossible to arrange for someone to know the other three students as they are unfamiliar$$A and$$the X ,$$B and$$Z , the problem is solved.

Task 3

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

Decision

As said in one joke about the ensign, “what is there to think? it’s necessary to shake! ” Fix a point$$A , and the point$$We parameterize the angle$$φ between radius vectors$$O A and$$O B . Consider the angles$$φ ∈ [ 0 , π ] . The area of ​​the smaller segment will then be equal to$$S ( φ ) = φ R 2 / 2 - ( 1 / 2 ) R 2 sin φ , then

$$¯ S ( φ ) =1π π ∫ 0dφS(φ)=(R2/2π) π ∫ 0dφ(φ-sinφ)=R22 π ( π 22 -2)=πR2/4-R2/π.

Task 4

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

Decision

Hands got cold in this place, 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 you can only spend the memory constant. Fix some current balance$$r (first$$r = 0 , at the end$$r = 4 ) and go through the array from start to finish with a pointer$$j . We also get the so-called insert index$$i , which initially indicates the beginning of the array and then only increases.

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

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

Task 5

Explore the convergence and absolute convergence series

$$+ ∞ ∑ n=0sinπ√n 2 + 1 .

Decision

SHAD, are you serious? Well, why? Okay ... we

’ll write

$$sin π √n 2 + 1 =sinπn√1 + 1 / n 2 =sin ( πn+ π2 n +o(n-2))=(-1)nsin(π2 n +o(n-2))== ( - 1 ) n ( π2 n +o(n-2)).

It can be seen that the series converges conditionally. Term$$o ( n - 2 ) converges on an integral basis, and the term$$( - 1 ) n / n converges according to the Dirichlet criterion. If we consider absolute convergence, we must recall the property$$| | | a + b | ⩾ | a | - | b | . Term$$ still converges on the same integral basis, but the term $$ diverges as the sum of a 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, having asked for a certain set of such bones once, to simulate a throw (a) of the correct 7-sided bone, (b) of the correct 15-sided 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: pyramid (4), cube (6), octahedron (8), dodecahedron (12), icosahedron (20).

Note that we can simulate a throw$$- of the granular bone, taking the remainder of the division by five of what fell on the icosahedron. Similarly, we can simulate a throw of a trihedral bone, dividing the remainder of the division by$$from everything that falls on the pyramid. Then if$$ and $$ - the results of the rolls of such bones, then the result of the throw $$-face bone we will recount as $$Note that here all outcomes are equally probable, that is, this is really the correct bone.

However, the cast$$- The facet bone cannot be simulated. At this point, it became clear that if we have an honest cube$$, then we can simulate any dividers $$as well as if we have two honest dice $$ and $$we can simulate a work $$. That is why we can simulate any number that can be decomposed into prime factors.$$, $$ and $$(there are no others among the Platonic solids).

Suppose we want to simulate a number that does not decompose into the product of such prime factors. Kinem for this$$ bones $$, and the numbers that fell out at all $$ bones, we write in one vector that describes a point in a hypercube of size $$. If we want to pretend$$-shaped bone, we must divide the points in this space into $$ groups of equal size, which cannot be done, because otherwise the work $$ will have to be divided into $$and we haven’t received this yet.

Task 7

Let be $$, $$Are square real matrices. Prove that$$

Decision

Here I was very helped by the formula, which is terribly loved in theory. physics, and I strongly recommend taking it into service for those who go to the exam. For any matrix$$, in which all eigenvalues ​​are positive, is true $$

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 an expression of the form$$which can be arranged in a row only if $$. This completely corresponds to the radius of convergence of the logarithm, but only in multidimensional space.

To get started, let's reformulate the assignment and prove that$$ for any real number $$, and then just take $$Why is this needed? This is necessary in order to make the matrix norm$$ less $$. When considered very small$$, you can safely write such a chain (under the trace of the matrix you can move around in a loop):

$$

Here we brazenly used the property $$

Ok, we proved this formula for some segment $$near zero. How now to spread it to everything$$, in particular $$? Note that the left and right sides of the proved formula contain polynomials in$$(because the determinant includes only works)! That is, we proved that two polynomials coincide on a segment, but it immediately follows that they coincide everywhere on a number line.

Task 8

Sitting at the table $$miners, in front of each of whom lies a heap of golden sand. Every minute, all prospectors take half of the sand from the left heap and half from the right heap and lay it to themselves. Describe the asymptotic behavior of the amount of sand in piles for an arbitrary$$.

Decision

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

$$

Where $$ - the amount of gold from the prospector sitting in position $$ during $$. Coordinate$$ closed in a circle $$.

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

$$

This farm must satisfy our difference equation, therefore, we substitute this sum into the equation explicitly and require that the coefficients for all exponents on the left and on the right coincide. In fact, we just made a basis change (switched to plane waves) and require that in the new basis we have the same coefficients before the basis vectors. This leads to the equation

$$

For fixed $$this is an equation in itself, which is likewise solved by another Fourier transform. We will denote the Fourier transform by the coordinate by the tilde, and by the coordinate + time - by the cap. Writing down

$$

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

$$

We got the so-called dispersion relation. That is, plane waves here may not be arbitrary$$, but only with those who obey this formula. This dispersion relation is a reformulation of the original equation in a new basis. Let us capture some momentum$$ and try to find the appropriate frequency $$which may exist in such a system.

If the cosine on the right is less than unity in absolute value, then the complex frequency will have to be substituted into the complex exponent$$(which will have the imaginary part). It is easy to see that the imaginary part of this exponent will then be positive ($$), then it will enter the exponent as $$-2 \ pi \ omega '' / Tand reduce its modulus after cosine. But, fortunately, such frequencies will quickly go to rest. Indeed, if we look at the contribution that modes with such frequencies will make, we will see that they will decay exponentially in time. Such modes will not contribute to the asymptotic behavior.

Therefore, we have two cases left. If a$$ - odd, then the cosine is equal $$ modulo only once when $$. In this case$$. This plane wave is just average. It turns out, with odd$$ there is no interesting dynamics at infinity: the wealth of prospectors converges to the average of what was originally:

$$

If $$ odd, then the cosine can still be equal $$, if a $$, and then an additional solution is possible $$ (only the term in which the material $$, we wrote it down). In this case

$$

Similarly, only one term remains, we write it. Now we know almost everything about the solution. This is some kind of construction that changes sign both in time steps and in space steps. Notice that if here$$was not even, it would violate the circularity of the circle. It remains only to find the value of the coefficient.

Take a look at the inverse Fourier transform:

$$

At $$ left is $$, and on the right it’s just $$, that is, the alternative sum of wealth at the initial time. So we get

$$

Afterword

For the control gave seven points out of eight. I did not write about the trick with$$in the problem of matrices, but simply laid out - this was not noticed. Then there was an interview. They didn’t ask me anything about the exam, they just talked for my life, why I want to enter the school of law (prepare the answer to this question!). Guys who had fewer tasks were asked to solve something on the spot, so it's better to come in a fighting mood. There will also be an opportunity to filter out undeliverable points for the control.

I liked the training at the SHAD very much. Here they always push some theory, read on the latest articles, and not on 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 are running wide: there is for every taste, from the very practical to the very theoretical, almost all modern branches of computer science are covered by fresh articles.
2. Teachers in the bulk of the fire, it was not too lazy to go to the other end of Moscow to listen to the evening after a lab.
3. Cool presentation of the material, everything is recorded on video, you can not go. You can rent out remotely, but you still want to go.
4. Great classmates!

As such, I did not even notice the cons. Curators treat everyone kindly, do not rush to deduct. Yandex (Mamontov’s premises) has a very pleasant atmosphere, air conditioning, delicious food, comfortable chairs, a human atmosphere! And, most importantly, quite a lot of freedom in choosing courses and your profile, even within the framework of the chosen specialty.

Go to the SHAD! And, yes, I forgot, be sure to deal with the formula for the complete decomposition of the determinant

$$