Found problems: 766
For an integer $a \ge 2$, denote by $\delta_(a) $ the second largest divisor of $a$. Let $(a_n)_{n\ge 1}$ be a sequence
of integers such that $a_1 \ge 2$ and $$a_{n+1} = a_n + \delta_(a_n)$$
for all $n \ge 1$. Prove that there exists a positive integer $k$ such that $a_k$ is divisible by $3^{2022}$.
The Fermat-numbers are defined by $F_n = 2^{2^n}+1$ for $n\in N$.
(a) Prove that $F_n = F_{n-1}F_{n-2}....F_1F_0 +2$ for $n > 0$.
(b) Prove that any two different Fermat numbers are coprime
A mouse is playing a game of mouse hopscotch. In mouse hopscotch there is a straight line of $11$ squares, and starting on the first square the mouse must reach the last square by jumping forward $1$, $2$, or $3$ squares at a time (so in particular the mouse’s first jump can be to the second, third, or fourth square). The mouse cannot jump past the last square. Compute the number of ways there are to complete mouse hopscotch.
We define the [i]Fibonacci sequence[/i] $\{F_n\}_{n\ge0}$ by $F_0=0$, $F_1=1$, and for $n\ge2$, $F_n=F_{n-1}+F_{n-2}$; we define the [i]Stirling number of the second kind[/i] $S(n,k)$ as the number of ways to partition a set of $n\ge1$ distinguishable elements into $k\ge1$ indistinguishable nonempty subsets.
For every positive integer $n$, let $t_n = \sum_{k=1}^{n} S(n,k) F_k$. Let $p\ge7$ be a prime. Prove that \[ t_{n+p^{2p}-1} \equiv t_n \pmod{p} \] for all $n\ge1$.
[i]Proposed by Victor Wang[/i]
A biologist watches a chameleon. The chameleon catches flies and rests after each catch. The biologist notices that:
[list=1][*]the first fly is caught after a resting period of one minute;
[*]the resting period before catching the $2m^\text{th}$ fly is the same as the resting period before catching the $m^\text{th}$ fly and one minute shorter than the resting period before catching the $(2m+1)^\text{th}$ fly;
[*]when the chameleon stops resting, he catches a fly instantly.[/list]
[list=a][*]How many flies were caught by the chameleon before his first resting period of $9$ minutes in a row?
[*]After how many minutes will the chameleon catch his $98^\text{th}$ fly?
[*]How many flies were caught by the chameleon after 1999 minutes have passed?[/list]
For any positive integer $ x$ define $ g(x)$ as greatest odd divisor of $ x,$ and
\[ f(x) \equal{} \begin{cases} \frac {x}{2} \plus{} \frac {x}{g(x)} & \text{if \ \(x\) is even}, \\
2^{\frac {x \plus{} 1}{2}} & \text{if \ \(x\) is odd}. \end{cases}
\]
Construct the sequence $ x_1 \equal{} 1, x_{n \plus{} 1} \equal{} f(x_n).$ Show that the number 1992 appears in this sequence, determine the least $ n$ such that $ x_n \equal{} 1992,$ and determine whether $ n$ is unique.
A sequence $(x_n)_{n= 1}^{\infty}$ satisfies $x_1 = 1$ and for each $n > 1, x_n = \pm (n-1)x_{n-1} \pm (n-2)x_{n-2} \pm ... \pm 2x_2 \pm x_1$. Prove that the signs ” $\pm$” can be chosen so that $x_n \ne 12$ holds only for finitely many $n$.
From the set of all permutations $f$ of $\{1, 2, ... , n\}$ that satisfy the condition:
$f(i) \geq i-1$ $i=1,...,n$
one is chosen uniformly at random. Let $p_n$ be the probability that the chosen permutation $f$ satisfies
$f(i) \leq i+1$ $i=1,...,n$
Find all natural numbers $n$ such that $p_n > \frac{1}{3}$.
For any positive integer $ x$ define $ g(x)$ as greatest odd divisor of $ x,$ and
\[ f(x) \equal{} \begin{cases} \frac {x}{2} \plus{} \frac {x}{g(x)} & \text{if \ \(x\) is even}, \\
2^{\frac {x \plus{} 1}{2}} & \text{if \ \(x\) is odd}. \end{cases}
\]
Construct the sequence $ x_1 \equal{} 1, x_{n \plus{} 1} \equal{} f(x_n).$ Show that the number 1992 appears in this sequence, determine the least $ n$ such that $ x_n \equal{} 1992,$ and determine whether $ n$ is unique.
Three hexagons of increasing size are shown below. Suppose the dot pattern continues so that each successive hexagon contains one more band of dots. How many dots are in the next hexagon?
[asy]
// diagram by SirCalcsALot
size(250);
real side1 = 1.5;
real side2 = 4.0;
real side3 = 6.5;
real pos = 2.5;
pair s1 = (-10,-2.19);
pair s2 = (15,2.19);
pen grey1 = rgb(100/256, 100/256, 100/256);
pen grey2 = rgb(183/256, 183/256, 183/256);
fill(circle(origin + s1, 1), grey1);
for (int i = 0; i < 6; ++i) {
draw(side1*dir(60*i)+s1--side1*dir(60*i-60)+s1,linewidth(1.25));
}
fill(circle(origin, 1), grey1);
for (int i = 0; i < 6; ++i) {
fill(circle(pos*dir(60*i),1), grey2);
draw(side2*dir(60*i)--side2*dir(60*i-60),linewidth(1.25));
}
fill(circle(origin+s2, 1), grey1);
for (int i = 0; i < 6; ++i) {
fill(circle(pos*dir(60*i)+s2,1), grey2);
fill(circle(2*pos*dir(60*i)+s2,1), grey1);
fill(circle(sqrt(3)*pos*dir(60*i+30)+s2,1), grey1);
draw(side3*dir(60*i)+s2--side3*dir(60*i-60)+s2,linewidth(1.25));
}
[/asy]
$\textbf{(A)}\ 35 \qquad \textbf{(B)}\ 37 \qquad \textbf{(C)}\ 39 \qquad \textbf{(D)}\ 43 \qquad \textbf{(E)}\ 49$
Given a $2 \times 2$ tile and seven dominoes ( $2 \times 1$ tile), find the number of ways of tiling (that is, cover without leaving gaps and without overlapping of any two tiles) a $2 \times 7$ rectangle using some of these tiles.
A very well known family of mathematicians has three children called [i]Antonia, Bernhard[/i] and [i]Christian[/i]. Each evening one of the children has to do the dishes. One day, their dad decided to construct of plan that says which child has to do the dishes at which day for the following $55$ days.
Let $x$ be the number of possible such plans in which Antonia has to do the dishes on three consecutive days at least once. Furthermore, let $y$ be the number of such plans in which there are three consecutive days in which Antonia does the dishes on the first, Bernhard on the second and Christian on the third day.
Determine, whether $x$ and $y$ are different and if so, then decide which of those is larger.
Let $u_1$, $u_2$, $u_3$, $\dots$ be a sequence of integers satisfying the recurrence relation $u_{n + 2} = u_{n + 1}^2 - u_n$. Suppose $u_1 = 39$ and $u_2 = 45$. Prove that 1986 divides infinitely many terms of the sequence.
Given a natural number $a_0$, we construct the sequence $\{a_n\}$ as follows $a_{n+1} = a^2_n-5$ if $a_n$ is odd, and $\frac{a_n}{2}$ if $a_n$ is even. Prove that for any odd $a_0 > 5$ in the sequence $\{a_n\}$ arbitrarily large numbers will occur.
Let $x_{n + 1} = 4x_n - x_{n - 1}$, $x_0 = 0$, $x_1 = 1$, and $y_{n + 1} = 4y_n - y_{n - 1}$, $y_0 = 1$, $y_1 = 2$. Show that for all $n \ge 0$ that $y_n^2 = 3x_n^2 + 1$.
The sequence $\{x_{n}\}_{n \ge 1}$ is defined by \[x_{1}=x_{2}=1, \; x_{n+2}= 14x_{n+1}-x_{n}-4.\] Prove that $x_{n}$ is always a perfect square.
Let $a_0, a_1, \ldots, a_n, a_{n+1}$ be a sequence of real numbers satisfying the following conditions:
\[a_0 = a_{n+1 }= 0,\]\[ |a_{k-1} - 2a_k + a_{k+1}| \leq 1 \quad (k = 1, 2,\ldots , n).\]
Prove that $|a_k| \leq \frac{k(n+1-k)}{2} \quad (k = 0, 1,\ldots ,n + 1).$
Prove that $(2m)!(2n)!$ is a multiple of $m!n!(m+n)!$ for any non-negative integers $m$ and $n$.
Let $m,n\geq 2$ be integers. Let $f(x_1,\dots, x_n)$ be a polynomial with real coefficients such that $$f(x_1,\dots, x_n)=\left\lfloor \frac{x_1+\dots + x_n}{m} \right\rfloor\text{ for every } x_1,\dots, x_n\in \{0,1,\dots, m-1\}.$$ Prove that the total degree of $f$ is at least $n$.
Consider the set $F$ of all polynomials whose coefficients are in the set of $\{0,1\}$. Let $q(x) = x^3 + x +1$. The number of polynomials $p(x)$ in $F$ of degree $14$ such that the product $p(x)q(x)$ is also in $F$ is:
The sequence $a_i$ is defined as $a_1 = 2, a_2 = 3$, and
$a_{n+1} = 2a_{n-1}$ or $a_{n+1} = 3a_n - 2a_{n-1}$ for all integers $n \ge 2$.
Prove that no term in $a_i$ is in the range $[1612, 2012]$.
Determine all real numbers A such that every sequence of non-zero real numbers $x_1, x_2, \ldots$ satisfying
\[ x_{n+1}=A-\frac{1}{x_n} \]
for every integer $n \ge 1$, has only finitely many negative terms.
Let $n \in \mathbb N$ and $A_n$ set of all permutations $(a_1, \ldots, a_n)$ of the set $\{1, 2, \ldots , n\}$ for which
\[k|2(a_1 + \cdots+ a_k), \text{ for all } 1 \leq k \leq n.\]
Find the number of elements of the set $A_n$.
[i]Proposed by Vidan Govedarica, Serbia[/i]
Consider 2n+1 coins lying in a circle. At the beginning, all the coins are heads up. Moving clockwise, 2n+1 flips are performed: one coin is flipped, the next coin is skipped, the next coin is flipped, the next two coins are skipped, the next coin is flipped,the next three coins are skipped and so on, until finally 2n coins are skipped and the next coin is flipped.Prove that at the end of this procedure,exactly one coin is heads down.
Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that \[ f(m+n)f(m-n) = f(m^2) \] for $m,n \in \mathbb{N}$.