Found problems: 1782
At a turnament between $n$ persons, everyone playes exactly one time against everyone else, and at one game there is everytime a winner and a looser.
Prove that one can arrange the participants in a chain$P_1 \to P_2 \to ... \to P_n$ such that the $i$-th person has won against the $(i+1)$-th person.
For all natural $n$, an $n$-staircase is a figure consisting of unit squares, with one square in the first row, two squares in the second row, and so on, up to $n$ squares in the $n^{th}$ row, such that all the left-most squares in each row are aligned vertically.
Let $f(n)$ denote the minimum number of square tiles requires to tile the $n$-staircase, where the side lengths of the square tiles can be any natural number. e.g. $f(2)=3$ and $f(4)=7$.
(a) Find all $n$ such that $f(n)=n$.
(b) Find all $n$ such that $f(n) = n+1$.
Let $ (a_{n})_{n\ge 1}$ be a sequence of positive integers satisfying $ (a_{m},a_{n}) = a_{(m,n)}$ (for all $ m,n\in N^ +$). Prove that for any $ n\in N^ + ,\prod_{d|n}{a_{d}^{\mu (\frac {n}{d})}}$ is an integer. where $ d|n$ denotes $ d$ take all positive divisors of $ n.$ Function $ \mu (n)$ is defined as follows: if $ n$ can be divided by square of certain prime number, then $ \mu (1) = 1;\mu (n) = 0$; if $ n$ can be expressed as product of $ k$ different prime numbers, then $ \mu (n) = ( - 1)^k.$
Mr. Fat and Ms. Taf play a game. Mr. Fat chooses a sequence of positive integers $ k_1, k_2, \ldots , k_n$. Ms. Taf must guess this sequence of integers. She is allowed to give Mr. Fat a red card and a blue card, each with an integer written on it. Mr. Fat replaces the number on the red card with $ k_1$ times the number on the red card plus the number on the blue card, and replaces the number on the blue card with the number originally on the red card. He repeats this process with number $ k_2$. (That is, he replaces the number on the red card with $ k_2$ times the number now on the red card plus the number now on the blue card, and replaces the number on the blue card with the number that was just placed on the red card.) He then repeats this process with each of the numbers $ k_3, \ldots k_n$, in this order. After has has gone through the sequence of integers, Mr. Fat then gives the cards back to Ms. Taf. How many times must Ms. Taf submit the red and blue cards in order to be able to determine the sequence of integers $ k_1, k_2, \ldots k_n$?
Let $n$ be a positive integer and let $a_1, a_2, \ldots, a_n$ be positive reals. Show that $$\sum_{i=1}^{n} \frac{1}{2^i}(\frac{2}{1+a_i})^{2^i} \geq \frac{2}{1+a_1a_2\ldots a_n}-\frac{1}{2^n}.$$
Given a finite number of boys and girls, a [i]sociable set of boys[/i] is a set of boys such that every girl knows at least one boy in that set; and a [i]sociable set of girls[/i] is a set of girls such that every boy knows at least one girl in that set. Prove that the number of sociable sets of boys and the number of sociable sets of girls have the same parity. (Acquaintance is assumed to be mutual.)
[i](Poland) Marek Cygan[/i]
Let $A$ be a set of positive integers such that
a) if $a\in A$, the all the positive divisors of $a$ are also in $A$;
b) if $a,b\in A$, with $1<a<b$, then $1+ab \in A$.
Prove that if $A$ has at least 3 elements, then $A$ is the set of all positive integers.
The sequence $ (a_n)$ satisfies $ a_1 \equal{} 1$ and $ \displaystyle 5^{(a_{n\plus{}1}\minus{}a_n)} \minus{} 1 \equal{} \frac{1}{n\plus{}\frac{2}{3}}$ for $ n \geq 1$. Let $ k$ be the least integer greater than $ 1$ for which $ a_k$ is an integer. Find $ k$.
Prove that: \[ \frac{1989}{2}\minus{}\frac{1988}{3}\plus{}\frac{1987}{4}\minus{}\cdots\minus{}\frac{2}{1989}\plus{}\frac{1}{1990}\equal{}\frac{1}{996}\plus{}\frac{3}{997}\plus{}\frac{5}{998}\plus{}\cdots\plus{}\frac{1989}{1990}\]
Let be a number $ n\ge 2, $ a binary funcion $ b:\mathbb{Z}\rightarrow\mathbb{Z}_2, $ and $ \frac{n^3+5n}{6} $ consecutive integers. Show that among these consecutive integers there are $ n $ of them, namely, $ b_1,b_2,\ldots ,b_n, $ that have the properties:
$ \text{(i)} b\left( b_1\right) =b\left( b_2\right) =\cdots =b\left( b_n\right) $
$ \text{(ii)} 1\le b_2-b_1\le b_3-b_2\le \cdots\le b_n-b_{n-1} $
Prove that for any $ n\in \mathbb N$ the number $ 1\plus{}\dfrac{1}{3}\plus{}\dfrac{1}{5}\plus{}\ldots\plus{}\dfrac{1}{2n\plus{}1}$ is not an integer.
Prove that every positive integer $n$, except a finite number of them, can be represented as a sum of $2004$ positive integers: $n=a_1+a_2+\cdots +a_{2004}$, where $1\le a_1<a_2<\cdots <a_{2004}$, and $a_i \mid a_{i+1}$ for all $1\le i\le 2003$.
[i]Chen Yonggao[/i]
Given the sequence $\{y_n\}_{n=1}^{\infty}$ defined by $y_1=y_2=1$ and
\[y_{n+2} = (4k-5)y_{n+1}-y_n+4-2k, \qquad n\ge1\]
find all integers $k$ such that every term of the sequence is a perfect square.
Let $N$ be a positive integer. Define a sequence $a_0,a_1,\ldots$ by $a_0=0$, $a_1=1$, and $a_{n+1}+a_{n-1}=a_n(2-1/N)$ for $n\ge1$. Prove that $a_n<\sqrt{N+1}$ for all $n$.
[i]Evan O'Dorney.[/i]
Let $S$ be a string of $99$ characters, $66$ of which are $A$ and $33$ are $B$. We call $S$ [i]good[/i] if, for each $n$ such that $1\le n \le 99$, the sub-string made from the first $n$ characters of $S$ has an odd number of distinct permutations. How many good strings are there? Which strings are good?
Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all $m,n\in\mathbb{N}$,
\[(2^m+1)f(n)f(2^mn)=2^mf(n)^2+f(2^mn)^2+(2^m-1)^2n. \]
We are given the finite sets $ X$, $ A_1$, $ A_2$, $ \dots$, $ A_{n \minus{} 1}$ and the functions $ f_i: \ X\rightarrow A_i$. A vector $ (x_1,x_2,\dots,x_n)\in X^n$ is called [i]nice[/i], if $ f_i(x_i) \equal{} f_i(x_{i \plus{} 1})$, for each $ i \equal{} 1,2,\dots,n \minus{} 1$. Prove that the number of nice vectors is at least
\[ \frac {|X|^n}{\prod\limits_{i \equal{} 1}^{n \minus{} 1} |A_i|}.
\]
$n$ pairs are formed from $n$ girls and $n$ boys at random.
What is the probability of having at least one pair of girls? For which $n$ the probability is over $0,9?$
The numbers $a_1,a_2$ and $a_3$ are distinct positive integers, such that
(i) $a_1$ is a divisor of $a_2+a_3+a_2a_3$;
(ii) $a_2$ is a divisor of $a_3+a_1+a_3a_1$;
(iii) $a_3$ is a divisor of $a_1+a_2+a_1a_2$.
Prove that $a_1,a_2$ and $a_3$ cannot all be prime.
Let $a_1,a_2,\dots,a_n$ be positive real numbers whose product is $1$. Show that the sum \[\textstyle\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\frac{a_3}{(1+a_1)(1+a_2)(1+a_3)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots(1+a_n)}\] is greater than or equal to $\frac{2^n-1}{2^n}$.
Determine all injective functions defined on the set of positive integers into itself satisfying the following condition: If $S$ is a finite set of positive integers such that $\sum\limits_{s\in S}\frac{1}{s}$ is an integer, then $\sum\limits_{s\in S}\frac{1}{f\left( s\right) }$ is also an integer.
We have $2p-1$ integer numbers, where $p$ is a prime number. Prove that we can choose exactly $p$ numbers (from these $2p-1$ numbers) so that their sum is divisible by $p$.
Prove that if a person a has infinitely many descendants (children, their children, etc.), then a has an infinite sequence $a_0, a_1, \ldots$ of descendants (i.e., $a = a_0$ and for all $n \geq 1, a_{n+1}$ is always a child of $a_n$). It is assumed that no-one can have infinitely many children.
[i]Variant 1[/i]. Prove that if $a$ has infinitely many ancestors, then $a$ has an infinite descending sequence of ancestors (i.e., $a_0, a_1, \ldots$ where $a = a_0$ and $a_n$ is always a child of $a_{n+1}$).
[i]Variant 2.[/i] Prove that if someone has infinitely many ancestors, then all people cannot descend from $A(dam)$ and $E(ve)$.
Determine whether there exists a function $ f: \mathbb{N}\longrightarrow \mathbb{N}$ such that
$ f(n)\equal{}f(f(n\minus{}1))\plus{}f(f(n\plus{}1))$ for all natural numbers $ n\ge 2$.
Prove that the sequence $ \{y_{n}\}_{n \ge 1}$ defined by
\[ y_{0}=1, \; y_{n+1}= \frac{1}{2}\left( 3y_{n}+\sqrt{5y_{n}^{2}-4}\right) \]
consists only of integers.