Školjka

%V0 There are $2^n$ words of length $n$ over the alphabet $\{0, 1\}$. Prove that the following algorithm generates the sequence $w_0, w_1, \ldots, w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit. (1) $w_0 = 00 \ldots 0$ ($n$ zeros). (2) Suppose $w_{m-1} = a_1a_2 \ldots a_n,\quad a_i \in \{0, 1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j = 1 + e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1 - a_j$. The obtained word is $w_m$.

%V0 An eccentric mathematician has a ladder with $n$ rungs that he always ascends and descends in the following way: When he ascends, each step he takes covers $a$ rungs of the ladder, and when he descends, each step he takes covers $b$ rungs of the ladder, where $a$ and $b$ are fixed positive integers. By a sequence of ascending and descending steps he can climb from ground level to the top rung of the ladder and come back down to ground level again. Find, with proof, the minimum value of $n,$ expressed in terms of $a$ and $b.$

%V0 Suppose $\,G\,$ is a connected graph with $\,k\,$ edges. Prove that it is possible to label the edges $1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1. Graph-DefinitionA graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $\,u,v\,$ belongs to at most one edge. The graph $G$ is connected if for each pair of distinct vertices $\,x,y\,$ there is some sequence of vertices $\,x = v_{0},v_{1},v_{2},\cdots ,v_{m} = y\,$ such that each pair $\,v_{i},v_{i + 1}\;(0\leq i < m)\,$ is joined by an edge of $\,G$.

%V0 An infinite sequence $\,x_{0},x_{1},x_{2},\ldots \,$ of real numbers is said to be bounded if there is a constant $\,C\,$ such that $\, \vert x_{i} \vert \leq C\,$ for every $\,i\geq 0$. Given any real number $\,a > 1,\,$ construct a bounded infinite sequence $x_{0},x_{1},x_{2},\ldots \,$ such that $$\vert x_{i} - x_{j} \vert \vert i - j \vert^{a}\geq 1$$ for every pair of distinct nonnegative integers $i, j$.

%V0 For any positive integer $x$ define $g(x)$ as greatest odd divisor of $x,$ and $$f(x) =\begin{cases}\frac{x}{2}+\frac{x}{g(x)}&\text{if\ \(x\) is even},\\ 2^{\frac{x+1}{2}}&\text{if\ \(x\) is odd}.\end{cases}$$ Construct the sequence $x_1 = 1, x_{n + 1} = f(x_n).$ Show that the number 1992 appears in this sequence, determine the least $n$ such that $x_n = 1992,$ and determine whether $n$ is unique.

%V0 Let $R_1,R_2, \ldots$ be the family of finite sequences of positive integers defined by the following rules: $R_1 = (1),$ and if $R_{n - 1} = (x_1, \ldots, x_s),$ then $$R_n = (1, 2, \ldots, x_1, 1, 2, \ldots, x_2, \ldots, 1, 2, \ldots, x_s, n).$$ For example, $R_2 = (1, 2),$ $R_3 = (1, 1, 2, 3),$ $R_4 = (1, 1, 1, 2, 1, 2, 3, 4).$ Prove that if $n > 1,$ then the $k$th term from the left in $R_n$ is equal to 1 if and only if the $k$th term from the right in $R_n$ is different from 1.