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

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

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

Complete this sequence

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

Courtesy : Quora.

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

Picking hats

N people come to a room to attend a conference. They leave their hats outside the room. When the conference ended, the people were in a hurry, so they picked one hat each at random, one after another. Given N is considerably large, find the probability that no one gets his/her own hat.

Courtesy : Prof. Sharad Sane, IIT Bombay.

The "ballot" problem

There are two candidates contesting for a post, A and B. Elections have ended and A got total a votes and B got total b votes, with a > b. Every person voted must vote for either A or B. They shuffled the ballot box and started counting. A is declared winner only if he leads at every point of counting. What is the probability that A will win the elections?

Courtesy : Prof. S.B. Pillai

Connect the pyramids

We have two pyramids, a square-base right pyramid and a triangle-base right pyramid. All the edges of both the pyramids are of equal length. We joined both the pyramids with one of the triangle-faces of one pyramid coinciding with one of the triangle-faces of another. What are the total number of faces of the new solid figure obtained?

Source : Winkler - Mathematical puzzles (Please go through this book. It is really good)

The "Mailbox" problem

We have n mailboxes, which each have a key and all keys are distinct. There is a master key which works for every mailbox.

Now, each key is put in one mailbox, and all mailboxes are locked using the master key.

So, what we have here is n locked mailboxes, which each has a key to one of those n mailboxes.

You want to open all the boxes. To start with, you have to break one box, take key from that, and open its corresponding box. When you find key to first box, you have to break another box and so on.

So, given you can break k boxes, what is the probability that you will be able to open all the mailboxes?

Courtesy: Prof. Sharad S. Sane, IIT Bombay.

Sequence of non-powers of primes

Given a natural number n, prove that we can always find out n consecutive natural numbers such that none of them is a perfect power of any prime.

Courtesy: Vinod reddy

Factorial-base representation

Show that every non-negative integer n can be uniquely represented as

n = a1*(1!) + a2*(2!) + a3*(3!) ...........

where all ai are integers and 0 <= ai <= i for all i.

Courtesy: Prof. Sharad S. Sane, IIT Bombay.

City-roads

There is a country consisting of N cities, just built. So, now you must build roads for the cities. Each road is a two-way path joining two cities. The way it works is, in one turn, you must choose two cities, and if there is no road between them, build a road, else, leave it as it is. What is the estimated number of turns required to build the roads such that there is a way from every city to every other city?

Courtesy : Aakash rao NS

Divisor - Nim

Alice and Bob are back in gaming. This time it is with numbers. They take a jar containing all the numbers from 1 to n. The game goes on like this. Alice starts the game, she picks a number x from numbers in the jar. Then, she removes all the divisors of x (including x). Alice and Bob repeat the steps without replacement. The player to draw the last number wins. Who will win the game (in terms of n if it depends on n) ?

Courtesy : Vinod

Complete the sequence

Find the next element in the sequence:
10 11 12 13 14 20 22 ... (Without using the polynomial-method)

Courtesy: QED 2012

The even fibonacci

Prove that F[2n] cannot be of the form 4k+2, where F[i] is ith Fibonacci number. (F[0] = 0, F[1] = 1 etc...)

Value of selection

There is a 2 dimensional matrix M ( mxn ) of non-negative integers. A "selection" is defined as set of elements, satisfying the following condition:
If m>n then there is exactly one element from each column. Else, there is exactly one element from each row.
And sum of all elements of a selection is called its "value".
Find the selection with maximum "value" in O(m*n).

Second largest element in an array

Given an unsorted array of size n, find the second largest element of the array in "n + log(n)" steps.
( Its not O(n+log(n)), its "n + log(n)" ).

Courtesy : Career cup.