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).