Pages

Tuesday, November 27, 2012

Subsets

Let [n] = {1,2,3,....,n}. We divide [n] into m subsets A1,A2.....Am, such that they satisfy the properties:
1). For all i, |Ai| is odd.
2). For all distinct i and j, |Ai ∩ Aj| is even.
Prove that m<=n, where for a set X, |X| denotes number of elements in X.

Courtesy : Prof. Sundar Vishwanathan, IIT Bombay

Monday, November 19, 2012

Squared squares

There is a square S of unit side. There are n disjoint smaller squares inside S, with sides parallel to the sides of S, where n is a perfect square. Prove that one can always draw a line parallel to some side of S, which passes through S and at most √n smaller squares.

Source : Algo Muse

Thursday, November 15, 2012

Footballers

There are 23 football players, with some strength associated with each player. To conduct a football match among them, you select a referee and divide the remaining 22 players into two groups with 11 players each and with total strength of one group(sum of strengths of all players) equal to total strength of the other(If possible).

The given set of strengths is in a way that it is possible to start a game with any player as referee. Prove that all players have equal strengths.

Courtesy : Vinod Kumar Reddy

Friday, October 5, 2012

Complete this sequence

Find the next term in the sequence 1, 11, 21, 1211. 111221. 312211, 13112221 ?(Not using the polynomial method).

Courtesy : Quora.

Tuesday, September 25, 2012

Necklaces

We say that two necklaces are different if one cant be obtained from another by rotating it (by whatever angle). Calculate the total number of different necklaces possible with N beads of R(<N) different colors.

Courtesy : Prof. Sharad Sane - IIT Bombay