Jan 26, 2013

Determinant of Binary Matrix

Source: Introduced to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008)


An N by N matrix M has entries in {0,1} such that all the 1's in a row appear consecutively. Show that determinant of M is -1 or 0 or 1.

I could not solve it but I have an awesome solution sent by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012)

Update (2/4/2013):
Solution posted by Amol Sahasrabudhe (IITB 2004 Alumnus, Ex-Morgan Stanley Quant Associate, Deutsche Bank Quant Associate) and Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments! Thanks a ton. I have posted the solution provided by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012). All three solutions are essentially the same.

Jan 15, 2013

Evenly Spaced Ones in Binary String

Source: Sent to me by Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student)

Given a arbitrary binary string of length n, find three evenly spaced ones within the string if they exist. Write an algorithm which solves this in O(n * log(n)) time.

Update (29th January 2013):
Solution posted by JDGM in comments!

Jan 5, 2013

Fermat Theorem Puzzle

Source: Andrej Cherkaev's List of Puzzles

A computer scientist claims that he proved somehow that the Fermat theorem is correct for the following 3 numbers:


He announces these 3 numbers and calls for a press conference where he is going to present the value of N (to show that

x^N + y^N = z^N

and that the guy from Princeton was wrong). As the press conference starts, a 10-years old boy raises his hand and says that the respectable scientist has made a mistake and the Fermat theorem cannot hold for those 3 numbers. The scientist checks his computer calculations and finds a bug.

How did the boy figure out that the scientist was wrong?

Update (06/01/2012):
Solution posted by a lot of people in comments!

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...