Found problems: 1782
An array $ n\times n$ is given, consisting of $ n^2$ unit squares. A [i]pawn[/i] is placed arbitrarily on a unit square. The pawn can move from a square of the $ k$-th column to any square of the $ k$-th row. Show that there exists a sequence of $ n^2$ moves of the pawn so that all the unit squares of the array are visited once, the pawn returning to its original position.
[b]Dinu Serbanescu[/b]
Find all functions $f:\mathbb{R}^+\to\mathbb{R}^+$ such that whenever $a>b>c>d>0$ and $ad=bc$,
\[f(a+d)+f(b-c)=f(a-d)+f(b+c).\]
[i]Calvin Deng.[/i]
There are $ n \plus{} 1$ cells in a row labeled from $ 0$ to $ n$ and $ n \plus{} 1$ cards labeled from $ 0$ to $ n$. The cards are arbitrarily placed in the cells, one per cell. The objective is to get card $ i$ into cell $ i$ for each $ i$. The allowed move is to find the smallest $ h$ such that cell $ h$ has a card with a label $ k > h$, pick up that card, slide the cards in cells $ h \plus{} 1$, $ h \plus{} 2$, ... , $ k$ one cell to the left and to place card $ k$ in cell $ k$. Show that at most $ 2^n \minus{} 1$ moves are required to get every card into the correct cell and that there is a unique starting position which requires $ 2^n \minus{} 1$ moves. [For example, if $ n \equal{} 2$ and the initial position is 210, then we get 102, then 012, a total of 2 moves.]
What is the value of ${ \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+5\sqrt{1+\cdots }}}}}} $?
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}}$.
Define a sequence $ < a_n > _{n\geq0}$ by $ a_0 \equal{} 0$, $ a_1 \equal{} 1$ and
\[ a_n \equal{} 2a_{n \minus{} 1} \plus{} a_{n \minus{} 2},\]
for $ n\geq2.$
$ (a)$ For every $ m > 0$ and $ 0\leq j\leq m,$ prove that $ 2a_m$ divides
$ a_{m \plus{} j} \plus{} ( \minus{} 1)^ja_{m \minus{} j}$.
$ (b)$ Suppose $ 2^k$ divides $ n$ for some natural numbers $ n$ and $ k$. Prove that $ 2^k$ divides $ a_n.$
Determine all $(m,n) \in \mathbb{Z}^+ \times \mathbb{Z}^+$ which satisfy $3^m-7^n=2.$
Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $.
We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.
Given that $g(n) = \frac{1}{{2 + \frac{1}{{3 + \frac{1}{{... + \frac{1}{{n - 1}}}}}}}}$ and $k(n) = \frac{1}{{2 + \frac{1}{{3 + \frac{1}{{... + \frac{1}{{n - 1 + \frac{1}{n}}}}}}}}}$, for natural $n$. Prove that $\left| {g(n) - k(n)} \right| \le \frac{1}{{(n - 1)!n!}}$.
$S,T$ are two trees without vertices of degree 2. To each edge is associated a positive number which is called length of this edge. Distance between two arbitrary vertices $v,w$ in this graph is defined by sum of length of all edges in the path between $v$ and $w$. Let $f$ be a bijective function from leaves of $S$ to leaves of $T$, such that for each two leaves $u,v$ of $S$, distance of $u,v$ in $S$ is equal to distance of $f(u), f(v)$ in $T$. Prove that there is a bijective function $g$ from vertices of $S$ to vertices of $T$ such that for each two vertices $u,v$ of $S$, distance of $u,v$ in $S$ is equal to distance of $g(u)$ and $g(v)$ in $T$.
Let $f$ be a function defined for the non-negative integers, such that:
a) $f(n)=0$ if $n=2^{j}-1$ for some $j \geq 0$.
b) $f(n+1)=f(n)-1$ otherwise.
i) Show that for every $n \geq 0$ there exists $k \geq 0$ such that $f(n)+n=2^{k}-1$.
ii) Find $f(2^{1990})$.
Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function, and let $f^m$ be $f$ applied $m$ times. Suppose that for every $n \in \mathbb{N}$ there exists a $k \in \mathbb{N}$ such that $f^{2k}(n)=n+k$, and let $k_n$ be the smallest such $k$. Prove that the sequence $k_1,k_2,\ldots $ is unbounded.
[i]Proposed by Palmer Mebane, United States[/i]
A blackboard contains 68 pairs of nonzero integers. Suppose that for each positive integer $k$ at most one of the pairs $(k, k)$ and $(-k, -k)$ is written on the blackboard. A student erases some of the 136 integers, subject to the condition that no two erased integers may add to 0. The student then scores one point for each of the 68 pairs in which at least one integer is erased. Determine, with proof, the largest number $N$ of points that the student can guarantee to score regardless of which 68 pairs have been written on the board.
Find all functions $ f:\mathbb{Q}\to\mathbb{R}$ that satisfy $ f(x\plus{}y)\equal{}f(x)f(y)\minus{}f(xy)\plus{}1$ for every $x,y\in\mathbb{Q}$.
$\text{ }$
[asy]
unitsize(11);
for(int i=0; i<6; ++i)
{
if(i<5)
draw( (i, 0)--(i,5) );
else draw( (i, 0)--(i,2) );
if(i < 3)
draw((0,i)--(5,i));
else draw((0,i)--(4,i));
}
[/asy]
We are dividing the above figure into parts with shapes: [asy]
unitsize(11);
draw((0,0)--(0,2));
draw((1,0)--(1,2));
draw((2,1)--(2,2));
draw((0,0)--(1,0));
draw((0,1)--(2,1));
draw((0,2)--(2,2));
[/asy][asy]
unitsize(11);
draw((0,0)--(0,2));
draw((1,0)--(1,2));
draw((2,1)--(2,2));
draw((3,1)--(3,2));
draw((0,0)--(1,0));
draw((0,1)--(3,1));
draw((0,2)--(3,2));
[/asy]
After that division, find the number of
[asy]
unitsize(11);
draw((0,0)--(0,2));
draw((1,0)--(1,2));
draw((2,1)--(2,2));
draw((0,0)--(1,0));
draw((0,1)--(2,1));
draw((0,2)--(2,2));
[/asy]
shaped parts.
Consider an infinite strip of unit squares. The squares are numbered "1", "2", "3", ... A pawn starts on one of the squares and it can move according to the following rules:
(1) from the square numbered "$n$" to the square numbered "$2n$", and vice versa;
(2) from the square numbered "$n$" to the square numbered "$3n + 1$", and vice versa.
Show that the pawn can reach the square numbered "$1$" in a finite number of moves.
Let $n\ge 1$ be an odd integer. Alice and Bob play the following game, taking alternating turns, with Alice playing first. The playing area consists of $n$ spaces, arranged in a line. Initially all spaces are empty. At each turn, a player either
• places a stone in an empty space, or
• removes a stone from a nonempty space $s,$ places a stone in the nearest empty space to the left of $s$ (if such a space exists), and places a stone in the nearest empty space to the right of $s$ (if such a space exists).
Furthermore, a move is permitted only if the resulting position has not occurred previously in the game. A player loses if he or she is unable to move. Assuming that both players play optimally throughout the game, what moves may Alice make on her first turn?
Let the sequence $ \{a_n\}_{n\geq 1}$ be defined by $ a_1 \equal{} 20$, $ a_2 \equal{} 30$ and $ a_{n \plus{} 2} \equal{} 3a_{n \plus{} 1} \minus{} a_n$ for all $ n\geq 1$. Find all positive integers $ n$ such that $ 1 \plus{} 5a_n a_{n \plus{} 1}$ is a perfect square.
Yamin and Tamim are playing a game with subsets of $\{1, 2, \ldots, n\}$ where $n \geq 3$.
[list]
[*] Tamim starts the game with the empty set.
[*] On Yamin's turn, he adds a proper non-empty subset of $\{1, 2, \ldots, n\}$ to his collection $F$ of blocked sets.
[*] On Tamim's turn, he adds or removes a positive integer less than or equal to $n$ to or from their set but Tamim can never add or remove an element so that his set becomes one of the blocked sets in $F$.
[/list]
Tamim wins if he can make his set to be $\{1, 2, \ldots, n\}$. Yamin wins if he can stop Tamim from doing so. Yamin goes first and they alternate making their moves. Does Tamim have a winning strategy?
[i]Proposed by Ahmed Ittihad Hasib[/i]
Let $f$ be a polynomial with real coefficients of degree $n$. Suppose that $\displaystyle \frac{f(x)-f(y)}{x-y}$ is an integer for all $0 \leq x<y \leq n$. Prove that $a-b | f(a)-f(b)$ for all distinct integers $a,b$.
Let $n$ be an integer, and let $X$ be a set of $n+2$ integers each of absolute value at most $n$. Show that there exist three distinct numbers $a, b, c \in X$ such that $c=a+b$.
Let $F=A_0A_1...A_n$ be a convex polygon in the plane. Define for all $1 \leq k \leq n-1$ the operation $f_k$ which replaces $F$ with a new polygon $f_k(F)=A_0A_1..A_{k-1}A_k^\prime A_{k+1}...A_n$ where $A_k^\prime$ is the symmetric of $A_k$ with respect to the perpendicular bisector of $A_{k-1}A_{k+1}$. Prove that $(f_1\circ f_2 \circ f_3 \circ...\circ f_{n-1})^n(F)=F$.
At a certain mathematical conference, every pair of mathematicians are either friends or strangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two (i.e., is of the form $ 2^k$ for some positive integer $ k$).
We select a real number $\alpha$ uniformly and at random from the interval $(0,500)$. Define \[ S = \frac{1}{\alpha} \sum_{m=1}^{1000} \sum_{n=m}^{1000} \left\lfloor \frac{m+\alpha}{n} \right\rfloor. \] Let $p$ denote the probability that $S \ge 1200$. Compute $1000p$.
[i]Proposed by Evan Chen[/i]
Let $n$ be a positive integer, set $S_n = \{ (a_1,a_2,\cdots,a_{2^n}) \mid a_i=0 \ \text{or} \ 1, 1 \leq i \leq 2^n\}$. For any two elements $a=(a_1,a_2,\cdots,a_{2^n})$ and $b=(b_1,b_2,\cdots,b_{2^n})$ of $S_n$, define
\[ d(a,b)= \sum_{i=1}^{2^n} |a_i - b_i| \]
We call $A \subseteq S_n$ a $\textsl{Good Subset}$ if $d(a,b) \geq 2^{n-1}$ holds for any two distinct elements $a$ and $b$ of $A$. How many elements can the $\textsl{Good Subset}$ of $S_n$ at most have?