## Posts

Showing posts from 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

### Expected Number of Attempts - Broken Coffee Machine

Related Problem:Expected Length of Last Straw - Breaking the back of a Camel - CSE Blog

Problem:

Your boss tells you to bring him a cup of coffee from the company vending machine. The problem is the machine is broken. When you press the button for a drink, it will randomly fill a percentage of the cup (between 0 and 100 percent). You know you need to bring a full cup back to your boss.

What’s the expected number of times you will have to fill the cup?

Example: The machine fills the cup 10 percent, then 30 percent, then 80 percent–>the cup is full plus 20 percent that you throw away or drink yourself. It took 3 fills of the cup.

### Pebble Placement Puzzle 2

Source: AUSTMS Gazette 35

Related Problem:Pebble Placement Puzzle 1

Problem: Peggy aims to place pebbles on an n × n chessboard in the following way. She must place each pebble at the center of a square and no two pebbles can be in the same square. To keep it interesting, Peggy makes sure that no four pebbles form a non-degenerate parallelogram.

What is the maximum number of pebbles Peggy can place on the chessboard?

### Pebble Placement Puzzle 1

Source: AUSTMS Gazette 35

Problem:

There are several pebbles placed on an n × n chessboard, such that each pebble is inside a square and no two pebbles share the same square.

Perry decides to play the following game. At each turn, he moves one of the pebbles to an empty neighboring square. After a while, Perry notices that every pebble has passed through every square of the chessboard exactly once and has come back to its original position.

Prove that there was a moment when no pebble was on its original position.

### Diminishing Differences Puzzle Source: Australian Mathematical Society Gazette Puzzle Corner 34

Problem: Begin with n integers x1, . . . , xn around a circle. At each turn, simultaneously replace all of them by the absolute differences

Repeat this process until every number is 0, then stop. Prove that this process always terminates if and only if n is a power of 2.
Shameless plug:
Follow CSE Blog on CSE Blog - Twitter and CSE Blog on Quora. :-)

### Balancing Act Puzzle

Source:Australian Mathematical Society Gazette Puzzle Corner 35

Problem:
There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total
of W grams. Suppose W is less than the number of weights on the left multiplied by the number of weights on the right.

Is it always true that we can remove some, but not all, of the weights from each side and still keep the two sides balanced?

### "Flawless Harmony" Puzzle

Source: AUSTMS Puzzle Corner 35

Problem:

Call a nine-digit number flawless if it has all the digits from 1 to 9 in some order. An unordered pair of flawless numbers is called harmonious if they sum to 987654321. Note that (a, b) and (b, a) are considered to be the same unordered pair.

Without resorting to an exhaustive search, prove that the number of harmonious pairs is odd.

Update (23 Oct 2014):
Solution: Posted by me (Pratik Poddar) in comments!

### Minimum sum of numbers in an array

Source: Asked to me on quora ( cseblog.quora.com )

Problem:

Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array?

Example 1:
1 2 2 3 4

Example 2:
2 3 4 7 13

### Caterer's Problem Problem:

You are organizing a conference, with a festive dinner on the first day. The catering service has 1024 different dinner choices they know how to make, out of which you need to choose 10 to be in the dinner menu (each participant will choose one of these during the dinner). You send an email to the 6875 participants of the conference, with the list of all 1024 choices, asking them to rank the choices in linear order from their favorite to their unfavorite.

You want to find a list L of 10 choices, such that for any dinner choice d not in the list L, if we run a vote of d against L, at least half of people will favor one of the choices in L over d (it may be different dish for different people).

Is it always possible to produce such a list?

### 3D Tic Tac Toe Puzzle

Source: Shared by Alok Mittal (Cannan Partners)
Problem: A 3x3 tic tac toe has 8 "winning lines" (3 horizontal, 3 vertical and 2 diagonals). How many "winning lines" does the 3x3x3 3D tictactoe have? There is a brute force solution, and then there is the aha! solution.

Update (23 Oct 2014)
Solution: Posted in comments by Anti, Taz, Javier, Shubham Gupta, Leela. Detailed solution and much more advanced problems in the document http://library.msri.org/books/Book42/files/golomb.pdf Source:http://nrich.maths.org/

Problem:

A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions:

SUB JOURNEY
DISTANCE = 1000
WHILE (DISTANCE > 0.001)
MOVE DISTANCE
STOP
ROTATE(90, DEGREES, CLOCKWISE)
DISTANCE = DISTANCE / 2
END WHILE
EXPLODE
END SUB

Where does the robot explode?

Update (23 Oct 2014):
Solution: Posted by me (Pratik Poddar) in comments! Problem / Observation:

The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically.

Update (23 Oct 2014):
Solution: Posted by Mike Earnest and Taz in comments!

### Expected length of Last Straw - Breaking the back of a camel

Source:Puzzle Tweeter who took it from Mind your decisions

Problem: A camel is loaded with straws until it's back breaks. Each straw has a weight uniformly distributed between 0 and 1, independent of other straws. The camel's back breaks as soon as the total weight of all the straws exceeds 1. Find the expected weight of the last straw that breaks the camel's back.

Update (18th June 2014):
Solution posted by me (Pratik Poddar) in comments

### Cards on a Square Turntable

Source:Steve Miller's Math Riddles

Problem:

A square has a quarter in each corner. You are blindfolded and must get all quarters to be heads up or all to be tails up. You will be told when you have done this. You may flip however many you want, then ask if you are done (this constitutes a turn). The square is then rotated/spun an undisclosed number of times. You then get another turn and so on…

Is there a strategy that is guaranteed to work in a finite number of moves, and if so, what is that smallest number of moves you need to be 100% you’ll be able to have all heads up or all tails up?
The same problem is there on the blog - in a different form - asked more than 50 months back :-) - Blind Flipping - CSE Blog

### Cut the Polygon Puzzle - the solution will make you smile Source:FunctionSpace.org

Problem: Given the polygons P and Q as shown in the grid below, cut P into two polygons P1 and P2 such that, when pasted together differently, they form Q.

Update ( 21 June 2014 ) :

### Value of Pi - Estimation using Dice Source: Asked to a friend at Goldman Sachs Quant Interview
Problem: Estimate the value of pi using a dice
Update: (21 June 2014) Solution posted by Tushar Makkar, 'My first amateur attempt', Satadip, Gaurav Bajaj and me (Pratik) in comments. Thanks

### (2n choose n) is never a perfect power

Source: Cute problem sent by Sudeep Kanath

Problem: Prove that (2n choose n) is never a perfect power

Update ( 21 June 2014 ):
Solution: Posted by Sandeep, Dinesh Krithivasan and Vishal Khatri in comments.

### Coin Problem - Wolfram Mathematica Puzzle

Source: The super awesome puzzle blog by Gowtham Kumar - Puzzle Tweeter - Coin Problem who got it from Wolfram Mathematica

Problem:
Suppose you have an infinite stock of \$a bills and \$b bills such that g.c.d(a,b)=1. Find the largest amount of money (integer) that cannot be represented using \$a and \$b denominations.

Shameless plug: