Olympiad problems

2014 Belarus Team Selection Test, 3

Find the maximum possible number of edges of a simple graph with $8$ vertices and without any quadrilateral. (a simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.)

1970 IMO Longlists, 33

Tags: geometry , perimeter , combinatorics unsolved , combinatorics

The vertices of a given square are clockwise lettered $A,B,C,D$. On the side $AB$ is situated a point $E$ such that $AE = AB/3$. Starting from an arbitrarily chosen point $P_0$ on segment $AE$ and going clockwise around the perimeter of the square, a series of points $P_0, P_1, P_2, \ldots$ is marked on the perimeter such that $P_iP_{i+1} = AB/3$ for each $i$. It will be clear that when $P_0$ is chosen in $A$ or in $E$, then some $P_i$ will coincide with $P_0$. Does this possibly also happen if $P_0$ is chosen otherwise?

2014 Postal Coaching, 2

Tags: combinatorics unsolved , combinatorics

Fix positive integers $n,j,k$.How many integer sequences are there of the form $1\le a_1<a_2<\ldots<a_k\le n$,where $a_{i+1}-a_i\ge j$ for all $1\le i\le k-1$.

1995 Turkey MO (2nd round), 5

Tags: induction , combinatorics unsolved , combinatorics

Let $t(A)$ denote the sum of elements of a nonempty set $A$ of integers, and define $t(\emptyset)=0$. Find a set $X$ of positive integers such that for every integers $k$ there is a unique ordered pair of disjoint subsets $(A_{k},B_{k})$ of $X$ such that $t(A_{k})-t(B_{k}) = k$.

2006 South africa National Olympiad, 5

Tags: Pascal's Triangle , combinatorics unsolved , combinatorics

Find the number of subsets $X$ of $\{1,2,\dots,10\}$ such that $X$ contains at least two elements and such that no two elements of $X$ differ by $1$.

1994 China Team Selection Test, 3

Tags: symmetry , geometry , geometric transformation , reflection , trapezoid , combinatorics unsolved , combinatorics

Find the smallest $n \in \mathbb{N}$ such that if any 5 vertices of a regular $n$-gon are colored red, there exists a line of symmetry $l$ of the $n$-gon such that every red point is reflected across $l$ to a non-red point.

1993 China Team Selection Test, 3

Tags: graph theory , combinatorics unsolved , combinatorics

A graph $G=(V,E)$ is given. If at least $n$ colors are required to paints its vertices so that between any two same colored vertices no edge is connected, then call this graph ''$n-$colored''. Prove that for any $n \in \mathbb{N}$, there is a $n-$colored graph without triangles.

2007 India IMO Training Camp, 3

Tags: Putnam , absolute value , combinatorics unsolved , combinatorics

Given a finite string $S$ of symbols $X$ and $O$, we denote $\Delta(s)$ as the number of$X'$s in $S$ minus the number of $O'$s (For example, $\Delta(XOOXOOX)=-1$). We call a string $S$ [b]balanced[/b] if every sub-string $T$ of (consecutive symbols) $S$ has the property $-1\leq \Delta(T)\leq 2.$ (Thus $XOOXOOX$ is not balanced, since it contains the sub-string $OOXOO$ whose $\Delta$ value is $-3.$ Find, with proof, the number of balanced strings of length $n$.

2003 China Team Selection Test, 3

Tags: modular arithmetic , combinatorics unsolved , combinatorics

There is a frog in every vertex of a regular 2n-gon with circumcircle($n \geq 2$). At certain time, all frogs jump to the neighborhood vertices simultaneously (There can be more than one frog in one vertex). We call it as $\textsl{a way of jump}$. It turns out that there is $\textsl{a way of jump}$ with respect to 2n-gon, such that the line connecting any two distinct vertice having frogs on it after the jump, does not pass through the circumcentre of the 2n-gon. Find all possible values of $n$.

2011 Tuymaada Olympiad, 1

Tags: combinatorics unsolved , combinatorics

Red, blue, and green children are arranged in a circle. When a teacher asked the red children that have a green neighbor to raise their hands, $20$ children raised their hands. When she asked the blue children that have a green neighbor to raise their hands, $25$ children raised their hands. Prove that some child that raised her hand had two green neighbors.

2007 Vietnam National Olympiad, 1

Tags: combinatorics unsolved , combinatorics

Given a regular 2007-gon. Find the minimal number $k$ such that: Among every $k$ vertexes of the polygon, there always exists 4 vertexes forming a convex quadrilateral such that 3 sides of the quadrilateral are also sides of the polygon.

1989 IMO Longlists, 39

Tags: function , algebra , polynomial , calculus , integration , combinatorics unsolved , combinatorics

Alice has two urns. Each urn contains four balls and on each ball a natural number is written. She draws one ball from each urn at random, notes the sum of the numbers written on them, and replaces the balls in the urns from which she took them. This she repeats a large number of times. Bill, on examining the numbers recorded, notices that the frequency with which each sum occurs is the same as if it were the sum of two natural numbers drawn at random from the range 1 to 4. What can he deduce about the numbers on the balls?

1997 China Team Selection Test, 2

Tags: combinatorics unsolved , combinatorics

There are $ n$ football teams in a round-robin competition where every 2 teams meet once. The winner of each match receives 3 points while the loser receives 0 points. In the case of a draw, both teams receive 1 point each. Let $ k$ be as follows: $ 2 \leq k \leq n \minus{} 1$. At least how many points must a certain team get in the competition so as to ensure that there are at most $ k \minus{} 1$ teams whose scores are not less than that particular team's score?

2005 CHKMO, 4

Tags: function , number theory , prime numbers , combinatorics unsolved , combinatorics

Let $S=\{1,2,...,100\}$ . Find number of functions $f: S\to S$ satisfying the following conditions a)$f(1)=1$ b)$f$ is bijective c)$f(n)=f(g(n))f(h(n))\forall n\in S$, where $g(n),h(n)$ are positive integer numbers such that $g(n)\leq h(n),n=g(n)h(n)$ that minimize $h(n)-g(n)$.

2010 Tuymaada Olympiad, 4

Tags: combinatorics unsolved , combinatorics , invariant

On a blackboard there are $2010$ natural nonzero numbers. We define a "move" by erasing $x$ and $y$ with $y\neq0$ and replacing them with $2x+1$ and $y-1$, or we can choose to replace them by $2x+1$ and $\frac{y-1}{4}$ if $y-1$ is divisible by 4. Knowing that in the beginning the numbers $2006$ and $2008$ have been erased, show that the original set of numbers cannot be attained again by any sequence of moves.

1989 IMO Longlists, 44

Tags: combinatorics unsolved , combinatorics

Given two distinct numbers $ b_1$ and $ b_2$, their product can be formed in two ways: $ b_1 \times b_2$ and $ b_2 \times b_1.$ Given three distinct numbers, $ b_1, b_2, b_3,$ their product can be formed in twelve ways: $ b_1\times(b_2 \times b_3);$ $ (b_1 \times b_2) \times b_3;$ $ b_1 \times (b_3 \times b_2);$ $ (b_1 \times b_3) \times b_2;$ $ b_2 \times (b_1 \times b_3);$ $ (b_2 \times b_1) \times b_3;$ $ b_2 \times(b_3 \times b_1);$ $ (b_2 \times b_3)\times b_1;$ $ b_3 \times(b_1 \times b_2);$ $ (b_3 \times b_1)\times b_2;$ $ b_3 \times(b_2 \times b_1);$ $ (b_3 \times b_2) \times b_1.$ In how many ways can the product of $ n$ distinct letters be formed?

1994 Hungary-Israel Binational, 4

Tags: group theory , abstract algebra , pigeonhole principle , combinatorics unsolved , combinatorics

An [i]$ n\minus{}m$ society[/i] is a group of $ n$ girls and $ m$ boys. Prove that there exists numbers $ n_0$ and $ m_0$ such that every [i]$ n_0\minus{}m_0$ society[/i] contains a subgroup of five boys and five girls with the following property: either all of the boys know all of the girls or none of the boys knows none of the girls.

2014 Iran Team Selection Test, 3

Tags: LaTeX , combinatorics unsolved , combinatorics

we named a $n*n$ table $selfish$ if we number the row and column with $0,1,2,3,...,n-1$.(from left to right an from up to down) for every {$ i,j\in{0,1,2,...,n-1}$} the number of cell $(i,j)$ is equal to the number of number $i$ in the row $j$. for example we have such table for $n=5$ 1 0 3 3 4 1 3 2 1 1 0 1 0 1 0 2 1 0 0 0 1 0 0 0 0 prove that for $n>5$ there is no $selfish$ table

2002 Brazil National Olympiad, 4

Tags: combinatorics unsolved , combinatorics

For any non-empty subset $A$ of $\{1, 2, \ldots , n\}$ define $f(A)$ as the largest element of $A$ minus the smallest element of $A$. Find $\sum f(A)$ where the sum is taken over all non-empty subsets of $\{1, 2, \ldots , n\}$.

1990 China Team Selection Test, 1

Tags: induction , combinatorics unsolved , combinatorics

In a wagon, every $m \geq 3$ people have exactly one common friend. (When $A$ is $B$'s friend, $B$ is also $A$'s friend. No one was considered as his own friend.) Find the number of friends of the person who has the most friends.

2002 China Team Selection Test, 3

Tags: combinatorics unsolved , combinatorics

There is a game. The magician let the participant think up a positive integer (at least two digits). For example, an integer $ \displaystyle\overline{a_1a_2 \cdots a_n}$ is rearranged as $ \overline{a_{i_1}a_{i_2} \cdots a_{i_n}}$, that is, $ i_1, i_2, \cdots, i_n$ is a permutation of $ 1,2, \cdots, n$. Then we get $ n!\minus{}1$ integers. The participant is asked to calculate the sum of the $ n!\minus{}1$ numbers, then tell the magician the sum $ S$. The magician claims to be able to know the original number when he is told the sum $ S$. Try to decide whether the magician can be successful or not.

2010 Tuymaada Olympiad, 3

Tags: combinatorics unsolved , combinatorics

Arranged in a circle are $2010$ digits, each of them equal to $1$, $2$, or $3$. For each positive integer $k$, it's known that in any block of $3k$ consecutive digits, each of the digits appears at most $k+10$ times. Prove that there is a block of several consecutive digits with the same number of $1$s, $2$s, and $3$s.

1995 Dutch Mathematical Olympiad, 5

Tags: combinatorics unsolved , combinatorics

An array $ (a_1,a_2,...,a_{13})$ of $ 13$ integers is called $ tame$ if for each $ 1 \le i \le 13$ the following condition holds: If $ a_i$ is left out, the remaining twelve integers can be divided into two groups with the same sum of elements. A tame array is called $ turbo$ $ tame$ if the remaining twelve numbers can always be divided in two groups of six numbers having the same sum. $ (a)$ Give an example of a tame array of $ 13$ integers (not all equal). $ (b)$ Prove that in a tame array all numbers are of the same parity. $ (c)$ Prove that in a turbo tame array all numbers are equal.

2014 India Regional Mathematical Olympiad, 4

Tags: combinatorics unsolved , combinatorics

Is it possible to write the numbers $17$,$18$,$19$,...$32$ in a $4*4$ grid of unit squares with one number in each square such that if the grid is divided into four $2*2$ subgrids of unit squares ,then the product of numbers in each of the subgrids divisible by $16$?

1979 IMO Longlists, 58

Tags: combinatorics unsolved , combinatorics

Prove that there exists a $k_0\in\mathbb{N}$ such that for every $k\in\mathbb{N},k>k_0$, there exists a finite number of lines in the plane not all parallel to one of them, that divide the plane exactly in $k$ regions. Find $k_0$.