Analysis of the tasks of the entrance test to the JetBrains corporate magistracy at the ITMO University

We already announced to readers of Habr a set for the master’s program “Software Development / Software Engineering” based on ITMO University. The first stage of entrance tests for the program is an online test. And in order to help our applicants prepare for it, we decided to publish an analysis of several mathematical problems from last year’s version.


Task 1

Solve the equation in natural numbers: $ 2 ^ n + 1 = k ^ 2 $.

In the answer indicate the maximum possible value of the work $ k $ and $ n $.

Let’s move the unit to the right side and apply the square difference formula.

$ 2 ^ n = k ^ 2-1 = (k-1) (k + 1). $

Power of two $ 2 ^ n $ divided only by the powers of two. Therefore, we are interested in such $ k $at which $ (k-1) $ and $ (k + 1) $ at the same time are powers of two. At $ k = 3 $ we get the values $ 2 $ and $ 4 $ respectively. There can be no more values, because the distance between the powers of two increases. Thus, we obtain $ k = 3 $ and $ n = 3 $. Answer $ k cdot n = 9 $.

Task 2

What is the sequence limit? $ (1 + frac {1} {n}) ^ {5n + 4} $?

In the response, indicate the number. If necessary, leave three decimal places without rounding.

Highlight wonderful limit:

$ left (1 + frac {1} {n} right) ^ {5n + 4} = left ( left (1 + frac {1} {n} right) ^ n right) ^ 5 cdot left (1 + frac {1} {n} right) ^ 4. $

The limit of the first factor is calculated by the formula of the remarkable limit:

$ lim_ {n to infty} left ( left (1 + frac {1} {n} right) ^ n right) ^ 5 = e ^ 5, $

The limit of the second factor is obvious:

$ lim_ {n to infty} left (1 + frac {1} {n} right) ^ 4 = 1. $

(If a more formal proof is needed, then we can open the brackets and notice that for $ n to infty $ all terms, except 1, tend to zero.) So, both limits exist, therefore

$ lim_ {n to infty} left (1 + frac {1} {n} right) ^ {5n + 4} = lim_ {n to infty} left ( left (1 + frac {1} {n} right) ^ n right) ^ 5 cdot lim_ {n to infty} left (1 + frac {1} {n} right) ^ 4 = e ^ 5 cdot 1 approx 148.413. $

Task 3

Simplify the amount:

$ 1 - frac {1} {4} + frac {1} {3} - frac {1} {16} + frac {1} {9} - frac {1} {64} + fraction { 1} {27} - dots - frac {1} {4 ^ n} + frac {1} {3 ^ n} + dots $

In the response, indicate the number. If necessary, leave three decimal places without rounding.

We represent this alternating series as the difference of two positive sequences:

$ S_1 = 1 + frac {1} {3} + frac {1} {9} + frac {1} {27} + dots frac {1} {3 ^ n} + dots $

$ S_2 = frac {1} {4} + frac {1} {16} + frac {1} {64} + dots + frac {1} {4 ^ n} dots $

According to the formula sums of infinite decreasing geometric sequence we get:

$ S_1 = frac {1} {1 - 1/3} = frac32, quad quad S_2 = frac {1} {4} cdot frac {1} {1 - 1/4} = frac13 . $

As a result, we obtain

$ 1 - frac {1} {4} + frac {1} {3} - frac {1} {16} + frac {1} {9} - frac {1} {64} + fraction { 1} {27} - dots - frac {1} {4 ^ n} + frac {1} {3 ^ n} + dots = S_1 - S_2 = frac {3} {2} - frac { 1} {3} = frac {7} {6} approx 1.166. $

Task 4

Twenty-five people choose numbers, each randomly selects a number from $ 1 $ before $ 100 $ independently of each other. Next, the participants announce the selected numbers in turn (and do it honestly). The first (if there is such a person) who announces a number that has already been announced, receives a prize.

Which person is most likely to win a prize?

We estimate the probability that $ k $-th person receives a prize: he receives a prize if the previous $ k-1 $ the participants were given different numbers, and he is one of the previous ones $ k-1 $ numbers. Probability to name one of the voiced $ k-1 $ numbers is equal

$ p_k = frac {k-1} {100}. $

For participant with number $ i $ the probability of calling a number that has not yet sounded is

$ q_i = frac {100 - i + 1} {100}. $

Then the desired probability is equal to:

$ q_1 cdot q_2 cdot dotsb cdot q_ {k-1} cdot p_k = frac {100} {100} cdot frac {99} {100} cdot dotsb cdot frac {100- k + 2} {100} cdot frac {k-1} {100} = frac {100! cdot (k-1)} {(100 -k +1)! cdot 100 ^ k}. $

It remains to calculate these values ​​for all $ k in {1, dotsb, 25 } $ and find the minimum. This can be done with a small script, a tablet in Excel, or through WolframAlpha:

