## Posts

Showing posts from December, 2014

### Maximum Number of Collinear Points

Source: Asked to me by a friend - who was asked this question in an interview at Facebook

Problem:

Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm?

### Mathematics of SET game

Source: Sent to me by Pritish Kamath (http://www.mit.edu/~pritish/)

Problem:

Have you ever played "SET"? You have to play it.
http://www.setgame.com/learn_play
http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf

Even if you have not played the game, the game can be stated in a more abstract way as follows:
There are 12 points presented in F34 and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added.
Problem 1: How many points in F34 are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in F34, what is the probability that there exists a line among them?
Disclaimer:
We have not solved the problem yet. It can be very difficult or very easy.
Update (22/12/14):
It turns out to be a very very difficult problem.
Paper: http://www.math.rutgers.edu/~maclagan/papers/set.pdf