Regional Math Olympiad (India) Combinatorics Problems

Regional Math Olympiad (India) Combinatorics Problems

A person moves in the x − y plane moving along points with integer co-ordinates x and y only. When she is at point (x, y), she takes a step based on the following rules: (a) if x + y is even she moves to either (x + 1, y) or (x + 1, y + 1); (b) if x + y is odd she moves to either (x, y + 1) or (x + 1, y + 1). How many distinct paths can she take to go from (0, 0) to (8, 8) given that she took exactly three steps to the right ((x, y) to (x + 1, y))? (RMO 2014, Mumbai Region)

A finite non-empty set of integers is called 3-good if the sum of its elements is divisible by 3. Find the number of non-empty 3-good subsets of {0, 1, 2, . . . , 9}. (RMO 2013, Mumbai Region)

Let X = {1, 2, 3, . . . , 10}. Find the the number of pairs {A, B} such that A ⊆ X, B ⊆ X, A 6= B and A ∩ B = {2, 3, 5, 7}. (RMO 2012)

Let \((a_1, a_2, a_3, . . . , a_{2011}) \) be a permutation (that is a rearrangement) of the numbers 1, 2, 3, . . . , 2011. Show that there exist two numbers j, k such that \(1 \le j < k \le 2011 \) and | \(a_j – j \)| = |\({a_k – k}\) | . (RMO 2011)

Consider a 20-sided convex polygon K, with vertices \(A_1, A_2, . . . , A_{20} \) in that order. Find the number of ways in which three sides of K can be chosen so that every pair among them has at least two sides of K between them. (For example \((A_1A_2, A_4A_5, A_{11}A_{12}) \) is an admissible triple while \((A_1A_2, A_4A_5, A_{19}A_{20}) \) is not.) (RMO 2011)

Can you post the answers please..