MathDB

3

Part of 2011 India IMO Training Camp

Problems(4)

Good subsets

Source: Indian TST Day 2 Problem 3

6/20/2011
Let TT be a non-empty finite subset of positive integers ≥1\ge 1. A subset SS of TT is called good if for every integer t∈Tt\in T there exists an ss in SS such that gcd(t,s)>1gcd(t,s) >1. Let
A=(X,Y)∣X⊆T,Y⊆T,gcd(x,y)=1for allx∈X,y∈YA={(X,Y)\mid X\subseteq T,Y\subseteq T,gcd(x,y)=1 \text{for all} x\in X, y\in Y}
Prove that : a)a) If X0X_0 is not good then the number of pairs (X0,Y)(X_0,Y) in AA is even. b)b) the number of good subsets of TT is odd.
number theorygreatest common divisorsearchcombinatorics unsolvedcombinatorics
Balanced set

Source: Indian TST Day 1 problem 3.

7/2/2011
A set of nn distinct integer weights w1,w2,…,wnw_1,w_2,\ldots, w_n is said to be balanced if after removing any one of weights, the remaining (n−1)(n-1) weights can be split into two subcollections (not necessarily with equal size)with equal sum.
a)a) Prove that if there exist balanced sets of sizes k,jk,j then also a balanced set of size k+j−1k+j-1. b)b) Prove that for all odd n≥7n\geq 7 there exist a balanced set of size nn.
combinatorics unsolvedcombinatorics
Staircase problem

Source: India TST III-Problem 3

5/23/2011
Consider a n×n n\times n square grid which is divided into n2 n^2 unit squares(think of a chess-board). The set of all unit squares intersecting the main diagonal of the square or lying under it is called an nn-staircase. Find the number of ways in which an nn-stair case can be partitioned into several rectangles, with sides along the grid lines, having mutually distinct areas.
rectangleinductionLaTeXcombinatorics unsolvedcombinatorics
Two sequences...

Source: Indian TST Day 4 Problem 3

6/20/2011
Let {a0,a1,…}\{a_0,a_1,\ldots\} and {b0,b1,…}\{b_0,b_1,\ldots\} be two infinite sequences of integers such that (an−an−1)(an−an−2)+(bn−bn−1)(bn−bn−2)=0(a_{n}-a_{n-1})(a_n-a_{n-2}) +(b_n-b_{n-1})(b_n-b_{n-2})=0 for all integers n≥2n\geq 2. Prove that there exists a positive integer kk such that ak+2011=ak+20112011.a_{k+2011}=a_{k+2011^{2011}}.
functionnumber theory unsolvednumber theory