Found problems: 5802
For a positive integer $n$, let $d(n)$ be the number of all positive divisors of $n$. Find all positive integers $n$ such that $d(n)^3=4n$.
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]
At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid?
[i]Proposed by Evan Chen[/i]
Find all polynomials $P$ with integer coefficients such that $P (0)\ne 0$ and $$P^n(m)\cdot P^m(n)$$ is a square of an integer for all nonnegative integers $n, m$.
[i]Remark:[/i] For a nonnegative integer $k$ and an integer $n$, $P^k(n)$ is defined as follows: $P^k(n) = n$ if $k = 0$ and $P^k(n)=P(P(^{k-1}(n))$ if $k >0$.
Proposed by Adrian Beker.
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.
An alphabet consists of $n$ letters. What is the maximal length of a word if we know that any two consecutive letters $a,b$ of the word are different and that the word cannot be reduced to a word of the kind $abab$ with $a\neq b$ by removing letters.
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}$.
Find all functions $ f: \mathbb{N^{*}}\to \mathbb{N^{*}}$ satisfying
\[ \left(f^{2}\left(m\right)+f\left(n\right)\right) \mid \left(m^{2}+n\right)^{2}\]
for any two positive integers $ m$ and $ n$.
[i]Remark.[/i] The abbreviation $ \mathbb{N^{*}}$ stands for the set of all positive integers:
$ \mathbb{N^{*}}=\left\{1,2,3,...\right\}$.
By $ f^{2}\left(m\right)$, we mean $ \left(f\left(m\right)\right)^{2}$ (and not $ f\left(f\left(m\right)\right)$).
[i]Proposed by Mohsen Jamali, Iran[/i]
Find all pairs of positive integers $m,n\geq3$ for which there exist infinitely many positive integers $a$ such that \[ \frac{a^m+a-1}{a^n+a^2-1} \] is itself an integer.
[i]Laurentiu Panaitopol, Romania[/i]
Find all functions $f$ from the reals into the reals such that \[ f(ab) = f(a+b) \] for all irrational $a, b$.
$\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?
Consider a $(2m-1)\times(2n-1)$ rectangular region, where $m$ and $n$ are integers such that $m,n\ge 4.$ The region is to be tiled using tiles of the two types shown:
\[
\begin{picture}(140,40)
\put(0,0){\line(0,1){40}}
\put(0,0){\line(1,0){20}}
\put(0,40){\line(1,0){40}}
\put(20,0){\line(0,1){20}}
\put(20,20){\line(1,0){20}}
\put(40,20){\line(0,1){20}}
\multiput(0,20)(5,0){4}{\line(1,0){3}}
\multiput(20,20)(0,5){4}{\line(0,1){3}}
\put(80,0){\line(1,0){40}}
\put(120,0){\line(0,1){20}}
\put(120,20){\line(1,0){20}}
\put(140,20){\line(0,1){20}}
\put(80,0){\line(0,1){20}}
\put(80,20){\line(1,0){20}}
\put(100,20){\line(0,1){20}}
\put(100,40){\line(1,0){40}}
\multiput(100,0)(0,5){4}{\line(0,1){3}}
\multiput(100,20)(5,0){4}{\line(1,0){3}}
\multiput(120,20)(0,5){4}{\line(0,1){3}}
\end{picture}
\]
(The dotted lines divide the tiles into $1\times 1$ squares.) The tiles may be rotated and reflected, as long as their sides are parallel to the sides of the rectangular region. They must all fit within the region, and they must cover it completely without overlapping.
What is the minimum number of tiles required to tile the region?
Let $a$ be an integer and $n$ a positive integer . Show that the sum :
$$\sum_{k=1}^{n} a^{(k,n)}$$ is divisible by $n$ , where $(x,y)$ is the greatest common divisor of the numbers $x$ and $y$ .
Each side of a convex $2019$-gon polygon is dyed with red, yellow and blue, and there are exactly $673$ sides of each kind of color. Prove that there exists at least one way to draw $2016$ diagonals to divide the convex $2019$-gon polygon into $2017$ triangles, such that any two of the $2016$ diagonals don't have intersection inside the $2019$-gon polygon,and for any triangle in all the $2017$ triangles, the colors of the three sides of the triangle are all the same, either totally different.
An airline company is planning to introduce a network of connections between the ten different airports of Sawubonia. The airports are ranked by priority from first to last (with no ties). We call such a network [i]feasible[/i] if it satisfies the following conditions:
[list]
[*] All connections operate in both directions
[*] If there is a direct connection between two airports A and B, and C has higher priority than B, then there must also be a direct connection between A and C.[/list]
Some of the airports may not be served, and even the empty network (no connections at all) is allowed. How many feasible networks are there?
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.
For 31 years, n (>6) tennis players have records of wins. It turns out that for every two players, there is a third player who has won over them before. Prove that for every integer $k,l$ such that $2^{2^k+1}-1>n, 1<l<2k+1$, there exist $l$ players ($A_1, A_2, ... , A_l$) such that every player $A_{i+1}$ won over $A_i$. ($A_{l+1}$ is same as $A_1$)
Suppose $a$ is a non-zero real number such that $a +\frac{1}{a}$ is a whole number.
(a) Prove that $a^2 +\frac{1}{a^2}$ is also an integer.
(b) Prove that $a^n+\frac{1}{a^n}$ is also an integer, for any integer value positive of $n$.
Let $n>1$ be an integer and let $a_0,a_1,\ldots,a_n$ be non-negative real numbers. Definite $S_k=\sum_{i\equal{}0}^k \binom{k}{i}a_i$ for $k=0,1,\ldots,n$. Prove that\[\frac{1}{n} \sum_{k\equal{}0}^{n-1} S_k^2-\frac{1}{n^2}\left(\sum_{k\equal{}0}^{n} S_k\right)^2\le \frac{4}{45} (S_n-S_0)^2.\]
Let $s(n)$ denote the smallest prime divisor and $d(n)$ denote the number of positive divisors of a positive integer $n>1$. Is it possible to choose $2023$ positive integers $a_{1},a_{2},...,a_{2023}$ with $a_{1}<a_{2}-1<...<a_{2023}-2022$ such that for all $k=1,...,2022$ we have $d(a_{k+1}-a_{k}-1)>2023^{k}$ and $s(a_{k+1}-a_{k}) > 2023^{k}$?
[i]Authored by Nikola Velov[/i]
The 2010 positive numbers $a_1, a_2, \ldots , a_{2010}$ satisfy the inequality $a_ia_j \le i+j$ for all distinct indices $i, j$. Determine, with proof, the largest possible value of the product $a_1a_2\ldots a_{2010}$.
Given the graph $G$ and cycle $C$ in it, we can perform the following operation: add another vertex $v$ to the graph, connect it to all vertices in $C$ and erase all the edges from $C$. Prove that we cannot perform the operation indefinitely on a given graph.