Olympiad problems

2011 Kazakhstan National Olympiad, 3

In some cells of a rectangular table $m\times n (m, n> 1)$ is one checker. $Baby$ cut along the lines of the grid this table so that it is split into two equal parts, with the number of pieces on each side were the same. $Carlson$ changed the arrangement of checkers on the board (and on each side of the cage is still worth no more than one pieces). Prove that the $Baby$ may again cut the board into two equal parts containing an equal number of pieces

2003 China Team Selection Test, 2

Tags: quadratics , modular arithmetic , combinatorics unsolved , combinatorics

Suppose $A\subseteq \{0,1,\dots,29\}$. It satisfies that for any integer $k$ and any two members $a,b\in A$($a,b$ is allowed to be same), $a+b+30k$ is always not the product of two consecutive integers. Please find $A$ with largest possible cardinality.

2005 Tuymaada Olympiad, 5

Tags: combinatorics unsolved , combinatorics

You have $2$ columns of $11$ squares in the middle, in the right and in the left you have columns of $9$ squares (centered on the ones of $11$ squares), then columns of $7,5,3,1$ squares. (This is the way it was explained in the original thread, http://www.artofproblemsolving.com/Forum/viewtopic.php?t=44430 ; anyway, i think you can understand how it looks) Several rooks stand on the table and beat all the squares ( a rook beats the square it stands in, too). Prove that one can remove several rooks such that not more than $11$ rooks are left and still beat all the table. [i]Proposed by D. Rostovsky, based on folklore[/i]

2008 Brazil National Olympiad, 2

Tags: combinatorial geometry , combinatorics unsolved , combinatorics

Let $ S$ be a set of $ 6n$ points in a line. Choose randomly $ 4n$ of these points and paint them blue; the other $ 2n$ points are painted green. Prove that there exists a line segment that contains exactly $ 3n$ points from $ S$, $ 2n$ of them blue and $ n$ of them green.

2003 France Team Selection Test, 2

Tags: combinatorics unsolved , combinatorics

$10$ cities are connected by one-way air routes in a way so that each city can be reached from any other by several connected flights. Let $n$ be the smallest number of flights needed for a tourist to visit every city and return to the starting city. Clearly $n$ depends on the flight schedule. Find the largest $n$ and the corresponding flight schedule.

1996 Vietnam Team Selection Test, 1

Tags: geometry , rectangle , combinatorial geometry , area of a triangle , combinatorics unsolved , combinatorics

In the plane we are given $3 \cdot n$ points ($n>$1) no three collinear, and the distance between any two of them is $\leq 1$. Prove that we can construct $n$ pairwise disjoint triangles such that: The vertex set of these triangles are exactly the given 3n points and the sum of the area of these triangles $< 1/2$.

2010 Romania National Olympiad, 3

Tags: Ramsey Theory , combinatorics unsolved , combinatorics

In the plane are given $100$ points, such that no three of them are on the same line. The points are arranged in $10$ groups, any group containing at least $3$ points. Any two points in the same group are joined by a segment. a) Determine which of the possible arrangements in $10$ such groups is the one giving the minimal numbers of triangles. b) Prove that there exists an arrangement in such groups where each segment can be coloured with one of three given colours and no triangle has all edges of the same colour. [i]Vasile Pop[/i]

1994 China Team Selection Test, 2

Tags: function , ratio , arithmetic sequence , algebra , system of equations , combinatorics unsolved , combinatorics

An $n$ by $n$ grid, where every square contains a number, is called an $n$-code if the numbers in every row and column form an arithmetic progression. If it is sufficient to know the numbers in certain squares of an $n$-code to obtain the numbers in the entire grid, call these squares a key. [b]a.) [/b]Find the smallest $s \in \mathbb{N}$ such that any $s$ squares in an $n-$code $(n \geq 4)$ form a key. [b]b.)[/b] Find the smallest $t \in \mathbb{N}$ such that any $t$ squares along the diagonals of an $n$-code $(n \geq 4)$ form a key.

2006 Pan African, 5

Tags: counting , distinguishability , combinatorics unsolved , combinatorics

In how many ways can the integers from $1$ to $2006$ be divided into three non-empty disjoint sets so that none of these sets contains a pair of consecutive integers?

2002 China Team Selection Test, 3

Tags: inequalities , combinatorics unsolved , combinatorics

Seventeen football fans were planning to go to Korea to watch the World Cup football match. They selected 17 matches. The conditions of the admission tickets they booked were such that - One person should book at most one admission ticket for one match; - At most one match was same in the tickets booked by every two persons; - There was one person who booked six tickets. How many tickets did those football fans book at most?

2003 Tournament Of Towns, 3

Tags: combinatorics unsolved , combinatorics

A salesman and a customer altogether have $1999$ rubles in coins and bills of $1, 5, 10, 50, 100, 500 , 1000$ rubles. The customer has enough money to buy a Cat in the Bag which costs the integer number of rubles. Prove that the customer can buy the Cat and get the correct change.

1997 Belarusian National Olympiad, 1

Tags: combinatorics unsolved , combinatorics

We call the sum of any $k$ of $n$ given numbers (with distinct indices) a $k$-sum. Given $n$, find all $k$ such that, whenever more than half of $k$-sums of numbers $a_{1},a_{2},...,a_{n}$ are positive, the sum $a_{1}+a_{2}+...+a_{n}$ is positive as well.

2000 China National Olympiad, 3

Tags: combinatorics unsolved , combinatorics , Set systems

A test contains $5$ multiple choice questions which have $4$ options in each. Suppose each examinee chose one option for each question. There exists a number $n$, such that for any $n$ sheets among $2000$ sheets of answer papers, there are $4$ sheets of answer papers such that any two of them have at most $3$ questions with the same answers. Find the minimum value of $n$.

2009 All-Russian Olympiad, 4

Tags: modular arithmetic , geometry , geometric transformation , rotation , combinatorics unsolved , combinatorics

On a circle there are 2009 nonnegative integers not greater than 100. If two numbers sit next to each other, we can increase both of them by 1. We can do this at most $ k$ times. What is the minimum $ k$ so that we can make all the numbers on the circle equal?

2014 Singapore Senior Math Olympiad, 5

Tags: ceiling function , combinatorics unsolved , combinatorics

Alice and Bob play a number game. Starting with a positive integer $n$ they take turns changing the number with Alice going first. Each player may change the current number $k$ to either $k-1$ or $\lceil k/2\rceil$. The person who changes $1$ to $0$ wins. Determine all $n$ such that Alice has a winning strategy.

2007 Indonesia TST, 1

Tags: geometry , parallelogram , combinatorics unsolved , combinatorics

Call an $n$-gon to be [i]lattice[/i] if its vertices are lattice points. Prove that inside every lattice convex pentagon there exists a lattice point.

1999 Hungary-Israel Binational, 3

Tags: combinatorics unsolved , combinatorics

In a multiple-choice test, there are 4 problems, each having 3 possible answers. In some group of examinees, it turned out that for every 3 of them, there was a question that each of them gave a different answer to. What is the maximal number of examinees in this group?

2004 Tournament Of Towns, 3

Tags: combinatorics unsolved , combinatorics

What is the maximal number of knights that can be placed on the usual 8x8 chessboard so that each of then threatens at most 7 others?

2003 Iran MO (3rd Round), 14

Tags: induction , combinatorics unsolved , combinatorics

n \geq 6 is an integer. evaluate the minimum of f(n) s.t: any graph with n vertices and f(n) edge contains two cycle which are distinct( also they have no comon vertice)?

2003 Vietnam Team Selection Test, 1

Tags: analytic geometry , calculus , integration , binomial coefficients , combinatorics unsolved , combinatorics

Let be four positive integers $m, n, p, q$, with $p < m$ given and $q < n$. Take four points $A(0; 0), B(p; 0), C (m; q)$ and $D(m; n)$ in the coordinate plane. Consider the paths $f$ from $A$ to $D$ and the paths $g$ from $B$ to $C$ such that when going along $f$ or $g$, one goes only in the positive directions of coordinates and one can only change directions (from the positive direction of one axe coordinate into the the positive direction of the other axe coordinate) at the points with integral coordinates. Let $S$ be the number of couples $(f, g)$ such that $f$ and $g$ have no common points. Prove that \[S = \binom{n}{m+n} \cdot \binom{q}{m+q-p} - \binom{q}{m+q} \cdot \binom{n}{m+n-p}.\]

2012 USA TSTST, 9

Tags: graph theory , combinatorics unsolved , combinatorics , Binary operation

Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called [i]simple[/i] if it satisfies $(x \times y) \times z = x \times (y \times z)$ for all $x,y,z \in S$ and $x \times y \in \{x,y\}$ for all $x,y \in S$. Given a simple operation $\times$ on $S$, any string of elements in $S$ can be reduced to a single element, such as $xyz \to x \times (y \times z)$. A string of variables in $S$ is called[i] full [/i]if it contains each variable in $S$ at least once, and two strings are [i]equivalent[/i] if they evaluate to the same variable regardless of which simple $\times$ is chosen. For example $xxx$, $xx$, and $x$ are equivalent, but these are only full if $n=1$. Suppose $T$ is a set of strings such that any full string is equivalent to exactly one element of $T$. Determine the number of elements of $T$.

1995 China Team Selection Test, 3

Tags: vector , combinatorics unsolved , combinatorics

21 people take a test with 15 true or false questions. It is known that every 2 people have at least 1 correct answer in common. What is the minimum number of people that could have correctly answered the question which the most people were correct on?

2013 Vietnam Team Selection Test, 6

Tags: combinatorics , combinatorics unsolved

A cube with size $10\times 10\times 10$ consists of $1000$ unit cubes, all colored white. $A$ and $B$ play a game on this cube. $A$ chooses some pillars with size $1\times 10\times 10$ such that no two pillars share a vertex or side, and turns all chosen unit cubes to black. $B$ is allowed to choose some unit cubes and ask $A$ their colors. How many unit cubes, at least, that $B$ need to choose so that for any answer from $A$, $B$ can always determine the black unit cubes?

2005 Balkan MO, 4

Tags: combinatorics unsolved , combinatorics

Let $n \geq 2$ be an integer. Let $S$ be a subset of $\{1,2,\dots,n\}$ such that $S$ neither contains two elements one of which divides the other, nor contains two elements which are coprime. What is the maximal possible number of elements of such a set $S$?

2006 MOP Homework, 4

Tags: combinatorics unsolved , combinatorics

The squares of an n*n chessboard (n >1) are filled with 1s and -1s. A series of steps are performed. For each step, the number in each square is replaced with the product of the numbers that were in the squares adjacent. Find all values of n for which, starting from an arbitrary collection of numbers, after finitely many steps one obtains a board filled with 1s.