Search

Dokaži da ne postoji beskonačni niz prostih brojeva $p_0, p_1, p_2, \ldots$ takav da za svaki prirodni broj $k$ vrijedi

$$p_k = 2p_{k-1} + 1 \quad \text{ili} \quad p_k = 2p_{k-1} - 1.$$

Neka su $a$ i $b$ relativno prosti prirodni brojevi različiti od $1$. Definiran je niz $$x_1 = a, \qquad x_2 = b, \qquad x_n = \frac{x_{n-1}^2 + x_{n-2}^2}{x_{n-1} + x_{n-2}} \quad \text{za } n \geq 3.$$

Dokaži da niti jedan član $x_n$ ovog niza, osim prva dva, nije prirodni broj.

Za prirodni broj $d$ definiran je niz $$a_0 = 1, \qquad a_{n+1} = \begin{cases} \dfrac{a_n}{2}, & \text{ako je } a_n \text{ paran}, \\ a_n + d, & \text{inače}. \end{cases}$$

Za koje vrijednosti broja $d$ postoji prirodni broj $n$ za koji je $a_n = 1$?

Odredi sve nizove $a: \mathbb{N} \to \mathbb{N}$ takve da za sve $n \in \mathbb{N}$ vrijedi: $$a_n + a_{n+1} = a_{n+2}a_{n+3} - 200.$$

Zadan je niz realnih brojeva: $$x_0 = 1,$$ $$x_1 = 1,$$ $$x_n = \sqrt{\frac{n}{2} + x_{n-1}x_{n-2}}, \quad \text{za } n \geqslant 2.$$

Postoji li realni broj $A$ takav da je $An < x_n < An + 1$ za svaki $n \in \mathbb{N}$?

Dokaži da za svaki $x \in \left[\frac{1}{111}, \frac{110}{111}\right]$ možemo odabrati brojeve $a_i \in \{-1, 1\}$, $i = 1, 2, \ldots, 101$ takve da je $$\left|x_{101} - x\right| \leqslant \frac{1}{402},$$ pri čemu je $$x_0 = 1, \quad x_k = (x_{k-1} + 1)^{a_k}, \quad \text{za} \quad k = 1, 2, \ldots, 101.$$

Dokaži da niz $$a_k = \left\lfloor \frac{2^k}{k} \right\rfloor, \quad k \in \mathbb{N}$$ sadrži beskonačno mnogo neparnih brojeva.

($\lfloor x \rfloor$ označava najveći cijeli broj koji nije veći od $x$.)

Niz $a_1, a_2, \ldots$ pozitivnih realnih brojeva zadovoljava uvjet

$$a_{k+1} \geq \frac{ka_k}{a_k^2 + k - 1}$$

za svaki prirodni broj $k$. Dokaži da je

$$a_1 + a_2 + \cdots + a_n \geq n$$

za svaki $n \geq 2$.

Kriptogramom prirodnog broja $n$ zovemo uređenu $n$-torku $a = (a_1, a_2, \ldots, a_n)$ brojeva iz $\mathbb{N}_0$ takvu da vrijedi $$a_1 + 2a_2 + \cdots + na_n = n.$$

Neka je $\mathcal{K}_n$ skup svih kriptograma broja $n$. Za $a \in \mathcal{K}_n$ označimo sa $J(a)$ broj pojavljivanja broja $1$ u kriptogramu $a$. Dokaži da vrijedi $$\sum_{a \in \mathcal{K}_n} J(a) = \sum_{a \in \mathcal{K}_{n+1}} a_2.$$

Neka je $n \geq 3$ prirodni broj i neka je $(a_1, a_2, \ldots, a_n)$ strogo rastući niz realnih brojeva takav da je $\sum_{k=1}^n a_k = 2$. Neka je $M$ neki podskup skupa $\{1, 2, \ldots, n\}$ za koji je vrijednost izraza $\left|1 - \sum_{k \in M} a_k\right|$ najmanja moguća.

Dokaži da postoji strogo rastući niz realnih brojeva $(b_1, b_2, \ldots, b_n)$ takav da je $\sum_{k=1}^n b_k = 2$, za koji vrijedi $\sum_{k \in M} b_k = 1$.

Odredi sve periodične nizove $(x_n)_{n \in \mathbb{N}}$ pozitivnih realnih brojeva sa svojstvom da za sve $n \in \mathbb{N}$ vrijedi $$x_{n+2} = \frac{1}{2}\left(\frac{1}{x_{n+1}} + x_n\right).$$

