Given two natural numbers $ w$ and $ n,$ the tower of $ n$ $ w's$ is the natural number $ T_n(w)$ defined by \[ T_n(w) = w^{w^{\cdots^{w}}},\] with $ n$ $ w's$ on the right side. More precisely, $ T_1(w) = w$ and $ T_{n+1}(w) = w^{T_n(w)}.$ For example, $ T_3(2) = 2^{2^2} = 16,$ $ T_4(2) = 2^{16} = 65536,$ and $ T_2(3) = 3^3 = 27.$ Find the smallest tower of $ 3's$ that exceeds the tower of $ 1989$ $ 2's.$ In other words, find the smallest value of $ n$ such that $ T_n(3) > T_{1989}(2).$ Justify your answer.

In a country there are several cities; some of these cities are connected by airlines, so that an airline connects exactly two cities in each case and both flight directions are possible. Each airline belongs to one of $k$ flight companies; two airlines of the same flight company have always a common final point. Show that one can partition all cities in $k+2$ groups in such a way that two cities from exactly the same group are never connected by an airline with each other.

Let $f_1(x)$ be a polynomial of degree $2$ with the leading coefficient positive and $f_{n+1}(x) =f_1(f_n(x))$ for $n\ge 1.$ Prove that if the equation $f_2(x)=0$ has four different non-positive real roots, then for arbitrary $n$ then $f_n(x)$ has $2^n$ different real roots.

Let $ A_1,A_2,\dots,A_n$ be idempotent matrices with real entries. Prove that: \[ \mbox{N}(A_1)\plus{}\mbox{N}(A_2)\plus{}\dots\plus{}\mbox{N}(A_n)\geq \mbox{rank}(I\minus{}A_1A_2\dots A_n)\] $ \mbox{N}(A)$ is $ \mbox{dim}(\mbox{ker(A)})$

Let $ A$ be the subset of the set of positive integers, having the following $ 2$ properties: 1) If $ a$ belong to $ A$,than all of the divisors of $ a$ also belong to $ A$; 2) If $ a$ and $ b$, $ 1 < a < b$, belong to $ A$, than $ 1 \plus{} ab$ is also in $ A$; Prove that if $ A$ contains at least $ 3$ positive integers, than $ A$ contains all positive integers.

Suppose that $a_0=1$ and that $a_{n+1}=a_n+e^{-a_n}$ for $n=0,1,2,\dots.$ Does $a_n-\log n$ have a finite limit as $n\to\infty?$ (Here $\log n=\log_en=\ln n.$)

The set of positive integers is partitioned into finitely many subsets. Show that some subset $S$ has the following property: for every positive integer $n$, $S$ contains infinitely many multiples of $n$.

Let $\phi(n)$ be the number of positive integers less than $n$ that are relatively prime to $n$, where $n$ is a positive integer. Find all pairs of positive integers $(m,n)$ such that \[2^n + (n-\phi(n)-1)! = n^m+1.\]

Given an integer $n\ge 2$. Prove that there only exist a finite number of n-tuples of positive integers $(a_1,a_2,\ldots,a_n)$ which simultaneously satisfy the following three conditions: [list] [*] $a_1>a_2>\ldots>a_n$; [*] $\gcd (a_1,a_2,\ldots,a_n)=1$; [*] $a_1=\sum_{i=1}^{n}\gcd (a_i,a_{i+1})$,where $a_{n+1}=a_1$.[/list]

The sequence $\{x_{n}\}$ is defined by \[x_{0}\in [0, 1], \; x_{n+1}=1-\vert 1-2 x_{n}\vert.\] Prove that the sequence is periodic if and only if $x_{0}$ is irrational.

In each cell of an $n\times n$ board is a lightbulb. Initially, all of the lights are off. Each move consists of changing the state of all of the lights in a row or of all of the lights in a column (off lights are turned on and on lights are turned off). Show that if after a certain number of moves, at least one light is on, then at this moment at least $n$ lights are on.

Define a sequence by $a_0=1$, together with the rules $a_{2n+1}=a_n$ and $a_{2n+2}=a_n+a_{n+1}$ for each integer $n\ge0$. Prove that every positive rational number appears in the set $ \left\{ \tfrac {a_{n-1}}{a_n}: n \ge 1 \right\} = \left\{ \tfrac {1}{1}, \tfrac {1}{2}, \tfrac {2}{1}, \tfrac {1}{3}, \tfrac {3}{2}, \cdots \right\} $.

Let $S$ be a planar region. A $\emph{domino-tiling}$ of $S$ is a partition of $S$ into $1\times2$ rectangles. (For example, a $2\times3$ rectangle has exactly $3$ domino-tilings, as shown below.) [asy] import graph; size(7cm); pen dps = linewidth(0.7); defaultpen(dps); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle, linewidth(2)); draw((4,0)--(4,2)--(7,2)--(7,0)--cycle, linewidth(2)); draw((8,0)--(8,2)--(11,2)--(11,0)--cycle, linewidth(2)); draw((1,0)--(1,2)); draw((2,1)--(3,1)); draw((0,1)--(2,1), linewidth(2)); draw((2,0)--(2,2), linewidth(2)); draw((4,1)--(7,1)); draw((5,0)--(5,2), linewidth(2)); draw((6,0)--(6,2), linewidth(2)); draw((8,1)--(9,1)); draw((10,0)--(10,2)); draw((9,0)--(9,2), linewidth(2)); draw((9,1)--(11,1), linewidth(2)); [/asy] The rectangles in the partition of $S$ are called $\emph{dominoes}$. (a) For any given positive integer $n$, find a region $S_n$ with area at most $2n$ that has exactly $n$ domino-tilings. (b) Find a region $T$ with area less than $50000$ that has exactly $100002013$ domino-tilings.

Let $ \left(a_n \right)_{n \in \mathbb{N}}$ defined by $ a_1 \equal{} 1,$ and $ a_{n \plus{} 1} \equal{} a^4_n \minus{} a^3_n \plus{} 2a^2_n \plus{} 1$ for $ n \geq 1.$ Show that there is an infinite number of primes $ p$ such that none of the $ a_n$ is divisible by $ p.$