Found problems: 5802
Let $n$ be a positive integer. Let $P_n=\{2^n,2^{n-1}\cdot 3, 2^{n-2}\cdot 3^2, \dots, 3^n \}.$ For each subset $X$ of $P_n$, we write $S_X$ for the sum of all elements of $X$, with the convention that $S_{\emptyset}=0$ where $\emptyset$ is the empty set. Suppose that $y$ is a real number with $0 \leq y \leq 3^{n+1}-2^{n+1}.$
Prove that there is a subset $Y$ of $P_n$ such that $0 \leq y-S_Y < 2^n$
An integer $n$, unknown to you, has been randomly chosen in the interval $[1,2002]$ with uniform probability. Your objective is to select $n$ in an ODD number of guess. After each incorrect guess, you are informed whether $n$ is higher or lower, and you $\textbf{must}$ guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than $\tfrac{2}{3}$.
Let $f(x)$ be a function satisfying
\[xf(x)=\ln x \ \ \ \ \ \ \ \ \text{for} \ \ x>0\]
Show that $f^{(n)}(1)=(-1)^{n+1}n!\left(1+\frac{1}{2}+\cdots+\frac{1}{n}\right)$ where $f^{(n)}(x)$ denotes the $n$-th derivative evaluated at $x$.
Let $a,b,c,d$ be positive integers such that $ad \neq bc$ and $gcd(a,b,c,d)=1$. Let $S$ be the set of values attained by $\gcd(an+b,cn+d)$ as $n$ runs through the positive integers. Show that $S$ is the set of all positive divisors of some positive integer.
If $x$ is a positive real number, and $n$ is a positive integer, prove that
\[[ nx] > \frac{[ x]}1 + \frac{[ 2x]}2 +\frac{[ 3x]}3 + \cdots + \frac{[ nx]}n,\]
where $[t]$ denotes the greatest integer less than or equal to $t$. For example, $[ \pi] = 3$ and $\left[\sqrt2\right] = 1$.
$A$ and $B$ play a game, given an integer $N$, $A$ writes down $1$ first, then every player sees the last number written and if it is $n$ then in his turn he writes $n+1$ or $2n$, but his number cannot be bigger than $N$. The player who writes $N$ wins. For which values of $N$ does $B$ win?
[i]Proposed by A. Slinko & S. Marshall, New Zealand[/i]
Two people play a game as follows: At the beginning both of them have one point and in every move, one of them can double it's points, or when the other have more point than him, subtract to him his points. Can the two competitors have 2009 and 2002 points respectively? What about 2009 and 2003? Generally which couples of points can they have?
Show that every number of the form $2^{p}3^{q}$ , where $p,q$ are nonnegative integers, divides some number of the form $a_{2k}10^{2k}+a_{2k-2}10^{2k-2}+...+a_{2}10^{2}+a_{0}$, where $a_{2i}\in\{1,2,...,9\}$
Consider the following sequence : $a_1=1 ; a_n=\frac{a_[{\frac{n}{2}]}}{2}+\frac{a_[{\frac{n}{3}]}}{3}+\ldots+\frac{a_[{\frac{n}{n}]}}{n}$. Prove that $ a_{2n}< 2*a_{n } (\forall n\in\mathbb{N})$
For a positive integer $N$, let $T(N)$ denote the number of arrangements of the integers $1, 2, \cdots N$ into a sequence $a_1, a_2, \cdots a_N$ such that $a_i > a_{2i}$ for all $i$, $1 \le i < 2i \le N$ and $a_i > a_{2i+1}$ for all $i$, $1 \le i < 2i+1 \le N$. For example, $T(3)$ is $2$, since the possible arrangements are $321$ and $312$
(a) Find $T(7)$
(b) If $K$ is the largest non-negative integer so that $2^K$ divides $T(2^n - 1)$, show that $K = 2^n - n - 1$.
(c) Find the largest non-negative integer $K$ so that $2^K$ divides $T(2^n + 1)$
Suppose a grid with $2m$ rows and $2n$ columns is given, where $m$ and $n$ are positive integers. You may place one pawn on any square of this grid, except the bottom left one or the top right one. After placing the pawn, a snail wants to undertake a journey on the grid. Starting from the bottom left square, it wants to visit every square exactly once, except the one with the pawn on it, which the snail wants to avoid. Moreover, it wants to fi nish in the top right square. It can only move horizontally or vertically on the grid.
On which squares can you put the pawn for the snail to be able to finish its journey?
Show that for any finite set $S$ of distinct positive integers, we can find a set $T \supseteq S$ such that every member of $T$ divides the sum of all the members of $T$.
[b]Original Statement:[/b]
A finite set of (distinct) positive integers is called a [b]DS-set[/b] if each of the integers divides the sum of them all. Prove that every finite set of positive integers is a subset of some [b]DS-set[/b].
Let $(a_n)_{n\ge 1}$ be a sequence of real numbers such that
\[a_1\binom{n}{1}+a_2\binom{n}{2}+\ldots+a_n\binom{n}{n}=2^{n-1}a_n,\ (\forall)n\in \mathbb{N}^*\]
Prove that $(a_n)_{n\ge 1}$ is an arithmetical progression.
[i]Lucian Dragomir[/i]
Find all functions $f: \mathbb{Z} \to \mathbb{Z}$, such that $$f(x+y)((f(x) - f(y))^2+f(xy))=f(x^3)+f(y^3)$$ for all integers $x, y$.
For any integer $n+1,\ldots, 2n$ ($n$ is a natural number) consider its greatest odd divisor. Prove that the sum of all these divisors equals $n^2.$
Kid and Karlsson play a game. Initially they have a square piece of chocolate $2019\times 2019$ grid with $1\times 1$ cells . On every turn Kid divides an arbitrary piece of chololate into three rectanglular pieces by cells, and then Karlsson chooses one of them and eats it. The game finishes when it's impossible to make a legal move. Kid wins if there was made an even number of moves, Karlsson wins if there was made an odd number of moves.
Who has the winning strategy?
[i] (Д. Ширяев)[/i]
[hide=Thanks]Thanks to the user Vlados021 for translating the problem.[/hide]
Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i \plus{} a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$.
[i]Proposed by Mohsen Jamaali, Iran[/i]
Let $b\geq2$ and $w\geq2$ be fixed integers, and $n=b+w$. Given are $2b$ identical black rods and $2w$ identical white rods, each of side length 1.
We assemble a regular $2n-$gon using these rods so that parallel sides are the same color. Then, a convex $2b$-gon $B$ is formed by translating the black rods, and a convex $2w$-gon $W$ is formed by translating the white rods. An example of one way of doing the assembly when $b=3$ and $w=2$ is shown below, as well as the resulting polygons $B$ and $W$.
[asy]size(10cm);
real w = 2*Sin(18);
real h = 0.10 * w;
real d = 0.33 * h;
picture wht;
picture blk;
draw(wht, (0,0)--(w,0)--(w+d,h)--(-d,h)--cycle);
fill(blk, (0,0)--(w,0)--(w+d,h)--(-d,h)--cycle, black);
// draw(unitcircle, blue+dotted);
// Original polygon
add(shift(dir(108))*blk);
add(shift(dir(72))*rotate(324)*blk);
add(shift(dir(36))*rotate(288)*wht);
add(shift(dir(0))*rotate(252)*blk);
add(shift(dir(324))*rotate(216)*wht);
add(shift(dir(288))*rotate(180)*blk);
add(shift(dir(252))*rotate(144)*blk);
add(shift(dir(216))*rotate(108)*wht);
add(shift(dir(180))*rotate(72)*blk);
add(shift(dir(144))*rotate(36)*wht);
// White shifted
real Wk = 1.2;
pair W1 = (1.8,0.1);
pair W2 = W1 + w*dir(36);
pair W3 = W2 + w*dir(108);
pair W4 = W3 + w*dir(216);
path Wgon = W1--W2--W3--W4--cycle;
draw(Wgon);
pair WO = (W1+W3)/2;
transform Wt = shift(WO)*scale(Wk)*shift(-WO);
draw(Wt * Wgon);
label("$W$", WO);
/*
draw(W1--Wt*W1);
draw(W2--Wt*W2);
draw(W3--Wt*W3);
draw(W4--Wt*W4);
*/
// Black shifted
real Bk = 1.10;
pair B1 = (1.5,-0.1);
pair B2 = B1 + w*dir(0);
pair B3 = B2 + w*dir(324);
pair B4 = B3 + w*dir(252);
pair B5 = B4 + w*dir(180);
pair B6 = B5 + w*dir(144);
path Bgon = B1--B2--B3--B4--B5--B6--cycle;
pair BO = (B1+B4)/2;
transform Bt = shift(BO)*scale(Bk)*shift(-BO);
fill(Bt * Bgon, black);
fill(Bgon, white);
label("$B$", BO);[/asy]
Prove that the difference of the areas of $B$ and $W$ depends only on the numbers $b$ and $w$, and not on how the $2n$-gon was assembled.
[i]Proposed by Ankan Bhattacharya[/i]
Let $\mathcal{A}$ denote the set of all polynomials in three variables $x, y, z$ with integer coefficients. Let $\mathcal{B}$ denote the subset of $\mathcal{A}$ formed by all polynomials which can be expressed as
\begin{align*}
(x + y + z)P(x, y, z) + (xy + yz + zx)Q(x, y, z) + xyzR(x, y, z)
\end{align*}
with $P, Q, R \in \mathcal{A}$. Find the smallest non-negative integer $n$ such that $x^i y^j z^k \in \mathcal{B}$ for all non-negative integers $i, j, k$ satisfying $i + j + k \geq n$.
Let $n$ be a natural number. Prove that,
\[ \left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor \]
is even.
There is a broken computer such that only three primitive data $c$, $1$ and $-1$ are reserved. Only allowed operation may take $u$ and $v$ and output $u \cdot v + v.$ At the beginning, $u,v \in \{c, 1, -1\}.$ After then, it can also take the value of the previous step (only one step back) besides $\{c, 1, -1\}$. Prove that for any polynomial $P_{n}(x) = a_0 \cdot x^n + a_1 \cdot x^{n-1} + \ldots + a_n$ with integer coefficients, the value of $P_n(c)$ can be computed using this computer after only finite operation.
Let bet a sequence $\left( a_n \right)_{n\ge 1} $ with $ a_1=1 $ and defined as $ a_n=\sqrt[n]{1+na_{n-1}} . $
Show that $ \left( a_n \right)_{n\ge 1} $ is convergent and determine its limit.
[i]Florian Dumitrel[/i]
Find all pairs $(m,n)$ of nonnegative integers for which \[m^2 + 2 \cdot 3^n = m\left(2^{n+1} - 1\right).\]
[i]Proposed by Angelo Di Pasquale, Australia[/i]
Define a sequence $<f_0 (x), f_1 (x), f_2 (x), \dots>$ of functions by $$f_0 (x) = 1$$ $$f_1(x)=x$$ $$(f_n(x))^2 - 1 = f_{n+1}(x) f_{n-1}(x)$$ for $n \ge 1$. Prove that each $f_n (x)$ is a polynomial with integer coefficients.
Let $P$ be a polynomial with real coefficients. Find all functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that there exists a real number $t$ such that
\[f(x+t) - f(x) = P(x)\]
for all $x \in \mathbb{R}$.