Prove that the Catalan numbers satisfy the recurrence relationship \(C_n = C_0C_{n-1} + C_1C_{n-2} + \dots + C_{n-1}C_0\). The definition of the Catalan numbers \(C_n\) is given in the handbook.
A square grid on the plane and a triangle with vertices at the nodes of the grid are given. Prove that the tangent of any angle in the triangle is a rational number.
Prove that there is at most one point of an integer lattice on a circle with centre at \((\sqrt 2, \sqrt 3)\).
\(N\) points are given, no three of which lie on one line. Each two of these points are connected by a segment, and each segment is coloured in one of the \(k\) colours. Prove that if \(N > \lfloor k!e\rfloor\), then among these points one can choose three such that all sides of the triangle formed by them will be colored in one colour.
Peter marks several cells on a \(5 \times 5\) board. His friend, Richard, will win if he can cover all of these cells with non-overlapping corners of three squares, that do not overlap with the border of the square (you can only place the corners on the squares). What is the smallest number of cells that Peter should mark so that Richard cannot win?
Every day, James bakes a square cake size \(3\times3\). Jack immediately cuts out for himself four square pieces of size \(1\times1\) with sides parallel to the sides of the cake (not necessarily along the \(3\times3\) grid lines). After that, Sarah cuts out from the rest of the cake a square piece with sides, also parallel to the sides of the cake. What is the largest piece of cake that Sarah can count on, regardless of Jack’s actions?
In honor of the March 8 holiday, a competition of performances was organized. Two performances reached the final. \(N\) students of the 5th grade played in the first one and \(n\) students of the 4th grade played in the second one. The performance was attended by \(2n\) mothers of all \(2n\) students. The best performance is chosen by a vote of the mothers. It is known that half of the mothers vote honestly, i.e. for the performance that was truly better and the mothers of the other half in any case vote for the performance in which their child participates.
a) Find the probability of the best performance winning by a majority of votes.
b) The same question but this time more than two performances made it to the final.
A fly crawls along a grid from the origin. The fly moves only along the lines of the integer grid to the right or upwards (monotonic wandering). In each node of the net, the fly randomly selects the direction of further movement: upwards or to the right. Find the probability that at some point:
a) the fly will be at the point \((8, 10)\);
b) the fly will be at the point \((8, 10)\), along the line passing along the segment connecting the points \((5, 6)\) and \((6, 6)\);
c) the fly will be at the point \((8, 10)\), passing inside a circle of radius 3 with center at point \((4, 5)\).
A fly moves from the origin only to the right or upwards along the lines of the integer grid (a monotonic wander). In each node of the net, the fly randomly selects the direction of further movement: upwards or to the right.
a) Prove that sooner or later the fly will reach the point with abscissa 2011.
b) Find the mathematical expectation of the ordinate of the fly at the moment when the fly reached the abscissa 2011.
In his laboratory, the Scattered Scientist created a unicellular organism, which, with a probability of 0.6 is divided into two of the same organisms, and with a probability of 0.4 dies without leaving any offspring. Find the probability that after a while the Scattered Scientist will not have any such organisms.