Found problems: 1488
2005 MOP Homework, 1
Let $X$ be a set with $n$ elements and $0 \le k \le n$. Let $a_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at least $k$ common components (where a common component of $f$ and g is an $x \in X$ such that $f(x) = g(x)$). Let $b_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at most $k$ common components.
(a) Show that $a_{n,k} \cdot b_{n,k-1} \le n!$.
(b) Let $p$ be prime, and find the exact value of $a_{p,2}$.
2002 Italy TST, 2
On a soccer tournament with $n\ge 3$ teams taking part, several matches are played in such a way that among any three teams, some two play a match.
$(a)$ If $n=7$, find the smallest number of matches that must be played.
$(b)$ Find the smallest number of matches in terms of $n$.
2001 Romania Team Selection Test, 4
Consider a convex polyhedron $P$ with vertices $V_1,\ldots ,V_p$. The distinct vertices $V_i$ and $V_j$ are called [i]neighbours[/i] if they belong to the same face of the polyhedron. To each vertex $V_k$ we assign a number $v_k(0)$, and construct inductively the sequence $v_k(n)\ (n\ge 0)$ as follows: $v_k(n+1)$ is the average of the $v_j(n)$ for all neighbours $V_j$ of $V_k$ . If all numbers $v_k(n)$ are integers, prove that there exists the positive integer $N$ such that all $v_k(n)$ are equal for $n\ge N$ .
2006 Bulgaria Team Selection Test, 3
[b]Problem 3.[/b] Let $n\geq 3$ is given natural number, and $M$ is the set of the first $n$ primes. For any nonempty subset $X$ of $M$ with $P(X)$ denote the product of its elements. Let $N$ be a set of the kind $\ds\frac{P(A)}{P(B)}$, $A\subset M, B\subset M, A\cap B=\emptyset$ such that the product of any 7 elements of $N$ is integer. What is the maximal number of elements of $N$?
[i]Alexandar Ivanov[/i]
1997 Polish MO Finals, 3
Given any $n$ points on a unit circle show that at most $\frac{n^2}{3}$ of the segments joining two points have length $> \sqrt{2}$.
2012 Kurschak Competition, 2
Denote by $E(n)$ the number of $1$'s in the binary representation of a positive integer $n$. Call $n$ [i]interesting[/i] if $E(n)$ divides $n$. Prove that
(a) there cannot be five consecutive interesting numbers, and
(b) there are infinitely many positive integers $n$ such that $n$, $n+1$ and $n+2$ are each interesting.
2014 Contests, 4
Square $ABCD$ is divided into $n^2$ equal small squares by lines parallel to its sides.A spider starts from $A$ and moving only rightward or upwards,tries to reach $C$.Every "movement" of the spider consists of $k$ steps rightward and $m$ steps upwards or $m$ steps rightward and $k$ steps upwards(it can follow any possible order for the steps of each "movement").The spider completes $l$ "movements" and afterwards it moves without limitation (it still moves rightwards and upwards only).If $n=m\cdot l$,find the number of the possible paths the spider can follow to reach $C$.Note that $n,m,k,l\in \mathbb{N^{*}}$ with $k<m$.
1991 Vietnam Team Selection Test, 3
Let a set $X$ be given which consists of $2 \cdot n$ distinct real numbers ($n \geq 3$). Consider a set $K$ consisting of some pairs $(x, y)$ of distinct numbers $x, y \in X$, satisfying the two conditions:
[b]I.[/b] If $(x, y) \in K$ then $(y, x) \not \in K$.
[b]II.[/b] Every number $x \in X$ belongs to at most 19 pairs of $K$.
Show that we can divide the set $X$ into 5 non-empty disjoint sets $X_1, X_2, X_3, X_4, X_5$ in such a way that for each $i = 1, 2, 3, 4, 5$ the number of pairs $(x, y) \in K$ where $x, y$ both belong to $X_i$ is not greater than $3 \cdot n$.
2025 Romania EGMO TST, P2
Prove that any finite set $H$ of lattice points on the plane has a subset $K$ with the following properties:
[list]
[*]any vertical or horizontal line in the plane cuts $K$ in at most $2$ points,
[*]any point of $H\setminus K$ is contained by a segment with endpoints from $K$.[/list]
2012 Indonesia TST, 2
Suppose $S$ is a subset of $\{1,2,3,\ldots,2012\}$. If $S$ has at least $1000$ elements, prove that $S$ contains two different elements $a,b$, where $b$ divides $2a$.
2006 China Team Selection Test, 1
Let $A$ be a non-empty subset of the set of all positive integers $N^*$. If any sufficient big positive integer can be expressed as the sum of $2$ elements in $A$(The two integers do not have to be different), then we call that $A$ is a divalent radical. For $x \geq 1$, let $A(x)$ be the set of all elements in $A$ that do not exceed $x$, prove that there exist a divalent radical $A$ and a constant number $C$ so that for every $x \geq 1$, there is always $\left| A(x) \right| \leq C \sqrt{x}$.
2011 Romania Team Selection Test, 3
Given a positive integer number $n$, determine the maximum number of edges a simple graph on $n$ vertices may have such that it contain no cycles of even length.
1997 Irish Math Olympiad, 4
Let $ S$ be the set of natural numbers $ n$ satisfying the following conditions:
$ (i)$ $ n$ has $ 1000$ digits,
$ (ii)$ all the digits of $ n$ are odd, and
$ (iii)$ any two adjacent digits of $ n$ differ by $ 2$.
Determine the number of elements of $ S$.
2012 Czech-Polish-Slovak Match, 2
City of Mar del Plata is a square shaped $WSEN$ land with $2(n + 1)$ streets that divides it into $n \times n$ blocks, where $n$ is an even number (the leading streets form the perimeter of the square). Each block has a dimension of $100 \times 100$ meters. All streets in Mar del Plata are one-way. The streets which are parallel and adjacent to each other are directed in opposite direction. Street $WS$ is driven in the direction from $W$ to $S$ and the street $WN$ travels from $W$ to $N$. A street cleaning car starts from point $W$. The driver wants to go to the point $E$ and in doing so, he must cross as much as possible roads. What is the length of the longest route he can go, if any $100$-meter stretch cannot be crossed more than once? (The figure shows a plan of the city for $n=6$ and one of the possible - but not the longest - routes of the street cleaning car. See http://goo.gl/maps/JAzD too.)
[img]http://s14.postimg.org/avfg7ygb5/CPS_2012_P5.jpg[/img]
1989 IMO Longlists, 49
Let $ t(n)$ for $ n \equal{} 3, 4, 5, \ldots,$ represent the number of distinct, incongruent, integer-sided triangles whose perimeter is $ n;$ e.g., $ t(3) \equal{} 1.$ Prove that
\[ t(2n\minus{}1) \minus{} t(2n) \equal{} \left[ \frac{6}{n} \right] \text{ or } \left[ \frac{6}{n} \plus{} 1 \right].\]
2009 Bosnia Herzegovina Team Selection Test, 1
Given an $1$ x $n$ table ($n\geq 2$), two players alternate the moves in which they write the signs + and - in the cells of the table. The first player always writes +, while the second always writes -. It is not allowed for two equal signs to appear in the adjacent cells. The player who can’t make a move loses the game. Which of the players has a winning strategy?
2013 Moldova Team Selection Test, 2
Let $a_n=1+n!(\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{n!})$ for any $n\in \mathbb{Z}^{+}$. Consider $a_n$ points in the plane,no $3$ of them collinear.The segments between any $2$ of them are colored in one of $n$ colors. Prove that among them there exist $3$ points forming a monochromatic triangle.
2004 Baltic Way, 13
The $25$ member states of the European Union set up a committee with the following rules:
1) the committee should meet daily;
2) at each meeting, at least one member should be represented;
3) at any two different meetings, a different set of member states should be represented;
4) at $n^{th}$ meeting, for every $k<n$, the set of states represented should include at least one state that was represented at the $k^{th}$ meeting.
For how many days can the committee have its meetings?
2016 SDMO (High School), 5
$3n-1$ points are given in the plane, no three are collinear. Prove that one can select $2n$ of them whose convex hull is not a triangle.
2006 MOP Homework, 5
Smallville is populated by unmarried men and women, some of which are acquainted. The two City Matchmakers know who is acquainted with whom. One day, one of the matchmakers claimed: "I can arrange it so that every red haired man will marry a woman with who he is acquainted." The other matchmaker claimed: "I can arrange it so that every blonde woman will marry a man with whom she is acquainted." An amateur mathematician overheard this conversation and said: "Then it can be arranged so that every red haired man will marry a woman with whom he is acquainted and at the same time very blonde woman will marry a man with who she is acquainted." Is the mathematician right?
2007 All-Russian Olympiad, 8
Given an undirected graph with $N$ vertices. For any set of $k$ vertices, where $1\le k\le N$, there are at most $2k-2$ edges, which join vertices of this set. Prove that the edges may be coloured in two colours so that each cycle contains edges of both colours. (Graph may contain multiple edges).
[i]I. Bogdanov, G. Chelnokov[/i]
2003 Tournament Of Towns, 1
Smallville is populated by unmarried men and women, some of them are acquainted. Two city’s matchmakers are aware of all acquaintances. Once, one of matchmakers claimed: “I could arrange that every brunette man would marry a woman he was acquainted with”. The other matchmaker claimed “I could arrange that every blonde woman would marry a man she was acquainted with”. An amateur mathematician overheard their conversation and said “Then both arrangements could be done at the same time! ” Is he right?
1998 All-Russian Olympiad, 5
We are given five watches which can be winded forward. What is the smallest sum of winding intervals which allows us to set them to the same time, no matter how they were set initially?
1999 China Team Selection Test, 3
For every permutation $ \tau$ of $ 1, 2, \ldots, 10$, $ \tau \equal{} (x_1, x_2, \ldots, x_{10})$, define $ S(\tau) \equal{} \sum_{k \equal{} 1}^{10} |2x_k \minus{} 3x_{k \minus{} 1}|$. Let $ x_{11} \equal{} x_1$. Find
[b]I.[/b] The maximum and minimum values of $ S(\tau)$.
[b]II.[/b] The number of $ \tau$ which lets $ S(\tau)$ attain its maximum.
[b]III.[/b] The number of $ \tau$ which lets $ S(\tau)$ attain its minimum.
2010 Contests, 1
For all natural $n$, an $n$-staircase is a figure consisting of unit squares, with one square in the first row, two squares in the second row, and so on, up to $n$ squares in the $n^{th}$ row, such that all the left-most squares in each row are aligned vertically.
Let $f(n)$ denote the minimum number of square tiles requires to tile the $n$-staircase, where the side lengths of the square tiles can be any natural number. e.g. $f(2)=3$ and $f(4)=7$.
(a) Find all $n$ such that $f(n)=n$.
(b) Find all $n$ such that $f(n) = n+1$.