Found problems: 357
Starting from a positive integer $n$, we can replace the current number with a multiple of the current number or by deleting one or more zeroes from the decimal representation of the current number. Prove that for all values of $n$, it is possible to obtain a single-digit number by applying the above algorithm a finite number of times.
There is a nice solution to this...
Determine $w^2+x^2+y^2+z^2$ if
\[ \begin{array}{l} \displaystyle \frac{x^2}{2^2-1}+\frac{y^2}{2^2-3^2}+\frac{z^2}{2^2-5^2}+\frac{w^2}{2^2-7^2}=1 \\ \displaystyle \frac{x^2}{4^2-1}+\frac{y^2}{4^2-3^2}+\frac{z^2}{4^2-5^2}+\frac{w^2}{4^2-7^2}=1 \\ \displaystyle \frac{x^2}{6^2-1}+\frac{y^2}{6^2-3^2}+\frac{z^2}{6^2-5^2}+\frac{w^2}{6^2-7^2}=1 \\ \displaystyle \frac{x^2}{8^2-1}+\frac{y^2}{8^2-3^2}+\frac{z^2}{8^2-5^2}+\frac{w^2}{8^2-7^2}=1 \\ \end{array} \]
Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.
Let $ k \equal{} \sqrt[3]{3}$.
a, Find all polynomials $ p(x)$ with rationl coefficients whose degree are as least as possible such that $ p(k \plus{} k^2) \equal{} 3 \plus{} k$.
b, Does there exist a polynomial $ p(x)$ with integer coefficients satisfying $ p(k \plus{} k^2) \equal{} 3 \plus{} k$
Given an initial integer $ n_0 > 1$, two players, $ {\mathcal A}$ and $ {\mathcal B}$, choose integers $ n_1$, $ n_2$, $ n_3$, $ \ldots$ alternately according to the following rules :
[b]I.)[/b] Knowing $ n_{2k}$, $ {\mathcal A}$ chooses any integer $ n_{2k \plus{} 1}$ such that
\[ n_{2k} \leq n_{2k \plus{} 1} \leq n_{2k}^2.
\]
[b]II.)[/b] Knowing $ n_{2k \plus{} 1}$, $ {\mathcal B}$ chooses any integer $ n_{2k \plus{} 2}$ such that
\[ \frac {n_{2k \plus{} 1}}{n_{2k \plus{} 2}}
\]
is a prime raised to a positive integer power.
Player $ {\mathcal A}$ wins the game by choosing the number 1990; player $ {\mathcal B}$ wins by choosing the number 1. For which $ n_0$ does :
[b]a.)[/b] $ {\mathcal A}$ have a winning strategy?
[b]b.)[/b] $ {\mathcal B}$ have a winning strategy?
[b]c.)[/b] Neither player have a winning strategy?
In every $1\times1$ cell of a rectangle board a natural number is written. In one step it is allowed the numbers written in every cell of arbitrary chosen row, to be doubled, or the numbers written in the cells of the arbitrary chosen column to be decreased by 1. Will after final number of steps all the numbers on the board be $0$?
Let $m$ boxes be given, with some balls in each box. Let $n < m$ be a given integer. The following operation is performed: choose $n$ of the boxes and put $1$ ball in each of them. Prove:
[i](a) [/i]If $m$ and $n$ are relatively prime, then it is possible, by performing the operation a finite number of times, to arrive at the situation that all the boxes contain an equal number of balls.
[i](b)[/i] If $m$ and $n$ are not relatively prime, there exist initial distributions of balls in the boxes such that an equal distribution is not possible to achieve.
There are $n$ natural numbers written on the board. Every move, we could erase $a,b$ and change it to $\gcd(a,b)$ and $\text{lcm}(a,b) - \gcd(a,b)$. Prove that in finite number of moves, all numbers in the board could be made to be equal.
Let $k\ge 1$ be a positive integer.
We consider $4k$ chips, $2k$ of which are red and $2k$ of which are blue. A sequence of those $4k$ chips can be transformed into another sequence by a so-called move, consisting of interchanging a number (possibly one) of consecutive red chips with an
equal number of consecutive blue chips. For example, we can move from $r\underline{bb}br\underline{rr}b$ to $r\underline{rr}br\underline{bb}b$ where $r$ denotes a red chip and $b$ denotes a blue chip.
Determine the smallest number $n$ (as a function of $k$) such that starting from any initial sequence of the $4k$ chips, we need at most $n$ moves to reach the state in which the first $2k$ chips are red.
Peter has three accounts in a bank, each with an integral number of dollars. He is only allowed to transfer money from one account to another so that the amount of money in the latter is doubled. Prove that Peter can always transfer all his money into two accounts. Can Peter always transfer all his money into one account?
Let us consider a first-order language $L$ with a ternary predicate $\operatorname{Plus}$. Hence (well-formed) formulas of $L$ are built of symbols for variables, logical connectives, quantifiers, brackets, and the predicate symbol $\operatorname{Plus}$.
$$(\exists x_1)(\forall x_2):\operatorname{Plus}(x_2,x_1,x_2)\wedge(\forall x_3):\neg\operatorname{Plus}(x_1,x_3,x_3)$$
is an example of such a formula. Recall that a formula is [i]closed[/i] iff each variable symbol occurs within the scope of a quantifier. Show that there exists an algorithm which decides whether or not a given closed formula of $L$ is true for the set $\mathbb N$ of natural numbers ($\{0,1,2,\ldots\}$) where $\operatorname{Plus}(x,y,z)$ is interpreted as $x+y=z$.
What is that largest positive integer $n$ for which $n^3+100$ is divisible by $n+10$?
Two distinct positive integers $a,b$ are written on the board. The smaller of them is erased and replaced with the number $\frac{ab}{|a-b|}$. This process is repeated as long as the two numbers are not equal. Prove that eventually the two numbers on the board will be equal.
In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i].
Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.
[i]Author: Vasily Astakhov, Russia[/i]
Set $S_n = \sum_{p=1}^n (p^5+p^7)$. Determine the greatest common divisor of $S_n$ and $S_{3n}.$
At the entrance to a cave is a rotating round table. On top of the table are $n$ identical barrels, evenly spaced along its circumference. Inside each barrel is a herring either with its head up or its head down. In a move, Ali Baba chooses from $1$ to $n$ of the barrels and turns them upside down. Then the table spins around. When it stops, it is impossible to tell which barrels have been turned over. The cave will open if the heads of the herrings in all $n$ barrels are up or are all down. Determine all values of $n$ for which Ali Baba can open the cave in a fi nite number of moves.
[i](11 points)[/i]
A magician intends to perform the following trick. She announces a positive integer $n$, along with $2n$ real numbers $x_1 < \dots < x_{2n}$, to the audience. A member of the audience then secretly chooses a polynomial $P(x)$ of degree $n$ with real coefficients, computes the $2n$ values $P(x_1), \dots , P(x_{2n})$, and writes down these $2n$ values on the blackboard in non-decreasing order. After that the magician announces the secret polynomial to the audience. Can the magician find a strategy to perform such a trick?
There is $n$ black points in the plane.We do the following algorithm:
Start from any point from those $n$ points and colour it red. Then connect this point to the nearest black point available and colour this new point red. Then do the same with this point but at any step , but you are never allowed to draw a line which intersects on of the current drawn segments. If you reach an intersection , the algorithm is over.
Is it true that for any $n$ and at any initial position , we can start from a point st in the algorithm , we reach all the points?
Evaluate
\[ \int_{\minus{}1}^1 \frac{1\plus{}2x^2\plus{}3x^4\plus{}4x^6\plus{}5x^8\plus{}6x^{10}\plus{}7x^{12}}{\sqrt{(1\plus{}x^2)(1\plus{}x^4)(1\plus{}x^6)}}dx.\]
Let $n$ be a positive integer. The numbers $\{1, 2, ..., n^2\}$ are placed in an $n \times n$ grid, each exactly once. The grid is said to be [i]Muirhead-able[/i] if the sum of the entries in each column is the same, but for every $1 \le i,k \le n-1$, the sum of the first $k$ entries in column $i$ is at least the sum of the first $k$ entries in column $i+1$. For which $n$ can one construct a Muirhead-able array such that the entries in each column are decreasing?
[i]Proposed by Evan Chen[/i]
Let $\mathbb{Z}^+$ denote the set of positive integers. Find all functions $f: \mathbb{Z}^+ \times \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ such that
[list=i]
[*] $f(m,m)=m$
[*] $f(m,k) = f(k,m)$
[*] $f(m, m+k) = f(m,k)$[/list] , for each $m,k \in \mathbb{Z}^+$.
Let $ A_0 \equal{} (a_1,\dots,a_n)$ be a finite sequence of real numbers. For each $ k\geq 0$, from the sequence $ A_k \equal{} (x_1,\dots,x_k)$ we construct a new sequence $ A_{k \plus{} 1}$ in the following way.
1. We choose a partition $ \{1,\dots,n\} \equal{} I\cup J$, where $ I$ and $ J$ are two disjoint sets, such that the expression
\[ \left|\sum_{i\in I}x_i \minus{} \sum_{j\in J}x_j\right|
\]
attains the smallest value. (We allow $ I$ or $ J$ to be empty; in this case the corresponding sum is 0.) If there are several such partitions, one is chosen arbitrarily.
2. We set $ A_{k \plus{} 1} \equal{} (y_1,\dots,y_n)$ where $ y_i \equal{} x_i \plus{} 1$ if $ i\in I$, and $ y_i \equal{} x_i \minus{} 1$ if $ i\in J$.
Prove that for some $ k$, the sequence $ A_k$ contains an element $ x$ such that $ |x|\geq\frac n2$.
[i]Author: Omid Hatami, Iran[/i]
Several policemen try to catch a thief who has $2m$ accomplices. To that end they place the accomplices under surveillance. In the beginning, the policemen shadow nobody. Every morning each policeman places under his surveillance one of the accomplices. Every evening the thief stops trusting one of his accomplices The thief is caught if by the $m$-th evening some policeman shadows exactly those $m$ accomplices who are still trusted by the thief. Prove that to guarantee the capture of the thief at least $2^m$ policemen are needed.
Prove that there exist two infinite sequences $ \{a_n\}_{n\ge 1}$ and $ \{b_n\}_{n\ge 1}$ of positive integers such that the following conditions hold simultaneously:
$ (i)$ $ 0 < a_1 < a_2 < a_3 < \cdots$;
$ (ii)$ $ a_n < b_n < a_n^2$, for all $ n\ge 1$;
$ (iii)$ $ a_n \minus{} 1$ divides $ b_n \minus{} 1$, for all $ n\ge 1$
$ (iv)$ $ a_n^2 \minus{} 1$ divides $ b_n^2 \minus{} 1$, for all $ n\ge 1$
[19 points out of 100 for the 6 problems]
A crazy physicist discovered a new kind of particle wich he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(ii) At any moment, he may double the whole family of imons in the lab by creating a copy $I'$ of each imon $I$. During this procedure, the two copies $I'$ and $J'$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I'$ becomes entangled with its original imon $I$; no other entanglements occur or disappear at this moment.
Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.