Funkcija $U: \mathbb{N} \to \mathbb{N}$ definira se na sljedeći način: $$U(n) = \begin{cases} 1, & \text{za } n = 1, \\ \alpha_1^{p_1} \cdots \alpha_k^{p_k}, & \text{za } n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}, \text{gdje su } p_1, \ldots, p_k \text{ međusobno različiti prosti brojevi i } \alpha_1, \ldots, \alpha_k \in \mathbb{N}. \end{cases}$$

Za $m \in \mathbb{N}$ neka je $U^{(m)}(n) = U(U(\ldots U(n)\ldots))$, pri čemu se $U$ primjenjuje $m$ puta.

Dokaži da za svaki prirodni broj $A$ postoji prirodni broj $B$ takav da je $U^{(m)}(A) = B$ za beskonačno mnogo prirodnih brojeva $m$.

Ako je $a_1, a_2, \ldots, a_{2000}$ niz od $2000$ pozitivnih realnih brojeva, za koliko najviše indeksa $i \in \{1, 2, \ldots, 2000\}$ može vrijediti jednakost

$$a_i a_{i+3} = a_i a_{i+1} + a_{i+1} a_{i+2} + a_{i+2} a_{i+3}?$$

Smatramo da je $a_{j+2000} = a_j$ za $j \in \{1, 2, 3\}$.

Neka je $a_1, a_2, a_3, \ldots$ beskonačan niz brojeva iz skupa $\{1, 2, 3, 4, 5, 6, 7, 8\}$ takav da za svaki par prirodnih brojeva $(m, n)$ vrijedi:

uvjeti $a_n | n$ i $a_m | m$ ispunjeni su ako i samo ako je $a_{m+n} = a_m + a_n - 1$.

Odredi sve vrijednosti koje može poprimiti $a_{5555}$.

Neka je $c$ prirodan broj. Pretpostavimo da je $x_1, x_2, \ldots$ (beskonačan) strogo rastući niz prirodnih brojeva takav da za svaki prirodan broj $n$ vrijedi

$$x_n \mid n^2 + c.$$

Dokaži da postoji prirodan broj $M$ takav da je $x_n = n^2 + c$ za svaki $n \geqslant M$.

Neka je $a_1, a_2, a_3, \ldots$ niz pozitivnih realnih brojeva takav da za svaki prirodan broj $n \geqslant 2$ vrijedi

$$a_n - a_{n+2} \leqslant (a_{n-1} - a_{n+1}) \cdot \frac{a_{n+1} + a_{n+2}}{a_{n-1} + a_n}.$$

Dokaži da je $a_{100} \geqslant a_{102}$.

Neka je $n \geq 2$ prirodni broj. Za niz prirodnih brojeva $a_1 < a_2 < \ldots < a_n$, kažemo da je par $(i,j)$, $1 \leq i < j \leq n$ zlatni ako vrijedi jednakost

$$a_j^2 - a_i^2 = 2(a_i + a_{i+1} + \ldots + a_j).$$

Odredi najveći mogući broj zlatnih parova (koji se može postići u nekom nizu od $n$ prirodnih brojeva).

Niz prirodnih brojeva $(a_n)_{n \in \mathbb{N}}$ u kojem je $a_1 > 1$ zadovoljava relaciju

$$a_{n+1} = a_n + p^n \quad \text{za } n \in \mathbb{N},$$

pri čemu je $p = 2$ ako je $a_n$ potencija broja $2$, a inače je $p$ najmanji neparan prosti djelitelj broja $a_n$. Dokaži da postoji beskonačno mnogo parova prirodnih brojeva $(m,n)$ uz $m \neq n$ takvih da $a_m$ dijeli $a_n$.

Dokaži da u svakom aritmetičkom nizu prirodnih brojeva postoji beskonačno mnogo članova koji su djelitelji umnoška svih prethodnih članova.

Napomena. Za niz brojeva $(a_n)_{n \in \mathbb{N}}$ kažemo da je aritmetički ako je $a_n = \frac{1}{2}(a_{n-1} + a_{n+1})$ za svaki prirodan broj $n \geq 2$.

