Suppose \(a>b\) and \(c>d\). Prove that \(a+c>b+d\).
Using mathematical induction prove that \(2^n \geq n + 1\) for all natural numbers.
Circles and lines are drawn on the plane. They divide the plane into non-intersecting regions, see the picture below.
Show that it is possible to colour the regions with two colours in such a way that no two regions sharing some length of border are the same colour.
Consider a number consisting of \(3^n\) digits, all ones, such as 111 or 111111111 for example. Show that such a number with \(3^n\) digits is divisible by \(3^n\).
Numbers \(1,2,\dots,n\) are written on a whiteboard. In one go Louise is allowed to wipe out any two numbers \(a\) and \(b\), and write their sum \(a+b\) instead. Louise enjoys erasing the numbers, and continues the procedure until only one number is left on the whiteboard. What number is it? What if instead of \(a+b\) she writes \(a+b-1\)?
Prove that
(a) \[1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{1}{6} n (n+1)(2n+1)\]
(b) \[1^2 + 3^2 + 5^2 + \dots + (2n-1)^2 = \frac{1}{3} n (2n-1)(2n+1)\].
Definition. The sequence of numbers \(a_0, a_1, \dots , a_n, \dots\), which, with the given \(p\) and \(q\), satisfies the relation \(a_{n + 2} = pa_{n + 1} + qa_n\) (\(n = 0,1,2, \dots\)) is called a linear recurrent sequence of the second order.
The equation \[x^2-px-q = 0\] is called a characteristic equation of the sequence \(\{a_n\}\).
Prove that, if the numbers \(a_0\), \(a_1\) are fixed, then all of the other terms of the sequence \(\{a_n\}\) are uniquely determined.
The bus has \(n\) seats, and all of the tickets are sold to \(n\) passengers. The first to enter the bus is the Scattered Scientist and, without looking at his ticket, takes a random available seat. Following this, the passengers enter one by one. If the new passenger sees that his place is free, he takes his place. If the place is occupied, then the person who gets on the bus takes the first available seat. Find the probability that the passenger who got on the bus last will take his seat according to his ticket?
On a circle of radius 1, the point \(O\) is marked and from this point, to the right, a notch is marked using a compass of radius \(l\). From the obtained notch \(O_1\), a new notch is marked, in the same direction with the same radius and this is process is repeated 1968 times. After this, the circle is cut at all 1968 notches, and we get 1968 arcs. How many different lengths of arcs can this result in?
On a particular day it turned out that every person living in a particular city made no more than one phone call. Prove that it is possible to divide the population of this city into no more than three groups, so that within each group no person spoke to any other by telephone.