Found problems: 1488
1991 China Team Selection Test, 2
For $i = 1,2, \ldots, 1991$, we choose $n_i$ points and write number $i$ on them (each point has only written one number on it). A set of chords are drawn such that:
(i) They are pairwise non-intersecting.
(ii) The endpoints of each chord have distinct numbers.
If for all possible assignments of numbers the operation can always be done, find the necessary and sufficient condition the numbers $n_1, n_2, \ldots, n_{1991}$ must satisfy for this to be possible.
Oliforum Contest I 2008, 3
Let $ 0 < a_1 < a_2 < a_3 < ... < a_{10000} < 20000$ be integers such that $ gcd(a_i,a_j) < a_i, \forall i < j$ ; is $ 500 < a_1$ [i](always)[/i] true ?
[i](own)[/i] :lol:
1996 China Team Selection Test, 1
3 countries $A, B, C$ participate in a competition where each country has 9 representatives. The rules are as follows: every round of competition is between 1 competitor each from 2 countries. The winner plays in the next round, while the loser is knocked out. The remaining country will then send a representative to take on the winner of the previous round. The competition begins with $A$ and $B$ sending a competitor each. If all competitors from one country have been knocked out, the competition continues between the remaining 2 countries until another country is knocked out. The remaining team is the champion.
[b]I.[/b] At least how many games does the champion team win?
[b]II.[/b] If the champion team won 11 matches, at least how many matches were played?
2009 Tuymaada Olympiad, 1
All squares of a $ 20\times 20$ table are empty. Misha* and Sasha** in turn put chips in free squares (Misha* begins). The player after whose move there are four chips on the intersection of two rows and two columns wins. Which of the players has a winning strategy?
[i]Proposed by A. Golovanov[/i]
[b]US Name Conversions: [/b]
[i]Misha*: Naoki
Sasha**: Richard[/i]
2010 Bulgaria National Olympiad, 3
Let $a_0, a_1, \ldots, a_9$ and $b_1 , b_2, \ldots,b_9$ be positive integers such that $a_9<b_9$ and $a_k \neq b_k, 1 \leq k \leq 8.$ In a cash dispenser/automated teller machine/ATM there are $n\geq a_9$ levs (Bulgarian national currency) and for each $1 \leq i \leq 9$ we can take $a_i$ levs from the ATM (if in the bank there are at least $a_i$ levs). Immediately after that action the bank puts $b_i$ levs in the ATM or we take $a_0$ levs. If we take $a_0$ levs from the ATM the bank doesn’t put any money in the ATM. Find all possible positive integer values of $n$ such that after finite number of takings money from the ATM there will be no money in it.
2008 USA Team Selection Test, 3
For a pair $ A \equal{} (x_1, y_1)$ and $ B \equal{} (x_2, y_2)$ of points on the coordinate plane, let $ d(A,B) \equal{} |x_1 \minus{} x_2| \plus{} |y_1 \minus{} y_2|$. We call a pair $ (A,B)$ of (unordered) points [i]harmonic[/i] if $ 1 < d(A,B) \leq 2$. Determine the maximum number of harmonic pairs among 100 points in the plane.
2014 Contests, 1
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
2000 IberoAmerican, 1
A regular polygon of $ n$ sides ($ n\geq3$) has its vertex numbered from 1 to $ n$. One draws all the diagonals of the polygon. Show that if $ n$ is odd, it is possible to assign to each side and to each diagonal an integer number between 1 and $ n$, such that the next two conditions are simultaneously satisfied:
(a) The number assigned to each side or diagonal is different to the number assigned to any of the vertices that is endpoint of it.
(b) For each vertex, all the sides and diagonals that have it as an endpoint, have different number assigned.
2010 Contests, 1
Misha and Sahsa play a game on a $100\times 100$ chessboard. First, Sasha places $50$ kings on the board, and Misha places a rook, and then they move in turns, as following (Sasha begins):
At his move, Sasha moves each of the kings one square in any direction, and Misha can move the rook on the horizontal or vertical any number of squares. The kings cannot be captured or stepped over. Sasha's purpose is to capture the rook, and Misha's is to avoid capture.
Is there a winning strategy available for Sasha?
2009 Finnish National High School Mathematics Competition, 5
As in the picture below, the rectangle on the left hand side has been divided into four parts by line segments which are parallel to a side of the rectangle. The areas of the small rectangles are $A,B,C$ and $D$. Similarly, the small rectangles on the right hand side have areas $A^\prime,B^\prime,C^\prime$ and $D^\prime$. It is known that $A\leq A^\prime$, $B\leq B^\prime$, $C\leq C^\prime$ but $D\leq B^\prime$.
[asy]
import graph; size(12cm); real lsf=0.5; pen dps=linewidth(0.7)+fontsize(10); defaultpen(dps); pen ds=black; real xmin=-4.3,xmax=12.32,ymin=-10.68,ymax=6.3;
draw((0,3)--(0,0)); draw((3,0)--(0,0)); draw((3,0)--(3,3)); draw((0,3)--(3,3)); draw((2,0)--(2,3)); draw((0,2)--(3,2)); label("$A$",(0.86,2.72),SE*lsf); label("$B$",(2.38,2.7),SE*lsf); label("$C$",(2.3,1.1),SE*lsf); label("$D$",(0.82,1.14),SE*lsf); draw((5,2)--(11,2)); draw((5,2)--(5,0)); draw((11,0)--(5,0)); draw((11,2)--(11,0)); draw((8,0)--(8,2)); draw((5,1)--(11,1)); label("$A'$",(6.28,1.8),SE*lsf); label("$B'$",(9.44,1.82),SE*lsf); label("$C'$",(9.4,0.8),SE*lsf); label("$D'$",(6.3,0.86),SE*lsf);
dot((0,3),linewidth(1pt)+ds); dot((0,0),linewidth(1pt)+ds); dot((3,0),linewidth(1pt)+ds); dot((3,3),linewidth(1pt)+ds); dot((2,0),linewidth(1pt)+ds); dot((2,3),linewidth(1pt)+ds); dot((0,2),linewidth(1pt)+ds); dot((3,2),linewidth(1pt)+ds); dot((5,0),linewidth(1pt)+ds); dot((5,2),linewidth(1pt)+ds); dot((11,0),linewidth(1pt)+ds); dot((11,2),linewidth(1pt)+ds); dot((8,0),linewidth(1pt)+ds); dot((8,2),linewidth(1pt)+ds); dot((5,1),linewidth(1pt)+ds); dot((11,1),linewidth(1pt)+ds);
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
[/asy]
Prove that the big rectangle on the left hand side has area smaller or equal to the area of the big rectangle on the right hand side, i.e. $A+B+C+D\leq A^\prime+B^\prime+C^\prime+D^\prime$.
2005 Hong kong National Olympiad, 1
On a planet there are $3\times2005!$ aliens and $2005$ languages. Each pair of aliens communicates with each other in exactly one language. Show that there are $3$ aliens who communicate with each other in one common language.
1996 Kurschak Competition, 2
Two countries ($A$ and $B$) organize a conference, and they send an equal number of participants. Some of them have known each other from a previous conference. Prove that one can choose a nonempty subset $C$ of the participants from $A$ such that one of the following holds:
[list][*]the participants from $B$ each know an even number of people in $C$,
[*]the participants from $B$ each know an odd number of participants in $C$.[/list]
2010 Greece Team Selection Test, 2
In a blackboard there are $K$ circles in a row such that one of the numbers $1,...,K$ is assigned to each circle from the left to the right.
Change of situation of a circle is to write in it or erase the number which is assigned to it.At the beginning no number is written in its own circle.
For every positive divisor $d$ of $K$ ,$1\leq d\leq K$ we change the situation of the circles in which their assigned numbers are divisible by $d$,performing for each divisor $d$ $K$ changes of situation.
Determine the value of $K$ for which the following holds;when this procedure is applied once for all positive divisors of $K$ ,then all numbers $1,2,3,...,K$ are written in the circles they were assigned in.
2002 Taiwan National Olympiad, 2
A lattice point $X$ in the plane is said to be [i]visible[/i] from the origin $O$ if the line segment $OX$ does not contain any other lattice points. Show that for any positive integer $n$, there is square $ABCD$ of area $n^{2}$ such that none of the lattice points inside the square is visible from the origin.
2012 Postal Coaching, 4
Choose arbitrarily $n$ vertices of a regular $2n-$gon and colour them red. The remaining vertices are coloured blue. We arrange all red-red distances into a nondecreasing sequence and do the same with the blue-blue distances. Prove that the two sequences thus obtained are identical.
2012 China Second Round Olympiad, 8
There are $4$ distinct codes used in an intelligence station, one of them applied in each week. No two codes used in two adjacent weeks are the same code. Knowing that code $A$ is used in the first week, find the probability that code $A$ is used in the seventh week.
2001 Vietnam Team Selection Test, 3
Some club has 42 members. It’s known that among 31 arbitrary club members, we can find one pair of a boy and a girl that they know each other. Show that from club members we can choose 12 pairs of knowing each other boys and girls.
1994 All-Russian Olympiad, 8
There are $30$ students in a class. In an examination, their results were all different from each other. It is given that everyone has the same number of friends. Find the maximum number of students such that each one of them has a better result than the majority of his friends.
PS. Here majority means larger than half.
2010 Postal Coaching, 6
Let $n > 1$ be an integer.
A set $S \subseteq \{ 0, 1, 2, \cdots , 4n - 1 \}$ is called ’sparse’ if for any $k \in \{ 0, 1, 2, \cdots , n - 1 \}$ the following two conditions are satisfied:
$(a)$ The set $S \cap \{4k - 2, 4k - 1, 4k, 4k + 1, 4k + 2 \}$ has at most two elements;
$(b)$ The set $S \cap \{ 4k +1, 4k +2, 4k +3 \}$ has at most one element.
Prove that there are exactly $8 \cdot 7^{n-1}$ sparse subsets.
2006 Greece National Olympiad, 1
How many 5 digit positive integers are there such that each of its digits, except for the last one, is greater than or equal to the next digit?
2012 Indonesia TST, 2
Let $P_1, P_2, \ldots, P_n$ be distinct $2$-element subsets of $\{1, 2, \ldots, n\}$. Suppose that for every $1 \le i < j \le n$, if $P_i \cap P_j \neq \emptyset$, then there is some $k$ such that $P_k = \{i, j\}$. Prove that if $a \in P_i$ for some $i$, then $a \in P_j$ for exactly one value of $j$ not equal to $i$.
2014 Contests, 2
Define a [i]domino[/i] to be an ordered pair of [i]distinct[/i] positive integers. A [i]proper sequence[/i] of dominoes is a list of distinct dominoes in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i, j)$ and $(j, i)$ do not [i]both[/i] appear for any $i$ and $j$. Let $D_n$ be the set of all dominoes whose coordinates are no larger than $n$. Find the length of the longest proper sequence of dominoes that can be formed using the dominoes of $D_n$.
1991 China Team Selection Test, 3
All edges of a polyhedron are painted with red or yellow. For an angle of a facet, if the edges determining it are of different colors, then the angle is called [i]excentric[/i]. The[i] excentricity [/i]of a vertex $A$, namely $S_A$, is defined as the number of excentric angles it has. Prove that there exist two vertices $B$ and $C$ such that $S_B + S_C \leq 4$.
2006 MOP Homework, 5
For a triple $(m,n,r)$ of integers with $0 \le r \le n \le m-2$, define $p(m,n,r)=\sum^r_{k=0} (-1)^k \dbinom{m+n-2(k+1)}{n} \dbinom{r}{k}$. Prove that $p(m,n,r)$ is positive and that $\sum^n_{r=0} p(m,n,r)=\dbinom{m+n}{n}$.
2002 China Team Selection Test, 2
$ m$ and $ n$ are positive integers. In a $ 8 \times 8$ chessboard, $ (m,n)$ denotes the number of grids a Horse can jump in a chessboard ($ m$ horizontal $ n$ vertical or $ n$ horizontal $ m$ vertical ). If a $ (m,n) \textbf{Horse}$ starts from one grid, passes every grid once and only once, then we call this kind of Horse jump route a $ \textbf{H Route}$. For example, the $ (1,2) \textbf{Horse}$ has its $ \textbf{H Route}$. Find the smallest positive integer $ t$, such that from any grid of the chessboard, the $ (t,t\plus{}1) \textbf{Horse}$ does not has any $ \textbf{H Route}$.