Found problems: 357
Prove that every positive integer can be written as a finite sum of distinct integral powers of the golden ratio.
Given a set $X$ and a function $f: X \rightarrow X$, for each $x \in X$ we define $f^1(x)=f(x)$ and, for each $j \ge 1$, $f^{j+1}(x)=f(f^j(x))$. We say that $a \in X$ is a fixed point of $f$ if $f(a)=a$. For each $x \in \mathbb{R}$, let $\pi (x)$ be the quantity of positive primes lesser or equal to $x$.
Given an positive integer $n$, we say that $f: \{1,2, \dots, n\} \rightarrow \{1,2, \dots, n\}$ is [i]catracha[/i] if $f^{f(k)}(k)=k$, for every $k=1, 2, \dots n$. Prove that:
(a) If $f$ is catracha, $f$ has at least $\pi (n) -\pi (\sqrt{n}) +1$ fixed points.
(b) If $n \ge 36$, there exists a catracha function $f$ with exactly $ \pi (n) -\pi (\sqrt{n}) + 1$ fixed points.
The polynomial $P(x)$ is cubic. What is the largest value of $k$ for which the polynomials $Q_{1}(x) = x^{2}+(k-29)x-k$ and $Q_{2}(x) = 2x^{2}+(2k-43)x+k$ are both factors of $P(x)$?
The image shown below is a cross with length 2. If length of a cross of length $k$ it is called a $k$-cross. (Each $k$-cross ahs $6k+1$ squares.)
[img]http://aycu08.webshots.com/image/4127/2003057947601864020_th.jpg[/img]
a) Prove that space can be tiled with $1$-crosses.
b) Prove that space can be tiled with $2$-crosses.
c) Prove that for $k\geq5$ space can not be tiled with $k$-crosses.
For any integer $d > 0,$ let $f(d)$ be the smallest possible integer that has exactly $d$ positive divisors (so for example we have $f(1)=1, f(5)=16,$ and $f(6)=12$). Prove that for every integer $k \geq 0$ the number $f\left(2^k\right)$ divides $f\left(2^{k+1}\right).$
[i]Proposed by Suhaimi Ramly, Malaysia[/i]
Each positive integer $a$ undergoes the following procedure in order to obtain the number $d = d\left(a\right)$:
(i) move the last digit of $a$ to the first position to obtain the numb er $b$;
(ii) square $b$ to obtain the number $c$;
(iii) move the first digit of $c$ to the end to obtain the number $d$.
(All the numbers in the problem are considered to be represented in base $10$.) For example, for $a=2003$, we get $b=3200$, $c=10240000$, and $d = 02400001 = 2400001 = d(2003)$.)
Find all numbers $a$ for which $d\left( a\right) =a^2$.
[i]Proposed by Zoran Sunic, USA[/i]
There is a standard deck of $52$ cards without jokers. The deck consists of four suits(diamond, club, heart, spade) which include thirteen cards in each. For each suit, all thirteen cards are ranked from “$2$” to “$A$” (i.e. $2, 3,\ldots , Q, K, A$). A pair of cards is called a “[i]straight flush[/i]” if these two cards belong to the same suit and their ranks are adjacent. Additionally, "$A$" and "$2$" are considered to be adjacent (i.e. "A" is also considered as "$1$"). For example, spade $A$ and spade $2$ form a “[i]straight flush[/i]”; diamond $10$ and diamond $Q$ are not a “[i]straight flush[/i]” pair. Determine how many ways of picking thirteen cards out of the deck such that all ranks are included but no “[i]straight flush[/i]” exists in them.
For a sequence $x_1,x_2,\ldots,x_n$ of real numbers, we define its $\textit{price}$ as \[\max_{1\le i\le n}|x_1+\cdots +x_i|.\] Given $n$ real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price $D$. Greedy George, on the other hand, chooses $x_1$ such that $|x_1 |$ is as small as possible; among the remaining numbers, he chooses $x_2$ such that $|x_1 + x_2 |$ is as small as possible, and so on. Thus, in the $i$-th step he chooses $x_i$ among the remaining numbers so as to minimise the value of $|x_1 + x_2 + \cdots x_i |$. In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price $G$.
Find the least possible constant $c$ such that for every positive integer $n$, for every collection of $n$ real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality $G\le cD$.
[i]Proposed by Georgia[/i]
The numbers $ 1, 2,\ldots, 50 $ are written on a blackboard. Each minute any two numbers are erased and their positive difference is written instead. At the end one number remains. Which values can take this number?
Five men and fi ve women stand in a circle in random order. The probability that every man stands next to at least one woman is $\tfrac m n$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$.
Three nonnegative real numbers $ r_1$, $ r_2$, $ r_3$ are written on a blackboard. These numbers have the property that there exist integers $ a_1$, $ a_2$, $ a_3$, not all zero, satisfying $ a_1r_1 \plus{} a_2r_2 \plus{} a_3r_3 \equal{} 0$. We are permitted to perform the following operation: find two numbers $ x$, $ y$ on the blackboard with $ x \le y$, then erase $ y$ and write $ y \minus{} x$ in its place. Prove that after a finite number of such operations, we can end up with at least one $ 0$ on the blackboard.
Sequences $ (x_n)$ and $ (y_n)$ are constructed as follows: $ x_0 \equal{} 365$, $ x_{n\plus{}1} \equal{} x_n\left(x^{1986} \plus{} 1\right) \plus{} 1622$, and $ y_0 \equal{} 16$, $ y_{n\plus{}1} \equal{} y_n\left(y^3 \plus{} 1\right) \minus{} 1952$, for all $ n \ge 0$. Prove that $ \left|x_n\minus{} y_k\right|\neq 0$ for any positive integers $ n$, $ k$.
Let $T$ be the set of ordered triples $(x,y,z)$, where $x,y,z$ are integers with $0\leq x,y,z\leq9$. Players $A$ and $B$ play the following guessing game. Player $A$ chooses a triple $(x,y,z)$ in $T$, and Player $B$ has to discover $A$[i]'s[/i] triple in as few moves as possible. A [i]move[/i] consists of the following: $B$ gives $A$ a triple $(a,b,c)$ in $T$, and $A$ replies by giving $B$ the number $\left|x+y-a-b\right |+\left|y+z-b-c\right|+\left|z+x-c-a\right|$. Find the minimum number of moves that $B$ needs to be sure of determining $A$[i]'s[/i] triple.
If $a_1, a_2, \cdots, a_7$ are not necessarily distinct real numbers such that $1 < a_i < 13$ for all $i$, then show that we can choose three of them such that they are the lengths of the sides of a triangle.
Martin invented the following algorithm. Let two irreducible fractions $ \frac{s_1}{t_1}$ and $ \frac{s_2}{t_2}$ be given as inputs, with the numerators and denominators being positive integers. Divide $ s_1$ and $ s_2$ by their greatest common divisor $ c$ and obtain $ a_1$ and $ a_2$, respectively. Similarily, divide $ t_1$ and $ t_2$ by their greatest common divisor $ d$ and obtain $ b_1$ and $ b_2$, respectively. After that, form a new fraction $ \frac{a_1b_2 \plus{} a_2b_1}{t_1b_2}$, reduce it, and multiply the numerator of the result by $ c$. Martin claims that this algorithm always finds the sum of the original fractions as an irreducible fraction. Is his claim correct?
Sophia writes an algorithm to solve the graph isomorphism problem. Given a graph $G=(V,E)$, her algorithm iterates through all permutations of the set $\{v_1, \dots, v_{|V|}\}$, each time examining all ordered pairs $(v_i,v_j)\in V\times V$ to see if an edge exists. When $|V|=8$, her algorithm makes $N$ such examinations. What is the largest power of two that divides $N$?
An integer $N \ge 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold:
($1$) no one stands between the two tallest players,
($2$) no one stands between the third and fourth tallest players,
$\;\;\vdots$
($N$) no one stands between the two shortest players.
Show that this is always possible.
[i]Proposed by Grigory Chelnokov, Russia[/i]
We have a machine that has an input and an output. The input is a letter from the finite set $I$ and the output is a lamp that at each moment has one of the colors of the set $C=\{c_1,\dots,c_p\}$.
At each moment the machine has an inner state that is one of the $n$ members of finite set $S$. The function $o: S \rightarrow C$ is a surjective function defining that at each state, what color must the lamp be, and the function $t:S \times I \rightarrow S$ is a function defining how does giving each input at each state changes the state. We only shall see the lamp and we have no direct information from the state of the car at current moment.
In other words a machine is $M=(S,I,C,o,t)$ such that $S,I,C$ are finite, $t:S \times I \rightarrow S$ , and $o:S \rightarrow C$ is surjective. It is guaranteed that for each two different inner states, there's a sequence of inputs such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state.
(a) The machine $M$ has $n$ different inner states. Prove that for each two different inner states, there's a sequence of inputs of length no more than $n-p$ such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state.
(b) Prove that for a machine $M$ with $n$ different inner states, there exists an algorithm with no more than $n^2$ inputs that starting at any unknown inner state, at the end of the algorithm the state of the machine at that moment is known.
Can you prove the above claim for $\frac{n^2}{2}$?
Let $n > 1$ be an integer. In a circular arrangement of $n$ lamps $L_0, \ldots, L_{n-1},$ each of of which can either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, $Step_0, Step_1, \ldots .$ If $L_{j-1}$ ($j$ is taken mod $n$) is ON then $Step_j$ changes the state of $L_j$ (it goes from ON to OFF or from OFF to ON) but does not change the state of any of the other lamps. If $L_{j-1}$ is OFF then $Step_j$ does not change anything at all. Show that:
(i) There is a positive integer $M(n)$ such that after $M(n)$ steps all lamps are ON again,
(ii) If $n$ has the form $2^k$ then all the lamps are ON after $n^2-1$ steps,
(iii) If $n$ has the form $2^k + 1$ then all lamps are ON after $n^2 - n + 1$ steps.
Suppose that $n$ people $A_1$, $A_2$, $\ldots$, $A_n$, ($n \geq 3$) are seated in a circle and that $A_i$ has $a_i$ objects such that
\[ a_1 + a_2 + \cdots + a_n = nN \]
where $N$ is a positive integer. In order that each person has the same number of objects, each person $A_i$ is to give or to receive a certain number of objects to or from its two neighbours $A_{i-1}$ and $A_{i+1}$. (Here $A_{n+1}$ means $A_1$ and $A_n$ means $A_0$.) How should this redistribution be performed so that the total number of objects transferred is minimum?
On a blackboard there are $ n \geq 2, n \in \mathbb{Z}^{\plus{}}$ numbers. In each step we select two numbers from the blackboard and replace both of them by their sum. Determine all numbers $ n$ for which it is possible to yield $ n$ identical number after a finite number of steps.
Let $ \theta$ be an angle in the interval $ (0,\pi/2)$. Given that $ \cos \theta$ is irrational, and that $ \cos k \theta$ and $ \cos[(k \plus{} 1)\theta ]$ are both rational for some positive integer $ k$, show that $ \theta \equal{} \pi/6$.
For a polynomial $ P(x)$ with integer coefficients, $ r(2i \minus{} 1)$ (for $ i \equal{} 1,2,3,\ldots,512$) is the remainder obtained when $ P(2i \minus{} 1)$ is divided by $ 1024$. The sequence
\[ (r(1),r(3),\ldots,r(1023))
\]
is called the [i]remainder sequence[/i] of $ P(x)$. A remainder sequence is called [i]complete[/i] if it is a permutation of $ (1,3,5,\ldots,1023)$. Prove that there are no more than $ 2^{35}$ different complete remainder sequences.
Let $n$ be an integer greater than 2. A positive integer is said to be [i]attainable [/i]if it is 1 or can be obtained from 1 by a sequence of operations with the following properties:
1.) The first operation is either addition or multiplication.
2.) Thereafter, additions and multiplications are used alternately.
3.) In each addition, one can choose independently whether to add 2 or $n$
4.) In each multiplication, one can choose independently whether to multiply by 2 or by $n$.
A positive integer which cannot be so obtained is said to be [i]unattainable[/i].
[b]a.)[/b] Prove that if $n\geq 9$, there are infinitely many unattainable positive integers.
[b]b.)[/b] Prove that if $n=3$, all positive integers except 7 are attainable.
Let $c$ be a nonnegative integer, and define $a_n = n^2 + c$ (for $n \geq 1)$. Define $d_n$ as the greatest common divisor of $a_n$ and $a_{n + 1}$.
(a) Suppose that $c = 0$. Show that $d_n = 1,\ \forall n \geq 1$.
(b) Suppose that $c = 1$. Show that $d_n \in \{1,5\},\ \forall n \geq 1$.
(c) Show that $d_n \leq 4c + 1,\ \forall n \geq 1$.