Found problems: 5802
Given the numbers $ 1,2,2^2, \ldots ,2^{n\minus{}1}$, for a specific permutation $ \sigma \equal{} x_1,x_2, \ldots, x_n$ of these numbers we define $ S_1(\sigma) \equal{} x_1$, $ S_2(\sigma)\equal{}x_1\plus{}x_2$, $ \ldots$ and $ Q(\sigma)\equal{}S_1(\sigma)S_2(\sigma)\cdot \cdot \cdot S_n(\sigma)$. Evaluate $ \sum 1/Q(\sigma)$, where the sum is taken over all possible permutations.
A positive integer $n$ is called [i]egyptian[/i] if there exists a strictly increasing sequence $0<a_1<a_2<\dots<a_k=n$ of integers with last term $n$ such that
\[\frac{1}{a_1}+\frac{1}{a_2}+\dots+\frac{1}{a_k}=1.\]
(a) Determine if $n=72$ is egyptian.
(b) Determine if $n=71$ is egyptian.
(c) Determine if $n=72^{71}$ is egyptian.
Let $A=[a_{ij}]_{n\times n}$ be a matrix with nonnegative entries such that
$$\sum_{i=1}^n\sum_{j=1}^na_{ij}=n.$$
(a) Prove that $|\det A|\le1$.
(b) If $|\det A|=1$ and $\lambda\in\mathbb C$ is an arbitrary eigenvalue of $A$, show that $|\lambda|=1$.
Let
$f(x)=\frac{ax+b}{cx+d}$
$F_n(x)=f(f(f...f(x)...))$ (with $n\ f's$)
Suppose that $f(0) \not =0$, $f(f(0)) \not = 0$, and for some $n$ we have $F_n(0)=0$,
show that $F_n(x)=x$ (for any valid x).
Let $f: \mathbb{N} \to \mathbb{N}$ be a function that satisfies:
\[
f(1) = 2008,
\]
\[
f(4n^2) = 4f(n^2),
\]
\[
f(4n^2 + 2) = 4f(n^2) + 3,
\]
\[
f(4n(n+1)) = 4f(n(n+1)) + 1,
\]
\[
f(4n(n+1) + 3) = 4f(n(n+1)) + 4.
\]
Determine whether there exists a natural number $m$ such that:
\[
1^2 + 2^2 + \dots + m^2 + f(1^2) + \dots + f(m^2) = 2008m + 251.
\]
Find all functions $ f: \mathbb{R}\rightarrow \mathbb{R}$ satisfying
\[ f(f(x) \plus{} y) \equal{} f(x^2 \minus{} y) \plus{} 4f(x)y
\]
for all $ x,y \in \mathbb{R}$.
Determine all positive integers $n$ for which there exists an in finite subset $A$ of the set $\mathbb{N}$ of positive integers such that for all pairwise distinct $a_1,\ldots , a_n \in A$ the numbers $a_1+\ldots +a_n$ and $a_1a_2\ldots a_n$ are coprime.
For each positive integer \( n \), list in increasing order all irreducible fractions in the interval \([0, 1]\) that have a positive denominator less than or equal to \( n \):
\[
0 = \frac{p_0}{q_0} < \frac{1}{n} = \frac{p_1}{q_1} < \cdots < \frac{1}{1} = \frac{p_{M(n)}}{q_{M(n)}}.
\]
Let \( k \) be a positive integer. We define, for each \( n \) such that \( M(n) \geq k - 1 \),
\[
f_k(n) = \min \left\{ \sum_{s=0}^{k-1} q_{j+s} : 0 \leq j \leq M(n) - k + 1 \right\}.
\]
Determine, in function of \( k \),
\[
\lim_{n \to \infty} \frac{f_k(n)}{n}.
\]
For example, if \( n = 4 \), the enumeration is
\[
\frac{0}{1} < \frac{1}{4} < \frac{1}{3} < \frac{1}{2} < \frac{2}{3} < \frac{3}{4} < \frac{1}{1},
\]
where \( p_0 = 0, p_1 = 1, p_2 = 1, p_3 = 1, p_4 = 2, p_5 = 3, p_6 = 1 \) and \( q_0 = 1, q_1 = 4, q_2 = 3, q_3 = 2, q_4 = 3, q_5 = 4, q_6 = 1 \). In this case, we have \( f_1(4) = 1, f_2(4) = 5, f_3(4) = 8, f_4(4) = 10, f_5(4) = 13, f_6(4) = 17 \), and \( f_7(4) = 18 \).
Let $ N > M > 1$ be fixed integers. There are $ N$ people playing in a chess tournament; each pair of players plays each other once, with no draws. It turns out that for each sequence of $ M \plus{} 1$ distinct players $ P_0, P_1, \ldots P_M$ such that $ P_{i \minus{} 1}$ beat $ P_i$ for each $ i \equal{} 1, \ldots, M$, player $ P_0$ also beat $ P_M$. Prove that the players can be numbered $ 1,2, \ldots, N$ in such a way that, whenever $ a \geq b \plus{} M \minus{} 1$, player $ a$ beat player $ b$.
[i]Gabriel Carroll.[/i]
Prove that in the Euclidean plane every regular polygon having an even number of sides can be dissected into lozenges. (A lozenge is a quadrilateral whose four sides are all of equal length).
Define a sequence {$a_n$}$^{\infty}_{n=1}$ by $a_1 = 4, a_2 = a_3 = (a^2 - 2)^2$ and
$a_n = a_{n-1}.a_{n-2} - 2(a_{n-1} + a_{n-2}) - a_{n-3} + 8, n \ge 4$, where $a > 2$ is a natural number.
Prove that for all $n$ the number $2 + \sqrt{a_n}$ is a perfect square.
Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$?
Given a set $S \subset N$ and a positive integer n, let $S\oplus \{n\} = \{s+n / s \in S\}$. The sequence $S_k$ of sets is defined inductively as follows: $S_1 = {1}$, $S_k=(S_{k-1} \oplus \{k\}) \cup \{2k-1\}$ for $k = 2,3,4, ...$
(a) Determine $N - \cup _{k=1}^{\infty} S_k$.
(b) Find all $n$ for which $1994 \in S_n$.
Show that there exist infinitely many pairs of positive integers $(m,n)$ such that $\binom m{n-1}=\binom{m-1}n$.
Let $p$ be a prime number such that $p\mid (2^{2019}-1) .$ The sequence $a_1,a_2,...,a_n$ satisfies the following conditions: $a_0=2, a_1=1 ,a_{n+1}=a_n+\frac{p^2-1}{4}a_{n-1}$ $(n\geq 1).$ Prove that $p\nmid (a_n+1),$ for any $n\geq 0.$
Given a positive integer $ n$, for all positive integers $ a_1, a_2, \cdots, a_n$ that satisfy $ a_1 \equal{} 1$, $ a_{i \plus{} 1} \leq a_i \plus{} 1$, find $ \displaystyle \sum_{i \equal{} 1}^{n} a_1a_2 \cdots a_i$.
there are some identical squares with sides parallel, in a plane. Among any $k+1$ of them, there are two with a point in common. Prove they can be divided into $2k-1$ sets, such that all the squares in one set aint pairwise disjoint.
Let $\mathbb{Q}_{>0}$ denote the set of all positive rational numbers. Determine all functions $f:\mathbb{Q}_{>0}\to \mathbb{Q}_{>0}$ satisfying $$f(x^2f(y)^2)=f(x)^2f(y)$$ for all $x,y\in\mathbb{Q}_{>0}$
We say that a finite set $\mathcal{S}$ of points in the plane is [i]balanced[/i] if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say that $\mathcal{S}$ is [i]centre-free[/i] if for any three different points $A$, $B$ and $C$ in $\mathcal{S}$, there is no points $P$ in $\mathcal{S}$ such that $PA=PB=PC$.
(a) Show that for all integers $n\ge 3$, there exists a balanced set consisting of $n$ points.
(b) Determine all integers $n\ge 3$ for which there exists a balanced centre-free set consisting of $n$ points.
Proposed by Netherlands
Let $\mathbb{N}$ be the set of all positive integers. $f,g:\mathbb{N} \to \mathbb{N}$ be funtions such that $f$ is onto and $g$ is one-one and $f(n)\geq g(n)$ for all positive integers $n$. Prove that $f=g$.
Let $ n$ be an integer,$ n \geq 3.$ Let $ x_1, x_2, \ldots, x_n$ be real numbers such that $ x_i < x_{i\plus{}1}$ for $ 1 \leq i \leq n \minus{} 1$. Prove that
\[ \frac{n(n\minus{}1)}{2} \sum_{i < j} x_ix_j > \left(\sum^{n\minus{}1}_{i\equal{}1} (n\minus{}i)\cdot x_i \right) \cdot \left(\sum^{n}_{j\equal{}2} (j\minus{}1) \cdot x_j \right)\]
Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$.
The edges of $K_{n}(n \geq 3)$ are colored with $n$ colors, and every color is used.
Show that there is a triangle whose sides have different colors.
Let $D_n$ be the determinant of order $n$ of which the element in the $i$-th row and the $j$-th
column is $|i-j|.$ Show that $D_n$ is equal to
$$(-1)^{n-1}(n-1)2^{n-2}.$$
There are $ n$ points ($ n \geq 4$) on a sphere with radius $ R$, and not all of them lie on the same semi-sphere. Prove that among all the angles formed by any two of the $ n$ points and the sphere centre $ O$ ($ O$ is the vertex of the angle), there is at least one that is not less than $ \displaystyle 2 \arcsin{\frac{\sqrt{6}}{3}}$.
Find the smallest positive integer $n$ such that if $n$ squares of a $1000 \times 1000$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board.