Friday, September 26, 2008

Challenge problem - From a classic Steven Krantz book -

I have simply been unable to crack this one, particularly the general version of this problem... any hints ?
You have six points on a piece of paper. Every point will be joined to every other point by either by a red line segment or by a blue line segment. You can colour any line in anyway you choose. Show that there will have to be either be a triangle that is all blue or a triangle that is all red.
Formulate a generalization of the last problem. Suppose that you have k colors. How many points are required to guarantee that the process of joining all possible pairs of points with line segment segments of one of these colors will guarantee that there is a triangle of just one color?

Saturday, September 13, 2008

Interesting problems - first batch

Housie Magic -
This one arose from a party in my company, where we played Housie. The game goes like this - Every participant is distributed Housie tickets, each of which has 15 random numbers (distinct on a given ticket) printed on them. Numbers are between 1 to 100. Next, random numbers in the same range are selected and the numbers are called out. All participants who have the number on their ticket cross them. The first participant who gets all numbers crossed on their own ticket wins, and gets the prize.
Certainly, all numbers on the ticket are random and those called are random too. So everyone has an equal chance of winning. But there is a twist .....
What if you are allowed to take up more than one ticket ? You then get a bigger range of numbers to cross. Does that increase your chances of winning the prize ? Remember that to win, you need to have all numbers on any single ticket crossed.
Comments welcome ...
Sorting -
I ask this one for interviews and get varying answers... Given an array of integers (of size N), what is the most efficient algorithm to find out the 'K' largest numbers ? Note that K <= N, K > 0.
We don't want the largest K numbers to be sorted by themselves, just find the largest set. Is there a way to find the K numbers in less than O(N*K) ?

Wednesday, May 7, 2008

IPL - Manoranjan ka Baap

I and at least the few gentlemen around me have begun to wonder when the IPL circus is going to end ... Not that I don't like cricket - I have watched matches even in my university exam days. With IPL, its like if you love chocolate cake, you are asked to eat it everyday for two months. The organisers should have known how cricket tournaments tend drag on and on.

I watch cricket to get a sense of competition, aggression, and the drive to win among the teams. To give you an idea, remember the classic moments - Javed Miandad's last ball match winning six, Sachin's consecutive Sharjah centuries against Australia or Kluesener's 1999 world cup exploits. But the overwhelming feeling I get while watching IPL is that of a money-spinning exercise, the junk food of cricket. You don't get to savour the chocolate cake, because you are made to eat it rapidly before another helping arrives.

Saving grace - IPL's all purely market-driven. If it becomes unpopular, it won't sustain even with Cricket Board's backing ... Nobody needs to kill it... like dead rubber Test Matches (imagine a Test match played between India - Sri Lanka on flat, dusty wicket). If spectators stick with it, it will live, else it will die on its own.

Saturday, May 3, 2008

Starting up...

Tune in to this spot for thoughts on Computing, Economics, Science, Literature and just about everything under the Sun.