Found problems: 247
Compute the sum of all positive real numbers $x \le 5$ satisfying $$x =\frac{ \lceil x^2 \rceil + \lceil x \rceil \cdot \lfloor x \rfloor}{ \lceil x\rceil + \lfloor x \rfloor}$$
[list]
[*] A power grid with the shape of a $3\times 3$ lattice with $16$ nodes (vertices of the lattice) joined by wires (along the sides of squares. It may have happened that some of the wires have burned out. In one test technician can choose any two nodes and check if electrical current circulates between them (i.e there is a chain of intact wires joining the chosen nodes) . Technicial knows that current will circulate from any node to another node. What is the least number of tests required to demonstrate this?
[*] Previous problem for the grid of $5\times 5$ lattice.[/list]
Let be a real number $ a. $ For any real number $ p $ and natural number $ k, $ let be the set
$$ A_k(p)=\{ px\in\mathbb{Z}\mid k=\lceil x \rceil \} . $$
Find all real numbers $ b $ such that $ \# A_n(a)=\# A_n(b) , $ for any natural number $ n. $
$ \# $ [i]denotes the cardinal.[/i]
[i]Eugen Păltânea[/i]
A network is a simple directed graph such that each edge $ e$ has two intger lower and upper capacities $ 0\leq c_l(e)\leq c_u(e)$. A circular flow on this graph is a function such that:
1) For each edge $ e$, $ c_l(e)\leq f(e)\leq c_u(e)$.
2) For each vertex $ v$: \[ \sum_{e\in v^\plus{}}f(e)\equal{}\sum_{e\in v^\minus{}}f(e)\]
a) Prove that this graph has a circular flow, if and only if for each partition $ X,Y$ of vertices of the network we have:
\[ \sum_{\begin{array}{c}{e\equal{}xy}\\{x\in X,y\in Y}\end{array}} c_l(e)\leq \sum_{\begin{array}{c}{e\equal{}yx}\\{y\in Y,x\in X}\end{array}} c_l(e)\]
b) Suppose that $ f$ is a circular flow in this network. Prove that there exists a circular flow $ g$ in this network such that $ g(e)\equal{}\lfloor f(e)\rfloor$ or $ g(e)\equal{}\lceil f(e)\rceil$ for each edge $ e$.
We have $n$ bags each having $100$ coins. All of the bags have $10$ gram coins except one of them which has $9$ gram coins. We have a balance which can show weights of things that have weight of at most $1$ kilogram. At least how many times shall we use the balance in order to find the different bag?
[i]Proposed By Hamidreza Ziarati[/i]
Given $a_0 > 1$, the sequence $a_0, a_1, a_2, ...$ is such that for all $k > 0$, $a_k$ is the smallest integer greater than $a_{k-1}$ which is relatively prime to all the earlier terms in the sequence.
Find all $a_0$ for which all terms of the sequence are primes or prime powers.
Let $ n,k$ be given positive integers satisfying $ k\le 2n \minus{} 1$. On a table tennis tournament $ 2n$ players take part, they play a total of $ k$ rounds match, each round is divided into $ n$ groups, each group two players match. The two players in different rounds can match on many occasions. Find the greatest positive integer $ m \equal{} f(n,k)$ such that no matter how the tournament processes, we always find $ m$ players each of pair of which didn't match each other.
Bored in an infinitely long class, Evan jots down a fraction whose numerator and denominator are both $70$-character strings, as follows:
\[ r = \frac{loooloolloolloololllloloollollolllloollloloolooololooolololooooollllol}
{lolooloolollollolloooooloooloololloolllooollololoooollllooolollloloool}. \]
If $o=2013$ and $l=\frac{1}{50}$, find $\lceil roll \rceil$.
[i]Proposed by Evan Chen[/i]
Let $n$ be a positive integer. Daniel and Merlijn are playing a game. Daniel
has $k$ sheets of paper lying next to each other on a table, where $k$ is a
positive integer. On each of the sheets, he writes some of the numbers
from $1$ up to $n$ (he is allowed to write no number at all, or all numbers).
On the back of each of the sheets, he writes down the remaining numbers.
Once Daniel is finished, Merlijn can flip some of the sheets of paper (he is
allowed to flip no sheet at all, or all sheets). If Merlijn succeeds in making
all of the numbers from $1$ up to n visible at least once, then he wins.
Determine the smallest $k$ for which Merlijn can always win, regardless of
Daniel’s actions.
Determine whether it's possible to cover a $K_{2012}$ with
a) 1000 $K_{1006}$'s;
b) 1000 $K_{1006,1006}$'s.
[i]David Yang.[/i]
Suppose $A\subset \{(a_1,a_2,\dots,a_n)\mid a_i\in \mathbb{R},i=1,2\dots,n\}$. For any $\alpha=(a_1,a_2,\dots,a_n)\in A$ and $\beta=(b_1,b_2,\dots,b_n)\in A$, we define
\[ \gamma(\alpha,\beta)=(|a_1-b_1|,|a_2-b_2|,\dots,|a_n-b_n|), \] \[ D(A)=\{\gamma(\alpha,\beta)\mid\alpha,\beta\in A\}. \] Please show that $|D(A)|\geq |A|$.
There is a sequence with $a(2)=0$, $a(3)=1$ and $a(n)=a\left(\left\lfloor\dfrac n2\right\rfloor\right)+a\left(\left\lceil\dfrac n2\right\rceil\right)$ for $n\geq 4$. Find $a(2014)$. [Note that $\left\lfloor\dfrac n2\right\rfloor$ and $\left\lceil\dfrac n2\right\rceil$ denote the floor function (largest integer $\leq\tfrac n2$) and the ceiling function (smallest integer $\geq\tfrac n2$), respectively.]
Let $S$ be a set of 100 integers. Suppose that for all positive integers $x$ and $y$ (possibly equal) such that $x + y$ is in $S$, either $x$ or $y$ (or both) is in $S$. Prove that the sum of the numbers in $S$ is at most 10,000.
Let $P(x)$ be a polynomial with real coefficients. Prove that there exist positive integers $n$ and $k$ such that $k$ has $n$ digits and more than $P(n)$ positive divisors.
Let $n$ be a positive integer. Let $\mathcal{F}$ be a family of sets that contains more than half of all subsets of an $n$-element set $X$. Prove that from $\mathcal{F}$ we can select $\lceil \log_2 n \rceil + 1$ sets that form a separating family on $X$, i.e., for any two distinct elements of $X$ there is a selected set containing exactly one of the two elements.
Moderator says: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=614827&hilit=Schweitzer+2014+separating
Let $a_1,a_2,\ldots,a_n,\ldots$ be any permutation of all positive integers. Prove that there exist infinitely many positive integers $i$ such that $\gcd(a_i,a_{i+1})\leq \frac{3}{4} i$.
Let $n$ be a positive integer. Consider a triangular array of nonnegative integers as follows: \[
\begin{array}{rccccccccc}
\text{Row } 1: &&&&& a_{0,1} &&&& \smallskip\\
\text{Row } 2: &&&& a_{0,2} && a_{1,2} &&& \smallskip\\
&&& \vdots && \vdots && \vdots && \smallskip\\
\text{Row } n-1: && a_{0,n-1} && a_{1,n-1} && \cdots && a_{n-2,n-1} & \smallskip\\
\text{Row } n: & a_{0,n} && a_{1,n} && a_{2,n} && \cdots && a_{n-1,n}
\end{array}
\] Call such a triangular array [i]stable[/i] if for every $0 \le i < j < k \le n$ we have \[ a_{i,j} + a_{j,k} \le a_{i,k} \le a_{i,j} + a_{j,k} + 1. \] For $s_1, \ldots s_n$ any nondecreasing sequence of nonnegative integers, prove that there exists a unique stable triangular array such that the sum of all of the entries in row $k$ is equal to $s_k$.
An island has $10$ cities, where some of the possible pairs of cities are connected by roads. A [i]tour route[/i] is a route starting from a city, passing exactly eight out of the other nine cities exactly once each, and returning to the starting city. (In other words, it is a loop that passes only nine cities instead of all ten cities.) For each city, there exists a tour route that doesn't pass the given city. Find the minimum number of roads on the island.
A positive integer given in decimal representation $\overline{ a_na_{n-1} \ldots a_1a_0 }$ is called [i]monotone[/i] if $a_n\leq a_{n-1} \leq \cdots \leq a_0$. Determine the number of monotone positive integers with at most 1993 digits.
Determine whether there exists a polynomial $f(x_1, x_2)$ with two variables, with integer coefficients, and two points $A=(a_1, a_2)$ and $B=(b_1, b_2)$ in the plane, satisfying the following conditions:
(i) $A$ is an integer point (i.e $a_1$ and $a_2$ are integers);
(ii) $|a_1-b_1|+|a_2-b_2|=2010$;
(iii) $f(n_1, n_2)>f(a_1, a_2)$ for all integer points $(n_1, n_2)$ in the plane other than $A$;
(iv) $f(x_1, x_2)>f(b_1, b_2)$ for all integer points $(x_1, x_2)$ in the plane other than $B$.
[i]Massimo Gobbino, Italy[/i]
Determine all positive real numbers $ a$ such that there exists a positive integer $ n$ and sets $ A_1, A_2, \ldots, A_n$ satisfying the following conditions:
(1) every set $ A_i$ has infinitely many elements;
(2) every pair of distinct sets $ A_i$ and $ A_j$ do not share any common element
(3) the union of sets $ A_1, A_2, \ldots, A_n$ is the set of all integers;
(4) for every set $ A_i,$ the positive difference of any pair of elements in $ A_i$ is at least $ a^i.$
Given an integer $ m\geq 2$, and two real numbers $ a,b$ with $ a > 0$ and $ b\neq 0$. The sequence $ \{x_n\}$ is such that $ x_1 \equal{} b$ and $ x_{n \plus{} 1} \equal{} ax^{m}_{n} \plus{} b$, $ n \equal{} 1,2,...$. Prove that
(1)when $ b < 0$ and m is even, the sequence is bounded if and only if $ ab^{m \minus{} 1}\geq \minus{} 2$;
(2)when $ b < 0$ and m is odd, or when $ b > 0$ the sequence is bounded if and only if $ ab^{m \minus{} 1}\geq\frac {(m \minus{} 1)^{m \minus{} 1}}{m^m}$.
A necklace consists of 100 blue and several red beads. It is known that every segment of the necklace containing 8 blue beads contain also at least 5 red beads. What minimum number of red beads can be in the necklace?
[i]Proposed by A. Golovanov[/i]
Let $P_1$ be a regular $n$-gon, where $n\in\mathbb{N}$. We construct $P_2$ as the regular $n$-gon whose vertices are the midpoints of the edges of $P_1$. Continuing analogously, we obtain regular $n$-gons $P_3,P_4,\ldots ,P_m$. For $m\ge n^2-n+1$, find the maximum number $k$ such that for any colouring of vertices of $P_1,\ldots ,P_m$ in $k$ colours there exists an isosceles trapezium $ABCD$ whose vertices $A,B,C,D$ have the same colour.
[i]Radu Ignat[/i]
Let $n$ be a positive integer. Determine the size of the largest subset of $\{ -n, -n+1, \dots, n-1, n\}$ which does not contain three elements $a$, $b$, $c$ (not necessarily distinct) satisfying $a+b+c=0$.