{0, 0.01, 0.0198, 0.029106, 0.0376438, 0.0451725, 0.0514967, 0.0564747, 0.0600245, 0.0621254, 0.0628157, 0.0621875, 0.0603784, 0.0575607, 0.05393, 0.0496926, 0.0450547, 0.0402113, 0.0353386, 0.307 080760, 0.08708, 0.307, 0.307, 0.307, 0.07 }

From here we get $ k = 11 $ (maximum is reached on the eleventh element of the list $ 0.0628157 $)

Task 5

Each of nine unit squares $ 3 times 3 $square randomly colored red or blue with probability $ frac {1} {2} $. Determine the probability that none of the four squares $ 2 times2 $ not completely red.

In the answer, indicate the number. If necessary, leave three decimal places without rounding.

Squared $ 3 times 3 $ there are 4 different squares $ 2 times 2 $. Let’s call them $ A $, $ B $, $ C $ and $ D $.

Let us denote by the same letters the events that in the corresponding square all cells are colored in red. Then

$ Pr[A] = Pr[B] = Pr[C] = Pr[D] = frac {1} {2 ^ 4}. $

First, we calculate the probability of the opposite event – the probability that one of the squares is completely red $ Pr[Acup Bcup Ccup D]$. In order to calculate it, we use inclusion-exception formula:

$ begin {aligned} Pr[Acup Bcup Ccup D] & = Pr[A] + Pr[B] + Pr[C] + Pr[D]\ & - Pr[Acap B] - Pr[Acap B] - Pr[Acap B] - Pr[Acap B] - Pr[Acap B] - Pr[Acap B]\ & + Pr[Acap Bcap C] + Pr[Acap Bcap D] + Pr[Acap Ccap D] + Pr[Bcap Ccap D]\ & - Pr[Acap Bcap Ccap D]\ & = 4 cdot frac {1} {2 ^ 4} - 4 cdot frac {1} {2 ^ 6} - 2 cdot frac {1} {2 ^ 7} + 4 cdot frac {1} {2 ^ 8} - frac {1} {2 ^ 9} \ & = frac {1} {2 ^ 2} - frac {1} {2 ^ 4} - frac {1 } {2 ^ 6} + frac {1} {2 ^ 6} - frac {1} {2 ^ 9} \ & = frac {1} {4} - frac {1} {16} - frac {1} {512} = frac {128 - 32 - 1} {512} = frac {95} {512}. end {aligned} $

The sought probability that none of the four squares $ 2 times2 $ not completely red, equal

$ 1 - Pr[Acup Bcup Ccup D] = 1 - frac {95} {512} = frac {417} {512} approx 0.814. $

Task 6

Calculate the volume of the rotation figure formed by the selected area during rotation about the vertical axis.

In the answer, indicate the number. If necessary, leave three decimal places without rounding.

In our case, the task is simplified by the fact that the upper part of the rotation figure is half the ball of radius 1. Therefore, the volume of the upper part can be written out immediately – it is equal to $ 2 pi / 3 $ (the volume of the sphere is calculated by the formula $ 4 pi R ^ 3/3 $)

It remains to deal with the lower part bounded by a parabola $ y = 2 (x-2) ^ 2 $. The volume of the rotation figure can be calculated if the volume is divided into cylinders of small height. The volume of the cylinder is equal to the product of the base area ($ pi R ^ 2 $) to a height. Accordingly, we need to obtain the dependence of the radius (the role of radius plays $ x $) from height (from $ y $)

$ y = 2 (x-2) ^ 2 implies x = 2 pm sqrt {y / 2}. $

On the case of interest $ x le 2 $, so $ x = 2 - sqrt {y / 2} $. The volume of the lower part of the figure can be expressed by the following integral:

$ begin {aligned} int limits_0 ^ 2 pi (2 - sqrt {y / 2}) ^ 2 , dy & = pi int limits_0 ^ 2 left (4 - 4 sqrt {y / 2} + y / 2 right) dy \ & = pi left. Left (4y - frac {4} { sqrt {2}} cdot frac {2} {3} cdot y ^ {3/2} + frac {y ^ 2} {2 cdot2} right) right rvert_0 ^ 2 \ & = pi left (4 cdot 2 - frac {4 sqrt {2 }} {3} cdot {2 ^ {3/2}} + 1 right) = pi (9 - 16/3) = 11 pi / 3. end {aligned} $

In total, we obtain $ 2 pi / 3 + 11 pi / 3 = 13 pi / 3 approx 13.613 $.

Conclusion

We hope that this analysis will help applicants to prepare for the online test.
This year it consists of 12 tasks, for which we devote 2 hours. It is worth considering that in addition to mathematical ones, it also has programming tasks. The entire admission process and details of the next steps are described at Master’s program website. If you have any questions, the curators will be happy to answer them by mail or in telegram channel.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *