Shortlist problem Combinatorics in IMO 2016 ( international mathematic Olympiad)
Problem combinatoric 1 :
The leader of an IMO team chooses positive integers n and k with n > k, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an n-digit binary string, and the deputy leader writes down all n-digit binary strings which differ from the leader’s in exactly k positions. (For example, if n = 3 and k = 1, and if the leader chooses 101, the deputy leader would write down 001, 111 and 100.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of n and k) needed to guarantee the correct answer?
Also Read : The Solution Problem 1
Problem Combinatoric 2:
Find all positive integers n for which all positive divisors of n can be put into the cells of a rectangular table under the following constraints:
- each cell contains a distinct divisor;
- the sums of all rows are equal; and
- the sums of all columns are equal.
Problem Combinatoric 3 :
Let n be a positive integer relatively prime to 6. We paint the vertices of a regular n-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.
Problem Combinatoric 4 :
Find all positive integers n for which we can fill in the entries of an n x n table with the following properties:
- each entry can be one of I, M and O;
- in each row and each column, the letters I, M and O occur the same number of times; and
- in any diagonal whose number of entries is a multiple of three, the letters I, M and O occur the same number of times.
Problem Combinatoric 5 :
Let be a positive integer. Find the maximum number of diagonals of a regular n-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.
Problem Combinatoric 6:
There are islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route.
After each year, the ferry company will close a ferry route between some two islands X and Y . At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected by a ferry route to exactly one of X and Y , a new route between this island and the other of X and Y is added.
Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.
Problem Combinatoric 7:
Let be an integer. In the plane, there are n segments given in such a way that any two segments have an intersection point in the interior, and no three segments intersect at a single point. Jeff places a snail at one of the endpoints of each of the segments and claps his hands n – 1 times. Each time when he claps his hands, all the snails move along their own segments and stay at the next intersection points until the next clap. Since there are n – 1 intersection points on each segment, all snails will reach the furthest intersection points from their starting points after n 1 claps.
- Prove that if n is odd then Jeff can always place the snails so that no two of them ever occupy the same intersection point.
- Prove that if n is even then there must be a moment when some two snails occupy the same intersection point no matter how Jeff places the snails.
Problem Combinatoric 8:
Let n be a positive integer. Determine the smallest positive integer k with the following property: it is possible to mark k cells on a 2n x 2n board so that there exists a unique partition of the board into 1 x 2 and 2 x 1 dominoes, none of which contains two marked cells.