Consider the sequence $\{c_n\}$, where $$\begin{aligned} c_1 &= a_1 + a_2 + \cdots + a_8 \\ c_2 &= a_1^2 + a_2^2 + \cdots + a_8^2 \\ &\cdots \\ c_n &= a_1^n + a_2^n + \cdots + a_8^n \\ &\cdots \end{aligned}$$ in which $a_1, a_2, \ldots, a_8$ are real numbers not all equal to zero. Suppose that an infinite number of terms of the sequence $\{c_n\}$ are equal to zero. Find all natural numbers $n$ for which $c_n = 0$.

For every natural number $n$, evaluate the sum $$\sum_{k=0}^{\infty} \left[ \frac{n + 2^k}{2^{k+1}} \right] = \left[ \frac{n + 1}{2} \right] + \left[ \frac{n + 2}{4} \right] + \cdots + \left[ \frac{n + 2^k}{2^{k+1}} \right] + \cdots$$

(The symbol $[x]$ denotes the greatest integer not exceeding $x$.)

The real numbers $a_0, a_1, \ldots, a_n, \ldots$ satisfy the condition: $$1 = a_0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq \cdots.$$

The numbers $b_1, b_2, \ldots, b_n, \ldots$ are defined by $$b_n = \sum_{k=1}^{n} \left(1 - \frac{a_{k-1}}{a_k}\right) \frac{1}{\sqrt{a_k}}.$$

(a) Prove that $0 \leq b_n < 2$ for all $n$.

(b) Given $c$ with $0 \leq c < 2$, prove that there exist numbers $a_0, a_1, \ldots$ with the above properties such that $b_n > c$ for large enough $n$.

Let $a_1, a_2, a_3, \cdots$ be an infinite increasing sequence of positive integers. Prove that for every $p \geq 1$ there are infinitely many $a_m$ which can be written in the form

$$a_m = xa_p + ya_q$$

with $x, y$ positive integers and $q > p$.

A sequence $\{u_n\}$ is defined by $$u_0 = 2, \quad u_1 = 5/2, \quad u_{n+1} = u_n(u_{n-1}^2 - 2) - u_1 \text{ for } n = 1, 2, \cdots$$

Prove that for positive integers $n$, $$[u_n] = 2^{[2^n - (-1)^n]/3}$$ where $[x]$ denotes the greatest integer $\leq x$.

In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence.

The set of all positive integers is the union of two disjoint subsets $\{f(1), f(2), \ldots, f(n), \ldots\}$, $\{g(1), g(2), \ldots, g(n), \ldots\}$, where

$$f(1) < f(2) < \cdots < f(n) < \cdots,$$ $$g(1) < g(2) < \cdots < g(n) < \cdots,$$

and

$$g(n) = f(f(n)) + 1 \text{ for all } n \geq 1.$$

Determine $f(240)$.

Let $\{a_k\}$ $(k = 1, 2, 3, \ldots, n, \ldots)$ be a sequence of distinct positive integers. Prove that for all natural numbers $n$,

$$\sum_{k=1}^n \frac{a_k}{k^2} \geq \sum_{k=1}^n \frac{1}{k}.$$

Consider the infinite sequences $\{x_n\}$ of positive real numbers with the following properties:

$$x_0 = 1, \text{ and for all } i \geq 0, x_{i+1} \leq x_i.$$

(a) Prove that for every such sequence, there is an $n \geq 1$ such that

$$\frac{x_0^2}{x_1} + \frac{x_1^2}{x_2} + \cdots + \frac{x_{n-1}^2}{x_n} \geq 3.999.$$

(b) Find such a sequence for which

$$\frac{x_0^2}{x_1} + \frac{x_1^2}{x_2} + \cdots + \frac{x_{n-1}^2}{x_n} < 4.$$

For every real number $x_1$, construct the sequence $x_1, x_2, \ldots$ by setting $$x_{n+1} = x_n\left(x_n + \frac{1}{n}\right) \text{ for each } n \geq 1.$$ Prove that there exists exactly one value of $x_1$ for which $$0 < x_n < x_{n+1} < 1$$ for every $n$.

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 $|x_i| \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

$$|x_i - x_j||i - j|^a \geq 1$$

for every pair of distinct nonnegative integers $i, j$.

There are $n$ lamps $L_0, \ldots, L_{n-1}$ in a circle ($n > 1$), where we denote $L_{n+k} = L_k$. (A lamp at all times is either on or off.) Perform steps $s_0, s_1, \ldots$ as follows: at step $s_i$, if $L_{i-1}$ is lit, switch $L_i$ from on to off or vice versa, otherwise do nothing. Initially all lamps are on. Show that:

(a) There is a positive integer $M(n)$ such that after $M(n)$ steps all the lamps are on again;

(b) If $n = 2^k$, we can take $M(n) = n^2 - 1$;

(c) If $n = 2^k + 1$, we can take $M(n) = n^2 - n + 1$.

Find the maximum value of $x_0$ for which there exists a sequence $x_0, x_1, \ldots, x_{1995}$ of positive reals with $x_0 = x_{1995}$, such that for $i = 1, \ldots, 1995$, $$x_{i-1} + \frac{2}{x_{i-1}} = 2x_i + \frac{1}{x_i}.$$

Let $p, q, n$ be three positive integers with $p + q < n$. Let $(x_0, x_1, \ldots, x_n)$ be an $(n + 1)$-tuple of integers satisfying the following conditions:

(a) $x_0 = x_n = 0$.

(b) For each $i$ with $1 \leq i \leq n$, either $x_i - x_{i-1} = p$ or $x_i - x_{i-1} = -q$.

Show that there exist indices $i < j$ with $(i, j) \neq (0, n)$, such that $x_i = x_j$.

$k$ is a positive real. $N$ is an integer greater than 1. $N$ points are placed on a line, not all coincident. A move is carried out as follows. Pick any two points $A$ and $B$ which are not coincident. Suppose that $A$ lies to the right of $B$. Replace $B$ by another point $B'$ to the right of $A$ such that $AB' = kBA$. For what values of $k$ can we move the points arbitrarily far to the right by repeated moves?

Given $n > 2$ and reals $x_1 \leq x_2 \leq \cdots \leq x_n$, show that $(\sum_{i,j} |x_i - x_j|)^2 \leq \frac{2}{3}(n^2 - 1)\sum_{i,j}(x_i - x_j)^2$. Show that we have equality iff the sequence is an arithmetic progression.

Let $a_1, a_2, \ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1, a_2, \ldots, a_n$ leave $n$ different remainders upon division by $n$.

Prove that every integer occurs exactly once in the sequence $a_1, a_2, \ldots$.

Determine all positive integers relatively prime to all the terms of the infinite sequence $$a_n = 2^n + 3^n + 6^n - 1, \quad n \geq 1.$$

Real numbers $a_1, a_2, \ldots, a_n$ are given. For each $i$ ($1 \leq i \leq n$) define

$$d_i = \max\{a_j : 1 \leq j \leq i\} - \min\{a_j : i \leq j \leq n\}$$

and let

$$d = \max\{d_i : 1 \leq i \leq n\}.$$

(a) Prove that, for any real numbers $x_1 \leq x_2 \leq \cdots \leq x_n$,

$$\max\{|x_i - a_i| : 1 \leq i \leq n\} \geq \frac{d}{2}. \quad (*)$$

(b) Show that there are real numbers $x_1 \leq x_2 \leq \cdots \leq x_n$ such that equality holds in $(*)$.

Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number. Let $2n$ lamps labelled 1, 2, ..., $2n$ be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).

Let $N$ be the number of such sequences consisting of $k$ steps and resulting in the state where lamps 1 through $n$ are all on, and lamps $n + 1$ through $2n$ are all off.

Let $M$ be the number of such sequences consisting of $k$ steps, resulting in the state where lamps 1 through $n$ are all on, and lamps $n + 1$ through $2n$ are all off, but where none of the lamps $n + 1$ through $2n$ is ever switched on.

Determine the ratio $N/M$.

Suppose that $s_1, s_2, s_3, \ldots$ is a strictly increasing sequence of positive integers such that the subsequences

$$s_{s_1}, s_{s_2}, s_{s_3}, \ldots \quad \text{and} \quad s_{s_1 + 1}, s_{s_2 + 1}, s_{s_3 + 1}, \ldots$$

are both arithmetic progressions. Prove that the sequence $s_1, s_2, s_3, \ldots$ is itself an arithmetic progression.

Let $a_1, a_2, a_3, \ldots$ be a sequence of positive real numbers. Suppose that for some positive integer $s$, we have $$a _ {n} = \max \left\{a _ {k} + a _ {n - k} \mid 1 \leq k \leq n - 1 \right\}$$ for all $n > s$. Prove that there exist positive integers $\ell$ and $N$, with $\ell \leq s$ and such that $a_{n} = a_{\ell} + a_{n - \ell}$ for all $n \geq N$.

Let $a_0 < a_1 < a_2 < \cdots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n \geq 1$ such that $$a_n < \frac{a_0 + a_1 + \cdots + a_n}{n} \leq a_{n+1}.$$

The sequence $a_1, a_2, \ldots$ of integers satisfies the following conditions:

(i) $1 \leqslant a_{j} \leqslant 2015$ for all $j \geqslant 1$;

(ii) $k + a_{k} \neq \ell + a_{\ell}$ for all $1 \leqslant k < \ell$.

Prove that there exist two positive integers $b$ and $N$ such that $$\left| \sum_{j = m + 1}^{n} (a_{j} - b) \right| \leqslant 1007^{2}$$ for all integers $m$ and $n$ satisfying $n > m \geqslant N$.

For each integer $a_0 > 1$, define the sequence $a_0, a_1, a_2, \ldots$ by:

$$a_{n+1} = \begin{cases} \sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\ a_n + 3 & \text{otherwise,} \end{cases} \quad \text{for each } n \geqslant 0.$$

Determine all values of $a_0$ for which there is a number $A$ such that $a_n = A$ for infinitely many values of $n$.

Find all integers $n \geq 3$ for which there exist real numbers $a_1, a_2, \ldots, a_{n+2}$, such that $a_{n+1} = a_1$ and $a_{n+2} = a_2$, and $$a_i a_{i+1} + 1 = a_{i+2}$$ for $i = 1, 2, \ldots, n$.

Let $a_1, a_2, \ldots$ be an infinite sequence of positive integers. Suppose that there is an integer $N > 1$ such that, for each $n \geq N$, the number $$\frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}$$ is an integer. Prove that there is a positive integer $M$ such that $a_m = a_{m+1}$ for all $m \geq M$.

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k > 0$ coins showing $H$, then he turns over the $k$th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n = 3$ the process starting with the configuration $THT$ would be $THT \to HHT \to HTT \to TTT$, which stops after three operations.

(a) Show that, for each initial configuration, Harry stops after a finite number of operations.

(b) For each initial configuration $C$, let $L(C)$ be the number of operations before Harry stops. For example, $L(THT) = 3$ and $L(TTT) = 0$. Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$.

The Bank of Oslo issues two types of coin: aluminium (denoted $A$) and bronze (denoted $B$). Marianne has $n$ aluminium coins and $n$ bronze coins, arranged in a row in some arbitrary initial order. A chain is any subsequence of consecutive coins of the same type. Given a fixed positive integer $k \leq 2n$, Marianne repeatedly performs the following operation: she identifies the longest chain containing the $k^{\text{th}}$ coin from the left, and moves all coins in that chain to the left end of the row. For example, if $n = 4$ and $k = 4$, the process starting from the ordering $AABBBABA$ would be

$$AAB\underline{B}BABA \rightarrow BBB\underline{A}AABA \rightarrow AAA\underline{B}BBBA \rightarrow BBB\underline{B}AAAA \rightarrow BBB\underline{B}AAAA \rightarrow \cdots.$$

Find all pairs $(n,k)$ with $1 \leq k \leq 2n$ such that for every initial ordering, at some moment during the process, the leftmost $n$ coins will all be of the same type.

For each integer $k \geqslant 2$, determine all infinite sequences of positive integers $a_1, a_2, \ldots$ for which there exists a polynomial $P$ of the form $P(x) = x^k + c_{k-1}x^{k-1} + \cdots + c_1x + c_0$, where $c_0, c_1, \ldots, c_{k-1}$ are non-negative integers, such that

$$P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k}$$

for every integer $n \geqslant 1$.

Let $a_1, a_2, a_3, \ldots$ be an infinite sequence of positive integers, and let $N$ be a positive integer. Suppose that, for each $n > N$, $a_n$ is equal to the number of times $a_{n-1}$ appears in the list $a_1, a_2, \ldots, a_{n-1}$.

Prove that at least one of the sequences $a_1, a_3, a_5, \ldots$ and $a_2, a_4, a_6, \ldots$ is eventually periodic.

(An infinite sequence $b_1, b_2, b_3, \ldots$ is eventually periodic if there exist positive integers $p$ and $M$ such that $b_{m+p} = b_m$ for all $m \geq M$.)