Combinatorics Problem in Shortlist IMO problem 2015

Problem 1:

In Line land there are n\geqslant 1 towns, arranged along a road running from left to right. Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer (put to the right of the town and facing right). The sizes of the 2n bulldozers are distinct. Every time when a right and a left bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, the bulldozers are quite unprotected at their rears; so, if a bulldozer reaches the rear end of another one, the first one pushes the second one off the road, regardless of their sizes.

Let A and B be two towns, with B being to the right of A. We say that town A can sweep town B away if the right bulldozer of A can move over to B pushing off all bulldozers it meets. Similarly, B can sweep A away if the left bulldozer of B can move to A pushing off all bulldozers of all towns on its way.

Also Read:

Prove that there is exactly one town which cannot be swept away by any other one.(Also Read : Solution )

Problem 2 :

Let V be a finite set of points in the plane. We say that V is balanced if for any two distinct points A,B\in V, there exists a point C\in V such that AC = BC. We say that V is center-free if for any distinct points A,B,C\in V, there does not exist a point P\in V such that PA = PB = PC.

  • Show that for all n\geqslant 3, there exists a balanced set consisting of n points.
  • For which n\geqslant 3 does there exist a balanced, center-free set consisting of n points? (Read : Solution )

Problem 3:

For a finite set A of positive integers, we call a partition of A into two disjoint nonempty subsets A1 and A2 good if the least common multiple of the elements in A1 is equal to the greatest common divisor of the elements in A2. Determine the minimum value of n such that there exists a set of n positive integers with exactly 2015 good partitions. (Read : Solution )

Problem 4:

Let n be a positive integer. Two players A and B play a game in which they take turns choosing positive integers k\leqslant n. The rules of the game are:

  1. A player cannot choose a number that has been chosen by either player on any previous turn.
  2. A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.
  3. The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.

The player A takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies. (Read : Solution )

Problem 5:

Consider an infinite sequence a1, a2, …. of positive integers with a_i\leqslant 2015 for all i\geqslant 1. Suppose that for any two distinct indices i and j we have i+a_i\neq j+a_j.

Prove that there exist two positive integers b and N such that

Whenever n>m\geqslant N. ( Read : Solution )

Problem 6:

Let S be a nonempty set of positive integers. We say that a positive integer n is clean if it has a unique representation as a sum of an odd number of distinct elements from S. Prove that there exist infinitely many positive integers that are not clean. (Read : Solution )

Problem 7:

In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least 3, and it is possible to arrange all its members around a round table so that every two neighbours are enemies. Given that there are at most 2015 unsociable groups, prove that it is possible to partition the company into 11 parts so that no two enemies are in the same part. (Read : Solution problem 7 )

%d bloggers like this: